Example

Input

3 2
R1


Output

3 1 2
4 5 6
7 8 9
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int N;

vector<vector<pii>> make_initial() {
    vector<vector<pii>> res(N, vector<pii>(N));
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            res[i][j] = make_pair(i, j);
        }
    }
    return res;
}

vector<vector<pii>> eval(vector<vector<pii>> const& A, vector<vector<pii>> const& x) {
    auto res = A;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            res[i][j] = A[x[i][j].first][x[i][j].second];
        }
    }
    return res;
}

vector<vector<pii>> sequence(string const& s, int& p);
vector<vector<pii>> repetition(string const& s, int& p);
vector<vector<pii>> operation(string const& s, int& p);
int number(string const& s, int& p);

vector<vector<pii>> sequence(string const& s, int& p) {
    auto res = make_initial();
    while(p < s.size() && (s[p] == '(' || isalpha(s[p]))) {
        vector<vector<pii>> f;
        if(s[p] == '(') {
            f = repetition(s, p);
        } else if(isalpha(s[p])) {
            f = operation(s, p);
        } else {
            cout << "error pos: " << p << endl;
            assert(false); // error
        }
        res = eval(res, f);
    }
    return res;
}

vector<vector<pii>> repetition(string const& s, int& p) {
    auto x = sequence(s, ++p);
    ++p;
    assert(isdigit(s[p]));
    int n = number(s, p);
    auto res = make_initial();
    while(n > 0) {
        if(n & 1) {
            res = eval(res, x);
        }
        x = eval(x, x);
        n >>= 1;
    }
    return res;
}

vector<vector<pii>> operation(string const& s, int& p) {
    auto res = make_initial();
    char op = s[p++];
    int i = number(s, p) - 1;
    if(op == 'L') {
        for(int j = 0; j < N; ++j) {
            res[i][j].second = (j + 1) % N;
        }
    } else if(op == 'R') {
        for(int j = 0; j < N; ++j) {
            res[i][j].second = (j - 1 + N) % N;
        }
    } else if(op == 'U') {
        for(int j = 0; j < N; ++j) {
            res[j][i].first = (j + 1) % N;
        }
    } else if(op == 'D') {
        for(int j = 0; j < N; ++j) {
            res[j][i].first = (j - 1 + N) % N;
        }
    } else {
        assert(false);
    }
    return res;
}

int number(string const& s, int& p) {
    int res = 0;
    while(isdigit(s[p])) {
        res *= 10;
        res += (s[p++] - '0');
    }
    return res;
}

int main() {
    int L;
    string S;
    cin >> N >> L >> S;
    int p = 0;
    auto ans = sequence(S, p);
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            cout << (ans[i][j].first * N + ans[i][j].second + 1) << " \n"[j + 1 == N];
        }
    }
}
