Example

Input

3 2
R1


Output

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

typedef vector<int> vec;
typedef vector<vec > mat;

typedef pair<int,int> P;

mat bnf();

int N, L, p;
string s;

mat cal(char c, int num){
  
  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 + 1;
  
  num--;
  
  if( c == 'L' ){
    int tmp = res[num][0];
    for(int i=0;i<N-1;i++) res[num][i] = res[num][i+1];
    res[num][N-1] = tmp;
  }
  
  if( c == 'R' ){
    int tmp = res[num][N-1];
    for(int i=N-1;i>0;i--) res[num][i] = res[num][i-1];
    res[num][0] = tmp;
  }
  
  if( c == 'U' ){
    int tmp = res[0][num];
    for(int i=0;i<N-1;i++) res[i][num] = res[i+1][num];
    res[N-1][num] = tmp;
  }
  
  if( c == 'D' ){
    int tmp = res[N-1][num];
    for(int i=N-1;i>0;i--) res[i][num] = res[i-1][num];
    res[0][num] = tmp;
  }

  return res;
}

mat marge1(mat A, mat B){
  
  mat res( N, vec( N ) );
  
  for(int i=0;i<N;i++){
    
    for(int j=0;j<N;j++){
      B[i][j]--;
      res[i][j] = A[B[i][j]/N][B[i][j]%N];
    }
    
  }
  
  return res;
}

mat marge2(mat A, int num){ // doubling
  
  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 + 1;
  
  while(num){
    
    if( num % 2 ) res = marge1( res, A );
    
    A = marge1( A, A );
    
    num /= 2;
  }

  return res;
}


mat get_num(){
  
  if( s[p] == '(' ){
    
    p++;
    
    mat r = bnf();
    
    int num = 0;
    
    while( '0' <= s[p] && s[p] <= '9' ) num = num * 10 + s[p++] - '0';
    
    r = marge2( r, num );
    
    return r;
  }
  
  char c = s[p++];
  
  int num = 0;
  
  while( '0' <= s[p] && s[p] <= '9' ) num = num * 10 + s[p++] - '0';
  
  return cal( c, num );
}

mat bnf(){
  
  mat res = get_num();
  
  while( p < L ){
    
    if( s[p] == ')' ){
      p++;
      break;
    }
    
    mat r = get_num();
    
    res = marge1( res, r );
    
  }
  
  return res;
}

signed main(){
  
  cin>>N>>L;
  
  cin>>s;
  
  mat ans = bnf();
  
  for(int i=0;i<N;i++){
    
    for(int j=0;j<N;j++){
      
      if( j ) cout<<' ';

      cout<<ans[i][j];
      
    }

    cout<<endl;
    
  }
  
  return 0;
}

