Example

Input

3 2
R1


Output

3 1 2
4 5 6
7 8 9
#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;
typedef long long ll;
#define int long long
string s;
int n,p;
vector<vector<int> > a;

vector<vector<int> > I;

set<char> st={'L','R','U','D'};
set<char> st2={'0','1','2','3','4','5','6','7','8','9'};
vector<vector<int> > calc(vector<vector<int> > x,vector<vector<int> > y){
    vector<pair<int,int> > p(n*n+1);
    vector<vector<int> > ans(n,vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            p[y[i][j]] = make_pair(i,j);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            ans[p[i*n+j+1].first][p[i*n+j+1].second] = x[i][j];
            //cerr << p[i*n+j+1].first << " " <<p[i*n+j+1].second << endl;
        }
    }
    return ans;
}
vector<vector<int> > saiki(vector<vector<int> > x,int c){
    if(c==0){
        return I;
    }
    if(c==1){
        return x;
    }
    if(c%2==0){
        vector<vector<int> > ss = saiki(x,c/2);
        ss = calc(ss,ss);
        return ss;
    }else{
        vector<vector<int> > ss = saiki(x,c/2);
        ss = calc(ss,ss);
        ss = calc(x,ss);
        return ss;
    }
}

vector<vector<int> > sequence(int l,int r){
    vector<vector<int> > v(n,vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            v[i][j] = i*n+j+1;
        }
    }
    if(l>r)return v;
    if(st.count(s[l])==1){
        int ind = l;
        int c = 0;
        for(int i=l+1;i<=r;i++){
            if(st2.count(s[i])==1){
                ind = i;
                c *=10;
                c += (int)(s[i]-'0');
            }else{
                break;
            }
        }
        c--;
        if(s[l]=='L'){
            int tmp =v[c][0];
            for(int k=0;k<n-1;k++){
                v[c][k] = v[c][k+1];
            }
            v[c][n-1] = tmp;
        }
        if(s[l]=='R'){
            int tmp =v[c][n-1];
            for(int k=n-1;k>0;k--){
                v[c][k] = v[c][k-1];
            }
            v[c][0] = tmp;
        }
        if(s[l]=='U'){
            int tmp =v[0][c];
            for(int k=0;k<n-1;k++){
                v[k][c] = v[k+1][c];
            }
            v[n-1][c] = tmp;
        }
        if(s[l]=='D'){
            int tmp =v[n-1][c];
            for(int k=n-1;k>0;k--){
                v[k][c] = v[k-1][c];
            }
            v[0][c] = tmp;
        }
        vector<vector<int > >v2 = sequence(ind+1,r);
        return calc(v,v2);
    }else{
        int dep = 0;
        int ind = l;
        for(int i=l;i<=r;i++){
            if(s[i]=='('){
                dep++;
            }else if(s[i]==')'){
                dep--;
            }
            if(dep==0){
                ind = i;
                break;
            }
        }
        int c = 0;
        int ind2 = ind+1;
        for(int i=ind+1;i<=r;i++){
            if(st2.count(s[i])==1){
                ind2 = i;
                c *=10;
                c += s[i]-'0';

            }else{
                break;
            }
        }
        vector<vector<ll> >v = sequence(l+1,ind-1);
        v = saiki(v,c);
        //cerr << ind2 << endl;
        vector<vector<ll> >v2 = sequence(ind2+1,r);
        
        return calc(v,v2);
    }
}


signed main(){
    
    cin >> n >> p;
    a.resize(n);
    I.resize(n);
    for(int i=0;i<n;i++){
        a[i].resize(n);
        I[i].resize(n);
        for(int j=0;j<n;j++){
            a[i][j] = i*n+j+1;
            I[i][j] = i*n+j+1;
            //cerr << i << " " << j << " " <<a[i][j] << endl;
        }
    }
    cin >> s;
    
    vector<vector<ll> > ans =sequence(0,p-1);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout << ans[i][j];
            if(j!=n-1)cout << " ";
        }
        cout << endl;
    }
    return 0;
}
