Example

Input

3 2
R1


Output

3 1 2
4 5 6
7 8 9
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int, int> pii;
vector<vector<pii>> unit;

int getint(int &p, string s){
    int res=0;
    while(p<(int)s.length() && '0'<=s[p] && s[p]<='9'){
        res *= 10;
        res += s[p]-'0';
        p++;
    }
    return res;
}
vector<vector<pii>> compose(vector<vector<pii>> &a, vector<vector<pii>> &b){
    int n = a.size();
    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] = b[a[i][j].first][a[i][j].second];
        }
    }
    return res;
}
vector<vector<pii>> shiftmap(int &p, string s){
    auto res = unit;
    int n = unit.size();
    while(p<(int)s.length() && s[p]!=')'){
        vector<vector<pii>> ch = unit;
        if(s[p] == '('){
            ch = shiftmap(++p, s);
            int rep = getint(++p, s);
            auto curr = unit;
            for(int i=31; i>=0; i--){
                curr = compose(curr, curr);
                if(rep>>i&1){
                    curr = compose(curr, ch);
                }
            }
            ch = curr;
        }else if(s[p] == 'L'){
            int i = getint(++p, s) - 1;
            for(int j=0; j<n; j++){
                ch[i][j] = pii(i, (j+n-1)%n);
            }
        }else if(s[p] == 'R'){
            int i = getint(++p, s) - 1;
            for(int j=0; j<n; j++){
                ch[i][j] = pii(i, (j+1)%n);
            }
        }else if(s[p] == 'U'){
            int j = getint(++p, s) - 1;
            for(int i=0; i<n; i++){
                ch[i][j] = pii((i+n-1)%n, j);
            }
        }else if(s[p] == 'D'){
            int j = getint(++p, s) - 1;
            for(int i=0; i<n; i++){
                ch[i][j] = pii((i+1)%n, j);
            }
        }
        res = compose(res, ch);
    }
    return res;
}

int main(){
    int n,l;
    string s;
    cin >> n >> l >> s;
    unit = vector<vector<pii>>(n);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            unit[i].emplace_back(i, j);
        }
    }
    int p=0;
    auto shift = shiftmap(p, s);
    vector<vector<int>> ans(n,vector<int>(n));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            ans[shift[i][j].first][shift[i][j].second] = i*n +j +1;
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n-1; j++){
            cout << ans[i][j] << " ";
        }
        cout << ans[i][n-1] << endl;
    }
    return 0;
}

