#P9664. Latin Square

Latin Square

题目描述

本题来自 Codeforces Round #691 Latin Square。

你现在有一个 n×nn \times n 的矩阵 AA,AA 的行列编号均从 11 开始,到 nn 结束,其中 Ai,jA_{i,j} 表示 AA 第 ii 行到 jj 行的值。特别地,AA 的每一列和每一行都是一个长度为 nn 的排列。

现有如下对 AA 的操作:

  • R:将所有列向右循环移动 11 个单位,即 Ai,j mod n+1A_{i,j\bmod n+1} 的值变为 Ai,jA_{i,j};
  • L:将所有列向左循环移动 11 个单位,即 Ai,jA_{i,j} 的值变为 Ai,j mod n+1A_{i,j\bmod n+1};
  • D:将所有列向下循环移动 11 个单位,即 Ai mod n+1,jA_{i\bmod n+1,j} 的值变为 Ai,jA_{i,j};
  • U:将所有列向下循环移动 11 个单位,即 Ai,jA_{i,j} 的值变为 Ai mod n+1,jA_{i\bmod n+1,j};
  • I:将每一行排列对应的置换求逆;
  • C:将每一列排列对应的置换求逆。

对于长度为 nn 的排列 pp 而言置换求逆指得到另一个排列 qq 满足 qpi=iq_{p_i} = i。

现在长度为 mm 操作的操作序列 ss,每个操作都是上述操作中的一个,求 mm 次操作后,最终的矩阵 AA。

输入格式

第一行两个整数 n,mn, m,表示方阵 AA 的大小和操作次数。

接下来 nn 行,第 ii 行有 nn 个数,第 jj 个数表示 Ai,jA_{i,j} 的值。

最后一行为一个长度为 mm 的字符串 ss,第 ii 个字符为 R,L,D,U,I,C 其中的一个,表示第 ii 次操作。

输出格式

输出 nn 行,第 ii 行有 nn 个整数,第 jj 个整数表示 mm 次操作后,最终的矩阵 Ai,jA_{i,j} 的值。

样例

3 2
1 2 3
2 3 1
3 1 2
DR
2 3 1
3 1 2
1 2 3
3 1
1 2 3
2 3 1
3 1 2
I
1 2 3
3 1 2
2 3 1
见附加文件 mat3.in
见附加文件 mat3.out

数据范围

对于所有数据,1≤n≤1031\le n\le 10^3,1≤m≤1051\le m\le 10^5,Ai,∗,A∗,jA_{i,*},A_{*,j} 是一个长度为 nn 的排列。

详细测试点及附加限制如下表所示:

测试点编号 限制
1∼21\sim 2 n≤10n\le 10
3∼63\sim 6 si∈{R,L,D,U}s_i\in\{\text{R,L,D,U}\}
7∼107\sim1 0 si∈{I,C}s_i\in\{\text{I,C}\}
11∼2011\sim 20