Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Shifting a Matrix

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.

Input

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

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.

Sample Input 1

3 2
R1

Output for the Sample Input 1

3 1 2
4 5 6
7 8 9

Sample Input 2

3 7
(U2)300

Output for the Sample Input 2

1 2 3
4 5 6
7 8 9

Sample Input 3

3 7
(R1D1)3

Output for the Sample Input 3

3 4 7
1 5 6
2 8 9



Sample input:
3 2
R1


Sample output:
3 1 2
4 5 6
7 8 9

Submission status: Accepted

Solution code:
from string import digits
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N, L = map(int, readline().split())
    S = readline().strip()
    *I, = range(N*N)
    LRUD = "LRUD"
    FS = [[], [], [], []]
    for i in range(N):
        base = N*i
        F = I[:]
        for j in range(N):
            F[base+j] = base+((j+1) % N)
        FS[0].append(F)
        F = I[:]
        for j in range(N):
            F[base+j] = base+((j-1) % N)
        FS[1].append(F)

        base = i
        F = I[:]
        for j in range(N):
            F[base+N*j] = base+((j+1) % N)*N
        FS[2].append(F)
        F = I[:]
        for j in range(N):
            F[base+N*j] = base+((j-1) % N)*N
        FS[3].append(F)

    def fast_pow(f, n):
        r = I[:]
        while n:
            if n & 1:
                r = [f[x] for x in r]
            f = [f[x] for x in f]
            n >>= 1
        return r

    S += "$"
    cur = 0
    def number():
        nonlocal cur
        r = 0
        while S[cur] in digits:
            r = 10*r + int(S[cur])
            cur += 1 # digits
        return r

    def expr():
        nonlocal cur
        f0 = I[:]
        while 1:
            if S[cur] == '(':
                cur += 1 # '('
                r1 = expr()
                cur += 1 # ')'
                num = number()
                f1 = fast_pow(r1, num)
            elif S[cur] in LRUD:
                t = LRUD.index(S[cur])
                cur += 1 # LRUD
                num = number()
                f1 = FS[t][num-1]
            else:
                break
            f0 = [f0[x] for x in f1]
        return f0

    f = expr()
    ans = [str(x+1) for x in f]
    for i in range(N):
        write(" ".join(ans[i*N:i*N+N]))
        write("\n")
solve()