CF1458C.Latin Square

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.

Inverse of a permutation $p_1$, $p_2$, $\ldots$, $p_n$ is a permutation $q_1$, $q_2$, $\ldots$, $q_n$, such that $p_{q_i} = i$ for every $1 \leq i \leq n$.

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.

给你一个大小为 $n$ 的方阵。该矩阵的每一行和每一列都是 $1, 2, \ldots, n$ 的一个排列。对任意 $1 \leq i, j \leq n$，记 $a_{i, j}$ 为第 $i$ 行与第 $j$ 列交点处的元素。行编号从上到下依次为 $1, \ldots, n$，列编号从左到右依次为 $1, \ldots, n$。

共有六种操作类型：

• R：将所有列向右循环移动一位，形式化地，将每个 $a_{i, j}$ 的值设为 $a_{i, ((j - 2)\bmod n) + 1}$；
• L：将所有列向左循环移动一位，形式化地，将每个 $a_{i, j}$ 的值设为 $a_{i, (j\bmod n) + 1}$；
• D：将所有行向下循环移动一位，形式化地，将每个 $a_{i, j}$ 的值设为 $a_{((i - 2)\bmod n) + 1, j}$；
• U：将所有行向上循环移动一位，形式化地，将每个 $a_{i, j}$ 的值设为 $a_{(i\bmod n) + 1, j}$；
• I：将每行从左到右读出的排列替换为其逆排列；
• C：将每列从上到下读出的排列替换为其逆排列。

排列 $p_1, p_2, \ldots, p_n$ 的逆排列定义为排列 $q_1, q_2, \ldots, q_n$，使得对每个 $1 \leq i \leq n$ 均有 $p_{q_i} = i$。

可以验证，执行任意操作序列后，该矩阵的每一行和每一列仍均为 $1, 2, \ldots, n$ 的一个排列。

给定初始矩阵，你需要依次处理 $m$ 个操作，并输出最终的矩阵。

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$.

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。随后是 $t$ 个测试用例的描述。

每个测试用例描述的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 1000,\ 1 \leq m \leq 10^5$），分别表示矩阵的大小和操作次数。

接下来的 $n$ 行，每行包含 $n$ 个由单个空格分隔的整数，表示矩阵 $a$ 的描述（$1 \leq a_{i, j} \leq n$）。

该测试用例描述的最后一行是一个长度为 $m$ 的字符串，按顺序描述所有操作，格式如上所述。

所有测试用例中 $n$ 的总和不超过 $1000$，所有测试用例中 $m$ 的总和不超过 $10^5$。

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

对于每个测试用例，输出 $n$ 行，每行包含 $n$ 个整数——即经过 $m$ 次操作后的最终矩阵。

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

样例测试用例答案之间的换行仅用于提高可读性，无需输出。