Beautiful mind

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Jamshid Kāshānī was a great scientist in Persia. He was also a great mathematician. The king of the time that was not satisfied with courtesy of Jamshid toward himself, put Jamshid in jail and commanded his death. 

Before they execute him, as sign of good faith, he offered Jamshid a riddle and told him if he can solve the riddle faster than him, he’s free to go. The riddle is:

“Given a n × n matrix, you should simulate a series of operations on it. The operations are:

Upawrd: shift the rows one place up. First row will be placed the last row.

Downward: shift the rows one place down. Last row will be placed before first row.

Forward: shift the columns one place to right. Last column will be placed before first column.

Backward: shift the columns one place to left. First column will be placed after last column

Transpose: transpose the matrix. First row will be placed on first column, second row on second column and so on.

Rotate: rotate the matrix 90 degrees clockwise.

You should simulate all the operations on input matrix one by one and find the resulting matrix.”
Jamshid solved the riddle way quicker than the king and was released.
Your task is to solve the above riddle.

Input

First line of input contains a single integer t (t ≤ 20). The first line of each test contains a single integer n (1 ≤ n ≤ 50). Next n lines each contain n positive integers. j-th number of i-th line is the number at row i and column j of matrix. These numbers are not  greater than 100. After that there will be a line with the sequence of operations performed on matrix in order from left to right.  It is  a string of length at most 100. Each operation is shown by a character, “U” for upwards, “D” for downwards, “F” for forwards, “B” for backwards, “T” for transpose and “R” for rotate.

Output

For each test you should print a n × n, the resulting matrix after performing all operations on it. Output matrix should be formatted as input matrix (i.e. you should print n lines each containing n integers) Numbers should be separated by a single space.

You should print an empty line after each test.

Sample Input

2
4
4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13
R
3
19 28 37
46 55 64
73 82 91
UFBDTR

Sample Output

1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 16 
 
37 28 19 
64 55 46 
91 82 73 

Submit

Source: 4th Kashan University's ACM Contest