Example

Input

3 2
R1


Output

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

using Vec=vector<int>;
using Mat=vector<vector<int>>;
int n,l;
Mat E(){
    Mat res(n,Vec(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            res[i][j]=i*n+j;
        }
    }
    return res;
}
Mat merge(Mat lhs,Mat rhs){
    Mat res(n,Vec(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int row=rhs[i][j]/n;
            int col=rhs[i][j]%n;
            res[i][j]=lhs[row][col];
        }
    }
    return res;
}
int getNum(int &p,string s){
    int res=0;
    while(p<s.size() && isdigit(s[p])){
        res*=10;
        res+=s[p]-'0';
        p++;
    }
    return res;
}
Mat powM(Mat mat,int k){
    Mat res=E();
    while(k){
        if(k&1) res=merge(res,mat);
        k>>=1;
        mat=merge(mat,mat);
    }
    return res;
}
Mat prim(int &p,string s){
    if(s[p]=='L' || s[p]=='R'){
        char op=s[p++];
        Mat res=E();
        int k=getNum(p,s);
        k--;
        int diff=(op=='L' ? n-1 : 1);
        for(int j=0;j<n;j++) res[k][(j+diff)%n]=k*n+j%n;
        return res;
    }
    if(s[p]=='U' || s[p]=='D'){
        char op=s[p++];
        Mat res=E();
        int k=getNum(p,s);
        k--;
        int diff=(op=='U' ? n-1 : 1);
        for(int i=0;i<n;i++) res[(i+diff)%n][k]=i*n+k;
        return res;
    }
    assert(false);
}

Mat seq(int &p,string s){
    Mat res=E();
    while(p<s.size() && s[p]!=')'){
        Mat ret;
        if(s[p]=='('){
            p++;
            ret=seq(p,s);
            assert(s[p++]==')');
            int num=getNum(p,s);
            ret=powM(ret,num);
        }
        else{
            ret=prim(p,s);
        }
        res=merge(res,ret);
    }
    return res;
}

void output(Mat mat,ostream& out){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            out<<mat[i][j]+1<<(j+1==n ? "\n" : " ");
        }
    }
}
int main(){
    cin>>n>>l;
    string s;
    cin>>s;
    int p=0;
    Mat res=seq(p,s);
    output(res,cout);
    return 0;
}

