← 返回题目列表

Codeforces · 1458/C

C. 拉丁方

中文机器翻译题面 查看原题

给你一个大小为 $$$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

注意

示例测试用例答案之间的换行只是为了清晰起见,不必打印。