题目描述

本题来自 Codeforces Round #691 Latin Square。

你现在有一个 $n \times n$ 的矩阵 $A$，$A$ 的行列编号均从 $1$ 开始，到 $n$ 结束，其中 $A_{i,j}$ 表示 $A$ 第 $i$ 行到 $j$ 行的值。特别地，$A$ 的每一列和每一行都是一个长度为 $n$ 的排列。

现有如下对 $A$ 的操作：

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

对于长度为 $n$ 的排列 $p$ 而言置换求逆指得到另一个排列 $q$ 满足 $q_{p_i} = i$。

现在长度为 $m$ 操作的操作序列 $s$，每个操作都是上述操作中的一个，求 $m$ 次操作后，最终的矩阵 $A$。

输入格式

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

接下来 $n$ 行，第 $i$ 行有 $n$ 个数，第 $j$ 个数表示 $A_{i,j}$ 的值。

最后一行为一个长度为 $m$ 的字符串 $s$，第 $i$ 个字符为 R，L，D，U，I，C 其中的一个，表示第 $i$ 次操作。

输出格式

输出 $n$ 行，第 $i$ 行有 $n$ 个整数，第 $j$ 个整数表示 $m$ 次操作后，最终的矩阵 $A_{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\le n\le 10^3$，$1\le m\le 10^5$，$A_{i,*},A_{*,j}$ 是一个长度为 $n$ 的排列。

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