Example

Input

3 2
R1


Output

3 1 2
4 5 6
7 8 9
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
typedef vector<int> V;
typedef vector<V> VV;

int n,m,PRE[11111],X[1111];
string s;

VV init(){
    VV v(n,V(n));
    r(i,n)r(j,n)v[i][j]=i*n+j+1;
    return v;
}
inline void MUL(VV &a,VV &b){r(i,n)r(j,n)a[i][j]=b[PRE[a[i][j]]/n][PRE[a[i][j]]%n];}
inline void U(VV &a,int x){r(i,n-1)swap(a[i][x-1],a[i+1][x-1]);}
inline void D(VV &a,int x){r(i,n-1)swap(a[n-i-1][x-1],a[n-i-2][x-1]);}
inline void R(VV &a,int x){r(i,n-1)swap(a[x-1][n-i-1],a[x-1][n-i-2]);}
inline void L(VV &a,int x){r(i,n-1)swap(a[x-1][i],a[x-1][i+1]);}

inline void POW(VV &a,int x){ x--;
    VV v[30];
    v[0]=a;
    r(i,29){
        v[i+1]=v[i];
        MUL(v[i+1],v[i]);
    }
    r(i,30)if((1<<i)&x)MUL(a,v[i]);
}

inline VV dfs(int l,int r){
    VV res=init();
    for(int i=l;i<=r;i++){
        VV ret=init();
        if(s[i]=='('){
            int t=i,cc=1;
            i=X[i];
            ret=dfs(t+1,i-1);
            int p=0; i++;
            while(isdigit(s[i]))p=p*10+(s[i]-'0'),i++;
            POW(ret,p);
        }
        else if(isalpha(s[i])){
            int t=i,p=0; i++;
            while(isdigit(s[i]))p=p*10+(s[i]-'0'),i++;
            if(s[t]=='U')U(ret,p);
            if(s[t]=='D')D(ret,p);
            if(s[t]=='R')R(ret,p);
            if(s[t]=='L')L(ret,p);
        }
        MUL(ret,res);
        res=ret;
        i--;
    }
    return res;
}


int main(){
    r(i,11111)PRE[i]=i-1;
    cin>>n>>m>>s;s+='@';
    stack<int>st;
    r(i,m){
        if(s[i]=='(')st.push(i);
        if(s[i]==')')X[st.top()]=i,st.pop();
    }
    VV ans=dfs(0,m-1);
    r(i,n){
        r(j,n){
            if(j)cout<<' ';
            cout<<ans[i][j];
        }
        cout<<endl;
    }
}
