C. 拉丁方

每个测试的时间限制：2 秒
内存限制：512 兆字节

给定一个大小为 $n$ 的方阵。矩阵的每一行和每一列都是 $1, 2, \dots, n$ 的一个排列。用 $a_{i,j}$ 表示第 $i$ 行第 $j$ 列交叉处的元素，其中 $1 \le i, j \le n$。行从上到下编号为 $1, \dots, n$，列从左到右编号为 $1, \dots, 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, \dots, p_n$ 的逆排列是一个排列 $q_1, q_2, \dots, q_n$，使得对于每个 $1 \le i \le n$ 有 $p_{q_i} = i$。

容易看出，经过任意操作序列后，矩阵的每一行和每一列仍然是 $1, 2, \dots, n$ 的一个排列。

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

输入
第一行包含一个整数 $t$（$1 \le t \le 1000$）——测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 1000$，$1 \le m \le 10^5$）——矩阵的大小和操作的数量。

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

最后一行包含一个长度为 $m$ 的字符串，按顺序描述操作，格式如上所述。

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

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

示例

输入

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

输出

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

注：示例答案之间的空行仅为了清晰，实际输出时不需要打印空行。