You are given N×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.</p>

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 ≤ k ≤ 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 ≤ k ≤ 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 ≤ k ≤ 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 ≤ k ≤ 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×N matrix after operations indicated by the operation sequence.

입력 형식

The input consists of a single test case. The test case is formatted as follows.</p>

N L
S

The first line contains two integers N and L, where N (1 ≤ N ≤ 100) is the size of the given matrix and L (2 ≤ L ≤ 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⁹ 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.

예제 입력 1

3 2
R1

예제 출력 1

3 1 2
4 5 6
7 8 9

예제 입력 2

3 7
(U2)300

예제 출력 2

1 2 3
4 5 6
7 8 9

예제 입력 3

3 7
(R1D1)3

예제 출력 3

3 4 7
1 5 6
2 8 9