Problem T
L Keys
You need to get into a locked file with a rather strange lock system. You can make a file lock out of any $\mathcal{NP}$-hard problem you want in theory and the author of this file seems to have really taken that to heart, intending to show that it is not just possible in theory but in practice.
When you try to open it, it shows you a pixelated shape you have to fill with L-shaped blocks. You of course know that tiling such a shape with such blocks is a $\mathcal{NP}$-hard problem, so you need some additional information for this to be at all feasible.
Some time later you manage to figure out that the time it takes the system to check whether a tiling is valid is dependant on the number of tile corners that are in the correct place. Using this you arduously manage to figure out where all the corners go. Is this enough to solve the problem?
Input
The first line of input contains two integers $1 \leq R, C \leq 512$. Next there are $R$ lines, each with $C$ letters, which describe the shape that needs to be covered with L shaped blocks. The character . denotes a pixel that is not part of the shape. The letter o denotes a pixel that is the corner of an L shaped block. The letter x denotes a pixel covered by a L shaped block but is not a corner.
You may assume there is a solution to the input.
Output
Print the input again but replace the letters x by <, ^, >, v such that the character points to the corner of the L shape it belongs to.
If there is more than one correct answer any one of them will be accepted.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 xo .x x. ox |
4 2 >o .^ v. o< |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 5 xxoxo oxxxx oxxox xxoxo xxoxx oxxox |
6 5 v>o>o o<^v^ o<vo< ^>o>o v>ov^ o<^o< |
| Sample Input 3 | Sample Output 3 |
|---|---|
15 15 ........xx..... .......xoox.... ......xxooxx... .....xoxxxxox.. ....oxxo..oxxx. ...xxox....xoox ..xoxx.....xoox .xxxo.....oxxx. xoox.....xxox.. xoox....xoxx... .xxxo..oxxo.... ..xoxxxxox..... ...xxooxx...... ....xoox....... .....xx........ |
15 15 ........vv..... .......>oo<.... ......v>oo<v... .....>ov^^vo<.. ....o<>o..o<vv. ...v^o<....>oo< ..>ov^.....>oo< .vv>o.....o<^^. >oo<.....v^o<.. >oo<....>ov^... .^^>o..o<>o.... ..>o^vv^o<..... ...^>oo<^...... ....>oo<....... .....^^........ |
