给你一个大小为 $$$n$$$ 的方阵。该矩阵的每一行和每一列都是 $$$1$$$、$$$2$$$、$$$\ldots$$$、$$$n$$$ 的排列。令 $$$a_{i, j}$$$ 为每个 $$$1 \leq i, j \leq n$$$ 的第 $$$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:将每列中从上到下读取的排列替换为其逆排列。
可以看到,经过任何一系列操作后,矩阵的每一行和每一列仍然是 $$$1, 2, \ldots, n$$$ 的排列。
给定初始矩阵描述,您应该处理 $$$m$$$ 运算并输出最终矩阵。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,打印 $$$n$$$ 行,每行包含 $$$n$$$ 个整数 - $$$m$$$ 运算后的最终矩阵。
示例
输入 #1
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
输出 #1
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
注意
示例测试用例答案之间的换行只是为了清晰起见,不必打印。