Rotating Display

Time limit2sMemory limit512 MB

Summary

Given an N x N grid of arrow-like tokens and a long sequence of rotations and flips, print the grid after applying every command in order.

Level: Medium6 of 10
Topics: Simulation, Matrix, Implementation
Solved: No attempts yet

Problem

Wendy is finishing her summer job in the lab, testing a new 3D printed robot that is being taught to manipulate small objects.

A simple device called the display is used to test what the robot can do. The display is a thin transparent square array of $N \times N$ square slots. Each slot holds one token shaped like an ASCII character, for easier recognition, and small magnets keep the token in its slot. The display can be rotated by 90 degrees around the axis perpendicular to its surface, and it can be flipped by 180 degrees around one of the four axes parallel to its surface.

The robot simulates a rotation or a flip like this. It takes the tokens out of their slots and puts them back into different slots so that the contents of the display look exactly as if the whole display had been rotated or flipped. If a token has to be rotated or flipped in its new position to get that effect, the robot does that too. The display itself stays still during the whole process.

For example, suppose the upper left slot holds a token shaped like <. After a flip around the vertical axis the token moves to the upper right slot, where it looks like >. After a left rotation the same token moves back to the upper left slot, where it looks like ^.

Wendy has programmed the robot to carry out a long sequence of flips and rotations. To check that the robot's algorithms are correct, she needs to know in advance how the display should look when the robot finishes.

Input

A token on the display has the shape of one of these ten symmetric characters: <, >, ^, v, o, x, |, -, /, \. When a symmetric character is rotated or flipped, it either stays the same or becomes the symmetric character whose shape is the most similar to the rotated or flipped one. Under a rotation by 90 degrees to the right, < becomes ^, ^ becomes >, > becomes v, v becomes <, | becomes -, - becomes |, / becomes \, \ becomes /, and o and x stay the same. Under a flip around the vertical axis, < and > swap, / and \ swap, and the rest stay the same. Every other operation is a composition of these two.

The input holds several test cases. Each case starts with a line containing one integer $N$ ( $1 \le N \le 100$ ). The next $N$ lines give the initial state of the display. Each of those lines is a string of exactly $N$ symmetric characters. Each character is one slot, and the order of the characters in the input matches the order of the tokens on the display. No slot is empty.

After the $N$ lines comes a line with a command string that specifies the flips and rotations to carry out. Each command character means one rotation or flip: < is a left rotation, > is a right rotation, - is a flip around the horizontal axis, | is a flip around the vertical axis, \ is a flip around the main diagonal, and / is a flip around the anti-diagonal. Two successive command characters are separated by a single space. The robot has to respect the order of the commands. The number of commands is at least 1 and at most $10^6$ .

The input ends at end of file.

The decimal ASCII codes of the characters used in this problem are 45 (-), 47 (/), 60 (<), 62 (>), 92 (\), 94 (^), 111 (o), 118 (v), 120 (x), and 124 (|).

Output

For each test case, print $N$ lines giving the final position and orientation of the tokens on the display. The output format for the display is the same as the input format, except that the size of the display is not printed.

Examples7

Example 1

Input

3
o^-
/v|
vx^
< |
5
x>-o\
voooo
|ooo/
ooo/v
\o/vv
| \ |

Expected output

>-|
x<>
</o
<</o\
</ooo
/ooo|
oooo^
\o-<x

Example 2

Input

1
<
>
1
>
>
1
^
>
1
v
>
1
o
>
1
x
>
1
|
>
1
-
>
1
/
>
1
\
>

Expected output

^
v
>
<
o
x
-
|
\
/

Example 3

Input

1
<
/
1
>
/
1
^
/
1
v
/
1
o
/
1
x
/
1
|
/
1
-
/
1
/
/
1
\
/
1
<
-
1
>
-
1
^
-
1
v
-
1
o
-
1
x
-
1
|
-
1
-
-
1
/
-
1
\
-

Expected output

v
^
>
<
o
x
-
|
/
\
<
>
v
^
o
x
|
-
\
/

Example 4

Input

4
x>-o
v|/\
^o<x
-\/|
> > > >
4
x>-o
v|/\
^o<x
-\/|
| |
4
x>-o
v|/\
^o<x
-\/|
\ \
4
x>-o
v|/\
^o<x
-\/|
/ /
4
x>-o
v|/\
^o<x
-\/|
- -
4
x>-o
v|/\
^o<x
-\/|
< >
4
x>-o
v|/\
^o<x
-\/|
> > > > > > > >
4
x>-o
v|/\
^o<x
-\/|
\ / \ /

Expected output

x>-o
v|/\
^o<x
-\/|
x>-o
v|/\
^o<x
-\/|
x>-o
v|/\
^o<x
-\/|
x>-o
v|/\
^o<x
-\/|
x>-o
v|/\
^o<x
-\/|
x>-o
v|/\
^o<x
-\/|
x>-o
v|/\
^o<x
-\/|
x>-o
v|/\
^o<x
-\/|

Example 5

Input

4
x>-o
v|/\
^o<x
-\/|
<
4
x>-o
v|/\
^o<x
-\/|
>
4
x>-o
v|/\
^o<x
-\/|
-
4
x>-o
v|/\
^o<x
-\/|
|
4
x>-o
v|/\
^o<x
-\/|
/
4
x>-o
v|/\
^o<x
-\/|
\

Expected output

o/x-
|\v\
^-o/
x><|
|><x
/o-v
\^\|
-x/o
-/\|
vo<x
^|\/
x>-o
o-<x
/\|v
x>o^
|\/-
-x\o
/v/|
\o-^
|><x
x><|
v-o\
|/^/
o\x-

Example 6

Input

3
<^>
v/o
\|-
|
3
<^>
v/o
\|-
> >
3
<^>
v/o
\|-
< <
3
<^>
v/o
\|-
> > >
3
<^>
v/o
\|-
- | -
3
<^>
v/o
\|-
\ > \
3
<^>
v/o
\|-
/ / <
3
<^>
v/o
\|-
| - | \

Expected output

<^>
o\v
-|/
-|\
o/^
<v>
-|\
o/^
<v>
^o|
<\-
v>/
<^>
o\v
-|/
^o|
<\-
v>/
^o|
<\-
v>/
/<^
-\>
|ov

Example 7

Input

2
x^
|<
/ <
2
x\
</
< < | |
2
>v
>/
< / < > \ \ /
2
<\
\|
>
2
</
^o
> / < / - / \
2
^>
\\
- < / \
2
>\
<\
| \ / |
2
x-
\-
- > > \ > <
2
\o
/-
\ | - / < <
2
/|
^x
| | <
2
>/
\x
\ - / | / |
2
>>
o-
< \

Expected output

^x
>|
/>
\x
>\
^^
/^
-/
vo
<\
<\
v\
\>
\<
||
x/
-/
o\
-x
\<
/v
x\
<<
-o