Rotate an ASCII art image Out of all of the ASCII characters, it is easy to tell that some of them form groups that are rotations of the same basic character. For example, V &gt; ^ &lt;. This allows the possibility to construct ASCII art that can be rotated by multiples of 90 degrees and still remain ASCII art.

The Challenge

Your goal is to golf a program that accepts ASCII art and the number of degrees to rotate it from STDIN, and prints the rotated ASCII art to STDOUT.

On the first line of input, your program will receive a number N. This number represents the width and height of the ASCII art. 

You will then receive N more lines of exactly N characters each (the newline is not counted in this number). The size of the art will always be a square, although it may have padding in the form of spaces to make it a square.

You will then receive one more number on a final line: 90, 180, or 270. This represents how many degrees clockwise the picture should be rotated.

Note: The inputted image will only contain characters that can be rotated by the correct amount. If the input does not match these requirements exactly, no specific behavior is required.

As output, your program should print exactly N lines of N characters, with newlines after each line. The image should be rotated so that each character in the original has been replaced by a rotated version and has been moved to the correct place in the image.

Examples (not very beautiful ASCII art)

Input

5
&lt;- ||
|  |V
+-&gt;+ 
   |O
&lt;--+ 
90


Output

^ +-^
| | |
| V  
+-+--
 O &lt;-


(Rotations by 90 and 270 won't look very good because the characters are not squares)

Input

6
+ /\ +
| \ \|
(  \/|
 \   )
I \ / 
:) V $
180


Output

$ ^ (:
 / \ I
(   \ 
|/\  )
|\ \ |
+ \/ +


Required Supported Characters

For all rotations (90, 180, and 270), the program should be able to rotate:


Spaces, +, @, X and O which never change
V  &gt; &lt; ^
| - and \ / (rotated by 180 they stay the same)


For 180 degree rotation, these additional characters must be supported


I N Z % : 0 = S ~ $ # which stay the same
P d, ( ), [ ], { }, M W, and 9 6
C, 336 chars

I'm sure there's room for improvement.

char*a="&lt;^&gt;V|-|-/\\/\\ppdd(())[[]]{{}}MMWW9966",*p,*q;
n,x,y,r;
z(c){
    return(q=strchr(a,c))?a[(q-a&amp;-4)+(q-a+r&amp;3)]:c;
}
#define A(r)(r&amp;3^3?1-r%4:0)*
f(r){
    return A(r)x+A(~-r)y+(r&amp;2)/2*~-n;
}
main(){
    scanf("%d\n",&amp;n);
    p=q=malloc(n*n+1);
    for(y=n;y--;q+=n)gets(q);
    scanf("%d",&amp;r);
    for(r/=90;++y&lt;n;puts(""))for(x=0;x&lt;n;x++)putchar(z(p[f(r)+n*f(r+1)],r));
}