You are given $N \times N$ matrix $A$ initialized with $A_{i,j} = (i - 1)N + j$, where $A_{i,j}$ is the entry of the $i$-th row and the $j$-th column of $A$. Note that $i$ and $j$ are 1-based.

You are also given an operation sequence which consists of the four types of shift operations: left, right, up, and down shifts. More precisely, these operations are defined as follows:

- Left shift with $i$: circular shift of the $i$-th row to the left, i.e., setting previous $A_{i,k}$ to new $A_{i,k-1}$ for $2 \leq k \leq N$, and previous $A_{i,1}$ to new $A_{i,N}$.
- Right shift with $i$: circular shift of the $i$-th row to the right, i.e., setting previous $A_{i,k}$ to new $A_{i,k+1}$ for $1 \leq k \leq N - 1$, and previous $A_{i,N}$ to new $A_{i,1}$.
- Up shift with $j$: circular shift of the $j$-th column to the above, i.e., setting previous $A_{k,j}$ to new $A_{k-1,j}$ for $2 \leq k \leq N$, and previous $A_{1,j}$ to new $A_{N,j}$.
- Down shift with $j$: circular shift of the $j$-th column to the below, i.e., setting previous $A_{k,j}$ to new $A_{k+1,j}$ for $1 \leq k \leq N - 1$, and previous $A_{N,j}$ to new $A_{1,j}$.

An operation sequence is given as a string. You have to apply operations to a given matrix from left to right in a given string. Left, right, up, and down shifts are referred as 'L', 'R', 'U', and 'D' respectively in a string, and the following number indicates the row/column to be shifted. For example, "R25" means we should perform right shift with 25. In addition, the notion supports repetition of operation sequences. An operation sequence surrounded by a pair of parentheses must be repeated exactly $m$ times, where $m$ is the number following the close parenthesis. For example, "(L1R2)10" means we should repeat exactly 10 times the set of the two operations: left shift with 1 and right shift with 2 in this order.

Given operation sequences are guaranteed to follow the following 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'

Given $N$ and an operation sequence as a string, make a program to compute the $N \times N$ matrix after operations indicated by the operation sequence.

The input consists of a single test case. The test case is formatted as follows.

$N$ $L$

$S$

The first line contains two integers $N$ and $L$, where $N$ ($1 \leq N \leq 100$) is the size of the given matrix and $L$ ($2 \leq L \leq 1,000$) is the length of the following string. The second line contains a string $S$ representing the given operation sequence. You can assume that $S$ follows the above BNF. You can also assume numbers representing rows and columns are no less than 1 and no more than $N$, and the number of each repetition is no less than 1 and no more than $10^9$ in the given string.

Output the matrix after the operations in $N$ lines, where the $i$-th line contains single-space separated $N$ integers representing the $i$-th row of $A$ after the operations.

3 2 R1

3 1 2 4 5 6 7 8 9

3 7 (U2)300

1 2 3 4 5 6 7 8 9

3 7 (R1D1)3

3 4 7 1 5 6 2 8 9

Source: JAG Practice Contest for ACM-ICPC Asia Regional 2015
, Japan, 2015-11-22

http://jag-icpc.org/

http://jag2015autumn.contest.atcoder.jp/

http://jag-icpc.org/

http://jag2015autumn.contest.atcoder.jp/