Example

Input

3 2
R1


Output

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

vector<int> rights;
int n, l, m;
string s;

vector<int> conv(vector<int> a, vector<int> b) {
    vector<int> ret(m);
    for (int i = 0; i < m; ++i) {
        ret[i] = a[b[i]];
    }
    return ret;
}

vector<int> dubl(vector<int> a, int times) {
    vector<int> ret(m);
    vector<int> dbs(m);
    for (int i = 0; i < m; ++i) {
        ret[i] = i;
        dbs[i] = a[i];
    }
    for (int i = 0; (1 << i) <= times; ++i) {
        if ((times >> i) & 1) {
            ret = conv(ret, dbs);
        }
        dbs = conv(dbs, dbs);
    }
    return ret;
}

vector<int> dfs(int lef, int rig) {
    vector<int> ret(m);
    for (int i = 0; i < m; ++i) {
        ret[i] = i;
    }
    if (rights[lef] < rig) {
        int p = lef;
        while (p < rig) {
            ret = conv(ret, dfs(p, rights[p]));
            p = rights[p];
        }
        return ret;
    }
    if (s[lef] == '(') {
        int j = rig - 1;
        for (; '0' <= s[j] && s[j] <= '9'; --j);
        int times = 0;
        for (int i = j + 1; i < rig; ++i) {
            times = times * 10 + s[i] - '0';
        }
        return dubl(dfs(lef + 1, j), times);
    }
    int idx = 0;
    for (int i = lef + 1; i < rig; ++i) {
        idx = idx * 10 + s[i] - '0';
    }
    --idx;
    if (s[lef] == 'R') {
        for (int i = 0; i < n; ++i) {
            --ret[idx * n + i];
        }
        ret[idx * n] += n;
    }
    if (s[lef] == 'L') {
        for (int i = 0; i < n; ++i) {
            ++ret[idx * n + i];
        }
        ret[idx * n + n - 1] -= n;
    }
    if (s[lef] == 'D') {
        for (int i = 0; i < n; ++i) {
            ret[i * n + idx] -= n;
        }
        ret[idx] += n * n;
    }
    if (s[lef] == 'U') {
        for (int i = 0; i < n; ++i) {
            ret[i * n + idx] += n;
        }
        ret[(n - 1) * n + idx] -= n * n;
    }
    return ret;
}


int main() {
    cin >> n >> l >> s;
    m = n * n;
    rights.resize(l, -1);
    for (int i = 0; i < l; ++i) {
        if (('0' <= s[i] && s[i] <= '9') || s[i] == ')') continue;
        if (s[i] == '(') {
            int dep = 0;
            for (int j = i; j < l; ++j) {
                if (s[j] == '(') ++dep;
                if (s[j] == ')') --dep;

                if (dep == 0) {
                    for (int k = j + 1; k < l; ++k) {
                        if ('0' > s[k] || '9' < s[k]) {
                            rights[i] = k;
                            goto A;
                        }
                    }
                    rights[i] = l;
                }
            }
        }
        else {
            for (int j = i + 1; j < l; ++j) {
                if ('0' > s[j] || '9' < s[j]) {
                    rights[i] = j;
                    goto A;
                }
            }
            rights[i] = l;
        }
        A:
        continue;
    }
    vector<int> ret = dfs(0, l);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int k = i * n + j;
            if (j < n - 1)
                cout << ret[k] + 1 << " ";
            else
                cout << ret[k] + 1 << "\n";
        }
    }

    return 0;
}