给定一个 $N \times N$ 的矩阵 $A$，其初始值定义为 $A_{i,j} = (i - 1) \cdot N + j$，其中 $A_{i,j}$ 表示矩阵第 $i$ 行第 $j$ 列的元素。注意 $i$ 和 $j$ 均从 1 开始计数。

你还需要处理一个由四种位移操作组成的操作序列：左移、右移、上移和下移。这些操作定义如下：

• 第 $i$ 行左移：将第 $i$ 行循环左移，即对于 $2 \le k \le N$，将原来的 $A_{i,k}$ 变为新的 $A_{i,k-1}$，并将原来的 $A_{i,1}$ 变为新的 $A_{i,N}$。
• 第 $i$ 行右移：将第 $i$ 行循环右移，即对于 $1 \le k \le N - 1$，将原来的 $A_{i,k}$ 变为新的 $A_{i,k+1}$，并将原来的 $A_{i,N}$ 变为新的 $A_{i,1}$。
• 第 $j$ 列上移：将第 $j$ 列循环上移，即对于 $2 \le k \le N$，将原来的 $A_{k,j}$ 变为新的 $A_{k-1,j}$，并将原来的 $A_{1,j}$ 变为新的 $A_{N,j}$。
• 第 $j$ 列下移：将第 $j$ 列循环下移，即对于 $1 \le k \le N - 1$，将原来的 $A_{k,j}$ 变为新的 $A_{k+1,j}$，并将原来的 $A_{N,j}$ 变为新的 $A_{1,j}$。

操作序列以字符串形式给出。你需要按照字符串中从左到右的顺序对矩阵执行操作。左移、右移、上移和下移在字符串中分别表示为 'L'、'R'、'U' 和 'D'，其后的数字表示要移动的行号或列号。例如，“R25”表示对第 25 行执行右移操作。此外，该表示法支持操作序列的重复。被括号括起来的操作序列必须重复执行 $m$ 次，其中 $m$ 是紧跟在右括号后的数字。例如，“(L1R2)10”表示依次执行“第 1 行左移”和“第 2 行右移”这两项操作，并重复执行 10 次。

给定的操作序列保证符合以下 BNF 范式：

:= | | |

:= ’(’’)’

:=

:= ’L’ | ’R’ | ’U’ | ’D’

:= |

:= ’0’ |

:= ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’

给定 $N$ 和表示操作序列的字符串，请编写程序计算经过这些操作后的 $N \times N$ 矩阵。

输入格式

输入的第一行包含两个整数 $N$ 和 $L$，其中 $N$ ($1 \le N \le 100$) 是给定矩阵的大小，$L$ ($2 \le L \le 1,000$) 是后续字符串的长度。第二行包含一个表示给定操作序列的字符串 $S$。你可以假设 $S$ 符合上述 BNF 范式。你还可以假设字符串中表示行号和列号的数字不小于 1 且不超过 $N$，且每次重复的次数不小于 1 且不超过 $10^9$。

输出格式

输出操作后的矩阵，共 $N$ 行，其中第 $i$ 行包含 $N$ 个由空格分隔的整数，表示操作后矩阵 $A$ 的第 $i$ 行。

样例

样例输入 1

3 2
R1

样例输出 1

3 1 2
4 5 6
7 8 9

样例输入 2

3 7
(U2)300

样例输出 2

1 2 3
4 5 6
7 8 9

样例输入 3

3 7
(R1D1)3

样例输出 3

3 4 7
1 5 6
2 8 9