题目描述

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

同时，给定一个操作序列，包括四种类型的移动操作：向左、向右、向上和向下移动。具体操作定义如下：

• 向左移动 $i$ 行：循环将第 $i$ 行向左移动，即将原来的 $A_{i,k}$ 变为新的 $A_{i,k-1}$（对于 $2 \leq k \leq N$），将原来的 $A_{i,1}$ 变为新的 $A_{i,N}$。

• 向右移动 $i$ 行：循环将第 $i$ 行向右移动，即将原来的 $A_{i,k}$ 变为新的 $A_{i,k+1}$（对于 $1 \leq k \leq N-1$），将原来的 $A_{i,N}$ 变为新的 $A_{i,1}$。

• 向上移动 $j$ 列：循环将第 $j$ 列向上移动，即将原来的 $A_{k,j}$ 变为新的 $A_{k-1,j}$（对于 $2 \leq k \leq N$），将原来的 $A_{1,j}$ 变为新的 $A_{N,j}$。

• 向下移动 $j$ 列：循环将第 $j$ 列向下移动，即将原来的 $A_{k,j}$ 变为新的 $A_{k+1,j}$（对于 $1 \leq k \leq N-1$），将原来的 $A_{N,j}$ 变为新的 $A_{1,j}$。

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

给定的操作序列满足以下的 BNF：

<sequence> := <sequence><repetition> | <sequence><operation> | <repetition> | <operation>
<repetition> := '('<sequence>')'<number>
<operation> := <shift><number>
<shift> := 'L' | 'R' | 'U' | 'D'
<number> := <nonzero_digit> |<number><digit>
<digit> := '0' | <nonzero_digit>
<nonzero_digit> := '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'```

给定 $N$ 和一个操作序列的字符串，编写程序计算操作序列下对矩阵 $N \times N$ 的操作后的结果。

* * *

### 输入

输入包含一个测试用例。测试用例的格式如下。

> $N$ $L$  
> $S$

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

### 输出

输出经过操作序列执行后的矩阵，输出为 $N$ 行，每行包含 $N$ 个整数，表示操作后矩阵 $A$ 的第 $i$ 行。

* * *

* * *

### 示例 1

```plain
输入
3 2
R1
输出
3 1 2
4 5 6
7 8 9

示例 2

输入
3 7
(U2)300
输出
1 2 3
4 5 6
7 8 9

示例 3

输入
3 7
(R1D1)3
输出
3 4 7
1 5 6
2 8 9