Time Limit: 5 sec / Memory Limit: 512 MB
Problem Statement
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