Example

Input

3 2
R1


Output

3 1 2
4 5 6
7 8 9
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vec;
int n,len,pos;
string s;
 
vec mul(vec a,vec b){
  vec res(n*n);
  for(int i=0;i<n*n;i++)res[i]=b[a[i]];
  return res;
}
 
vec mpow(vec a,int t){
  if(t==0){
    vec res(n*n);
    for(int i=0;i<n*n;i++)res[i]=i;
    return res;
  }  
  vec res=mpow(mul(a,a),t/2);
  if(t%2==1)res=mul(res,a);
  return res;
}
 
vec calc();
 
vec getNum(){
 
  if(s[pos]=='('){
    pos++;
    vec res=calc();
    
    int num=0;
    while(pos<len&&'0'<=s[pos]&&s[pos]<='9')
      num=num*10+s[pos++]-'0';
    vec Ra= mpow(res,num);
    return Ra;
  }
  
  char ch=s[pos++];
  int num=0;
  while(pos<len&&'0'<=s[pos]&&s[pos]<='9'){
    num=num*10+s[pos]-'0';
    pos++;
  }
  
  vec res(n*n);  
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      int ni=i,nj=j;
      if(ch=='D'&&j+1==num){
        ni=(i+1)%n;
        nj=j;
      }else if(ch=='L'&&i+1==num){
        ni=i;
        nj=(j+n-1)%n;
      }else if(ch=='U'&&j+1==num){
        ni=(i+n-1)%n;
        nj=j;
      }else if(ch=='R'&&i+1==num){
        ni=i;
        nj=(j+1)%n;
      }
      res[i*n+j]=ni*n+nj;
    }
  }
  return res;
}
 
int C=0;
vec calc(){
  vec res=getNum();
  
  while(pos<len){
    if(s[pos]==')'){
      pos++;
      break;
    }
    vec num=getNum();
    res=mul(res,num);
  }
  return res;
}
 
int main() {
  while(cin>>n>>len) {
    cin>>s;
    pos=0;
    vec ans(n*n),ans2=calc();
    for(int i=0;i<n*n;i++){
      ans[ ans2[i]]=i;
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        if(j)cout<<' ';
        cout<<ans[i*n+j]+1;
      }
      cout<<endl;
    }
  }
  return 0;
}