Example

Input

3 2
R1


Output

3 1 2
4 5 6
7 8 9
#include <algorithm>
#include <iostream>
#include <vector>
#include <cctype>
#include <numeric>
using namespace std;

int n;
string s;

vector<int> operator*(const vector<int> &f, const vector<int> &g) {
    vector<int> h(n * n);
    for (int i = 0; i < n * n; i++) h[i] = g[f[i]];
    return h;
}
vector<int> operator^(vector<int> f, int n_) {
    vector<int> res(n * n);
    iota(res.begin(), res.end(), 0);
    while (n_ > 0) {
        if (n_ & 1) res = res * f;
        f = f * f;
        n_ >>= 1;
    }
    return res;
}
vector<int> inv(vector<int> f) {
    vector<int> res(n * n);
    for (int i = 0; i < n * n; i++) res[f[i]] = i;
    return res;
}

vector<int> sequence(int &idx);
vector<int> repetition(int &idx);
vector<int> operation(int &idx);
int number(int &idx);

// <sequence> := <sequence><repetition> | <sequence><operation> |
//               <repetition> | <operation>
vector<int> sequence(int &idx) {
    vector<int> f(n * n);
    iota(f.begin(), f.end(), 0);
    while (idx < s.length() && s[idx] != ')') {
        if (s[idx] == '(') {
            f = f * repetition(idx);
        } else {
            f = f * operation(idx);
        }
    }
    return f;
}

// <repetition> := '('<sequence>')'<number>
vector<int> repetition(int &idx) {
    idx++;      // skip '('
    vector<int> f = sequence(idx);
    idx++;      // skip ')'
    int num = number(idx);
    return f ^ num;
}

// <operation> := <shift><number>
// <shift> := 'L' | 'R' | 'U' | 'D'
vector<int> operation(int &idx) {
    char op = s[idx++];
    int num = number(idx); num--;
    vector<int> f(n * n);
    iota(f.begin(), f.end(), 0);
    if (op == 'L') {
        int tmp = f[num * n + n - 1];
        for (int i = n - 1; i > 0; i--) f[num * n + i] = f[num * n + i - 1];
        f[num * n + 0] = tmp;
    } else if (op == 'R') {
        int tmp = f[num * n + 0];
        for (int i = 0; i < n - 1; i++) f[num * n + i] = f[num * n + i + 1];
        f[num * n + n - 1] = tmp;
    } else if (op == 'U') {
        int tmp = f[(n - 1) * n + num];
        for (int i = n - 1; i > 0; i--) f[i * n + num] = f[(i - 1) * n + num];
        f[0 * n + num] = tmp;
    } else if (op == 'D') {
        int tmp = f[0 * n + num];
        for (int i = 0; i < n - 1; i++) f[i * n + num] = f[(i + 1) * n + num];
        f[(n - 1) * n + num] = tmp;
    }
    return f;
}

// <number> := <nonzero_digit> | <number><digit>
// <digit> := '0' | <nonzero_digit>
// <nonzero_digit> := '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
int number(int &idx) {
    int res = 0;
    while (idx < s.length() && isdigit(s[idx])) {
        res = res * 10 + s[idx++] - '0';
    }
    return res;
}

int main() {
    int _; cin >> n >> _;
    cin >> s;
    int idx = 0;
    vector<int> res = inv(sequence(idx));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << res[i * n + j] + 1 << " \n"[j == n - 1];
        }
    }
    return 0;
}
