Problem Description

There is a 2D grid with $ H $ rows and $ W $ columns.
Let the cell at the $ i $ -th row from the top and the $ j $ -th column from the left be cell $(i,\ j)$.
The information of cell $(i,\ j)$ is given by a character $ s_{i,j} $. $ s_{i,j} $ can be . , # , < , ^ , > , or v . # indicates a cell that cannot be entered, < , ^ , > , and v indicate one-way cells, and . indicates an empty cell.
You will place a robot on a non-# cell and then repeatedly move the robot to cell $(r,\ c)$ by performing the following operation:

• Move the robot to an adjacent non-# cell up, down, left, or right. You must not move the robot outside the grid.

However, when the robot is on a one-way cell, it can only move in the specified direction.
More precisely, when the robot is at cell $(i,\ j)$,

• If $ s_{i,j} $ is < , the robot can only move to cell $(i,\ j\ -\ 1)$.
• If $ s_{i,j} $ is ^ , the robot can only move to cell $(i\ -\ 1,\ j)$.
• If $ s_{i,j} $ is > , the robot can only move to cell $(i,\ j\ +\ 1)$.
• If $ s_{i,j} $ is v , the robot can only move to cell $(i\ +\ 1,\ j)$.

For each non-# cell, determine if the robot can be moved from that cell to cell $(r,\ c)$.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ r $ $ c $ $s_{1,1}\dots\ s_{1,W}$ $\vdots$ $s_{H,1}\dots\ s_{H,W}$

Output Format

Output a string of $ W $ characters for $ H $ lines.
For the $ i $ -th line, the $ j $ -th character should be # if $ s_{i,j} $ is # , o if the robot can be moved from cell $ (i,j) $ to cell $(r,\ c)$ , and x if it cannot.

Sample Input and Output

Sample Input #1

3 3
1 1
..#
^^.
><.

Sample Output #1

oo#
ooo
xxo

Sample Input #2

10 12
9 1
#.^<..><<...
#<>.#<^.<<.^
^.<>.^.^.^>.
^.>#^><#....
.>.^>#...<<>
....^^.#<.<.
.>^..^#><#.^
......#>....
..<#<...^>^.
<..^>^^...^<

Sample Output #2

#xxxxxxxxxxx
#xxx#xxxxxxx
xooxxxxxxxxx
xox#xxx#xxxx
oooxx#xxxxxx
ooooxxx#xxxx
ooooox#xx#xx
oooooo#xxxxx
ooo#xoooxxxx
xooxooooooxx

Sample Input #3

15 20
13 9
####..<#^>#>.<<><^..
#.>#>.^#^.>><>...^..
>..<>.#.>.>.>...#..<
<^>.#..<>^#<#.>.<.^.
>#<^>.>#^>#^.^.#^><^
<^.^.#<...<.><#>...#
.<>....^..#>>#..>>><
.<#<^#.>#>^^.>.##.^<
.#.^.....<<#^#><^<<<
^.#>.#^.>.^.^<<>..><
.^#^<^^^<......^>.#^
.<..#>...^>^.^<..<.^
#.^.#..#.....>#.^^.>
.#^..>>><>>>^..#^.^^
.>#..<..<>.#>..^.#.^

Sample Output #3

####xxx#xx#xxxxxxxxx
#xx#xxx#xxxxxxxxxxxx
xxxxxx#xxxxxxxxx#xxx
xxxx#xxxxx#x#xxxxxxx
x#xxxxx#xx#xxxx#xxxx
xxoxo#xxxxxxxx#xxxx#
xxoooooxxx#xx#xxxxxx
xx#xo#ox#xxxxxx##xxx
x#xxooooooo#x#xxxxxx
xx#oo#ooooooxxxoooxx
xx#ooxoooooooooooo#x
xxoo#oooooooooooooox
#ooo#oo#ooooox#oooox
x#oooxxxxoooooo#ooox
xx#oooooooo#oooxo#ox

Notes/Hints

Note

Discussion of this problem is prohibited until 2020/12/27 18:00 JST. If any discussion occurs, legal action may be taken. It is okay to publish the total score or certification level after the exam, but please do not disseminate information about which problems were solved.

Constraints

• $1\ \le\ H,\ W$
• $H\ \times\ W\ \le\ 10^6$
• $1\ \le\ r\ \le\ H$
• $1\ \le\ c\ \le\ W$
• $ s_{i,j} $ is one of . , # , < , ^ , > , or v
• $ s_{r,c} $ is not #

Sample Explanation 1

When the robot is placed at cell $ (3,3) $ , it can be moved to cell $ (1,1) $ by moving through the sequence $(3,3)\ \rightarrow\ (2,3)\ \rightarrow\ (2,2)\ \rightarrow\ (1,2)\ \rightarrow\ (1,1)$. When the robot is placed at cell $ (3,1) $ , it cannot be moved to cell $ (1,1) $ due to the one-way cells.

见题面 Input 部分

见题面 Output 部分