Latin Square
Contest: Codeforces Round 691 (Div. 1)
Difficulty rating: 2700
Tags: math, matrices

You are given a square matrix of size $$$n$$$. Every row and every column of this matrix is a permutation of $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$n$$$. Let $$$a_{i, j}$$$ be the element at the intersection of $$$i$$$-th row and $$$j$$$-th column for every $$$1 \leq i, j \leq n$$$. Rows are numbered $$$1, \ldots, n$$$ top to bottom, and columns are numbered $$$1, \ldots, n$$$ left to right.

There are six types of operations:

- R: cyclically shift all columns to the right, formally, set the value of each $$$a_{i, j}$$$ to $$$a_{i, ((j - 2)\bmod n) + 1}$$$;
- L: cyclically shift all columns to the left, formally, set the value of each $$$a_{i, j}$$$ to $$$a_{i, (j\bmod n) + 1}$$$;
- D: cyclically shift all rows down, formally, set the value of each $$$a_{i, j}$$$ to $$$a_{((i - 2)\bmod n) + 1, j}$$$;
- U: cyclically shift all rows up, formally, set the value of each $$$a_{i, j}$$$ to $$$a_{(i\bmod n) + 1, j}$$$;
- I: replace the permutation read left to right in each row with its inverse.
- C: replace the permutation read top to bottom in each column with its inverse.

One can see that after any sequence of operations every row and every column of the matrix will still be a permutation of $$$1, 2, \ldots, n$$$.

Given the initial matrix description, you should process $$$m$$$ operations and output the final matrix.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — number of test cases. $$$t$$$ test case descriptions follow.

The first line of each test case description contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 1000, 1 \leq m \leq 10^5$$$) — size of the matrix and number of operations.

Each of the next $$$n$$$ lines contains $$$n$$$ integers separated by single spaces — description of the matrix $$$a$$$ ($$$1 \leq a_{i, j} \leq n$$$).

The last line of the description contains a string of $$$m$$$ characters describing the operations in order, according to the format above.

The sum of $$$n$$$ does not exceed $$$1000$$$, and the sum of $$$m$$$ does not exceed $$$10^5$$$.

Output format:
For each test case, print $$$n$$$ lines with $$$n$$$ integers each — the final matrix after $$$m$$$ operations.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
Line breaks between sample test case answers are only for clarity, and don't have to be printed.

Example input:
5
3 2
1 2 3
2 3 1
3 1 2
DR
3 2
1 2 3
2 3 1
3 1 2
LU
3 1
1 2 3
2 3 1
3 1 2
I
3 1
1 2 3
2 3 1
3 1 2
C
3 16
1 2 3
2 3 1
3 1 2
LDICRUCILDICRUCI

Example output:
2 3 1 
3 1 2 
1 2 3 

3 1 2 
1 2 3 
2 3 1 

1 2 3 
3 1 2 
2 3 1 

1 3 2 
2 1 3 
3 2 1 

2 3 1 
3 1 2 
1 2 3

Editorial:
For convenience, let's assume that all row and column indices, as well as matrix values, are from $$$0, \ldots, n - 1$$$ instead for $$$1, \ldots, n$$$.
If only shift operations were present, we could solve the problem in linear time: just maintain where the top left corner ends up after all the shifts, and then the matrix can be easily reconstructed (if this is not immediately clear to you, take a moment and think how this should be done). For the inverse operations, the approach is going to be similar, but we'll need a different way to look at the matrix. Instead of the matrix, let's think about the set of all triples $$$(i, j, a[i][j])$$$. Imagining a set of $$$n^2$$$ points in 3D, where $$$i, j$$$ are $$$x$$$ and $$$y$$$ coordinates in the horizontal plance, and $$$a[i][j]$$$ is the height $$$z$$$ is a good mental picture.
Shift operations apply $$$x \to (x \pm 1) \bmod n$$$ and $$$y \to (y \pm 1) \bmod n$$$ to all points. We can think of this as a translation of the entire 3D space, with some looping at the borders. Instead of the given points, let's keep track of where the point $$$(0, 0, 0)$$$ is located after the operations are done; it's just as easy as in two-dimensional version from before.
Now let's introduce the inverses. Consider, say, a row inverse operation, and all the points $$$(i, j, k)$$$, where $$$k = a[i][j]$$$, that have the same row index $$$i$$$. As an example, suppose that the top ($$$0$$$-th) row of the matrix contains numbers $$$(2, 1, 3, 0)$$$. The entries in the row correspond to points $$$(0, 0, 2)$$$, $$$(0, 1, 1)$$$, $$$(0, 2, 3)$$$, $$$(0, 3, 0)$$$. The inverse permutation to this row is $$$(3, 1, 0, 2)$$$, thus the new set of points should be $$$(0, 0, 3)$$$, $$$(0, 1, 1)$$$, $$$(0, 2, 0)$$$, $$$(0, 3, 2)$$$. In general, if there is currently a point $$$(i, j, k)$$$ in the set, then after the inverse there must be a point $$$(i, k, j)$$$. Thus, the entire operation may be summarized as "swap the second and third coordinates". Similarly, the column inverse is "swap the first and third coordinates". Again, we think of this transformation applied to the entire 3D space: this can be seen as a mirror reflection with respect to $$$y = z$$$ or $$$x = z$$$ plane.
How does this affect our "keep track of $$$(0, 0, 0)$$$" approach? It is easy to update its position: just swap respective coordinates. However, we now need to care about how the answer is reconstructed, since, say, the point $$$(1, 0, 0)$$$ not necessarily ends up one step to the right of $$$(0, 0, 0)$$$. Thus, in addition, let's keep track of how the direction vectors $$$v_x = (1, 0, 0)$$$, $$$v_y = (0, 1, 0)$$$, $$$v_z = (0, 0, 1)$$$ are permuted after all operations. Shifts do not affect them, but inverses swap two of them, depending on which coordinates where swapped.
We are almost done, we just need to reconstruct the answer at the end. If we had an initially given point $$$p = (i, j, k)$$$, where will it end up? If the origin ends up at a position represented as a vector $$$v_0 = (x, y, z)$$$, then $$$p$$$ ends up at $$$p' = v_0 + iv_x + jv_y + kv_z$$$, where $$$v_x, v_y, v_z$$$ are permuted accordingly. Once we have the result $$$p' = (i', j', k')$$$, all we need is to put $$$k'$$$ into $$$b[i'][j']$$$, where $$$b$$$ is the answer matrix.
This results, once again, in a linear time solution. This explanation could have been much shorter with some linear-algebraic machinery (basically each transformation = multiplication by a certain matrix), but I chose to leave it as elementary ($$$\neq$$$ simple!) as possible.