Example

Input

3 2
R1


Output

3 1 2
4 5 6
7 8 9
#include <iostream>
#include <numeric>
#include <vector>
#include <string>
#include <cassert>

struct Mat {
    static int n;
    std::vector<int> mat;

    Mat(char d = '$', int x = 0) : mat(n * n) {
        std::iota(mat.begin(), mat.end(), 0);

        if (d == 'L') {
            int tmp = mat[n * x + (n - 1)];
            for (int i = n - 1; i > 0; --i) {
                mat[n * x + i] = mat[n * x + (i - 1)];
            }
            mat[n * x + 0] = tmp;

        } else if (d == 'R') {
            int tmp = mat[n * x + 0];
            for (int i = 0; i < n - 1; ++i) {
                mat[n * x + i] = mat[n * x + (i + 1)];
            }
            mat[n * x + (n - 1)] = tmp;

        } else if (d == 'U') {
            int tmp = mat[n * (n - 1) + x];
            for (int i = n - 1; i > 0; --i) {
                mat[n * i + x] = mat[n * (i - 1) + x];
            }
            mat[n * 0 + x] = tmp;

        } else if (d == 'D') {
            int tmp = mat[n * 0 + x];
            for (int i = 0; i < n - 1; ++i) {
                mat[n * i + x] = mat[n * (i + 1) + x];
            }
            mat[n * (n - 1) + x] = tmp;
        }
    }

    Mat operator*(const Mat& m) const {
        auto ret = Mat();
        for (int i = 0; i < n * n; ++i) {
            ret.mat[i] = m.mat[mat[i]];
        }
        return ret;
    }

    Mat pow(int n) const {
        auto ret = Mat();
        auto b = *this;
        while (n > 0) {
            if (n & 1) ret = ret * b;
            n >>= 1;
            b = b * b;
        }
        return ret;
    }
};

int Mat::n;

struct Parser {
    std::string s;
    int i;

    Mat seq() {
        Mat ret;
        while (i < (int)s.length() && s[i] != ')') {
            if (s[i] == '(') {
                ++i;
                auto m = seq();

                assert(s[i] == ')');
                ++i;

                int e = num();
                ret = ret * m.pow(e);
            } else {
                assert(std::isupper(s[i]));
                char c = s[i];
                ++i;
                int x = num() - 1;

                ret = ret * Mat(c, x);
            }
        }
        return ret;
    }

    int num() {
        int ret = 0;
        while (i < (int)s.length() && std::isdigit(s[i])) {
            int d = s[i] - '0';
            ret = ret * 10 + d;
            ++i;
        }
        return ret;
    }

    Mat parse(const std::string& _s) {
        s = _s;
        i = 0;
        return seq();
    }
};

void solve() {
    int n, l;
    std::string s;
    std::cin >> n >> l >> s;
    Mat::n = n;

    Parser parser;
    auto m = parser.parse(s);

    std::vector<int> ans(n * n);
    for (int i = 0; i < n * n; ++i) {
        ans[m.mat[i]] = i;
    }

    for (int i = 0; i < n * n; ++i) {
        std::cout << ans[i] + 1 << " \n"[i % n == n - 1];
    }
}

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}

