Shifting a Matrix

You are given an $N \times N$ matrix $A$ whose entries start at $A_{i,j} = (i-1)N + j$, where $A_{i,j}$ is the entry in row $i$ and column $j$. Rows and columns are numbered from 1.

Four shift operations act on the matrix.

• Left shift with $i$ rotates row $i$ one step to the left: the old $A_{i,k}$ becomes the new $A_{i,k-1}$ for $2 \le k \le N$, and the old $A_{i,1}$ becomes the new $A_{i,N}$.
• Right shift with $i$ rotates row $i$ one step to the right: the old $A_{i,k}$ becomes the new $A_{i,k+1}$ for $1 \le k \le N-1$, and the old $A_{i,N}$ becomes the new $A_{i,1}$.
• Up shift with $j$ rotates column $j$ one step up: the old $A_{k,j}$ becomes the new $A_{k-1,j}$ for $2 \le k \le N$, and the old $A_{1,j}$ becomes the new $A_{N,j}$.
• Down shift with $j$ rotates column $j$ one step down: the old $A_{k,j}$ becomes the new $A_{k+1,j}$ for $1 \le k \le N-1$, and the old $A_{N,j}$ becomes the new $A_{1,j}$.

An operation sequence is given as one string and you apply its operations from left to right. The letters 'L', 'R', 'U', and 'D' name the left, right, up, and down shifts, and the number right after a letter is the row or column to shift, so "R25" is a right shift with 25. The notation also supports repetition. A sequence wrapped in parentheses and followed by a number $m$ repeats exactly $m$ times, so "(L1R2)10" repeats the pair of a left shift with 1 and a right shift with 2, in that order, 10 times.

Every operation sequence follows this grammar:

<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, compute the $N \times N$ matrix left after the whole sequence.

The input is a single test case in this format:

N L
S

The first line contains two integers $N$ and $L$. $N$ ($1 \le N \le 100$) is the size of the matrix and $L$ ($2 \le L \le 1000$) is the length of the string on the second line. The second line contains the operation sequence $S$, which follows the grammar above. Every row number and column number in $S$ is at least 1 and at most $N$, and every repetition count is at least 1 and at most $10^9$.

Print $N$ lines. The $i$-th line holds the $N$ integers of row $i$ of $A$ after the operations, separated by single spaces.