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> vi;

int n,l;
string s;
vi id;

vi composition(vi a, vi b){
  for(int i=0;i<n*n;i++){
    b[i] = a[b[i]];
  }
  return b;
}

vi pow(vi a, int x){
  vi res = id;
  while(x){
    if(x&1)res = composition(res,a);
    a = composition(a,a);
    x >>= 1;
  }
  return res;
}

int number(int &p){
  int res = 0;
  while(p<l && isdigit(s[p])){
    res = res * 10 + (int)(s[p++]-'0');
  }
  return res;
}

vi operation(int &p){
  if(s[p] == 'L'){
    int i = number(++p) - 1;
    vi res = id;
    for(int k=0;k<n;k++)res[i*n+k] = i*n+(k+1)%n;
    return res;
  }
  else if(s[p] == 'R'){
    int i = number(++p) - 1;
    vi res = id;
    for(int k=0;k<n;k++)res[i*n+k] = i*n+(k+n-1)%n;
    return res;
  }
  else if(s[p] == 'U'){
    int j = number(++p) - 1;
    vi res = id;
    for(int k=0;k<n;k++)res[k*n+j] = (k+1)%n*n+j;
    return res;
  }
  else if(s[p] == 'D'){
    int j = number(++p) - 1;
    vi res = id;
    for(int k=0;k<n;k++)res[k*n+j] = (k+n-1)%n*n+j;
    return res;
  }
  assert(true);
}

vi sequence(int &p){
  if(p==l || s[p] == ')'){
    return id;
  }

  vi a;
  if(s[p] == '('){
    vi t = sequence(++p);
    int x = number(++p);
    a = pow(t,x);
  }else{
    a = operation(p);
  }
  vi b = sequence(p);
  
  return composition(a,b);
}

int main(){
  cin >> n >> l >> s;
  
  id.resize(n*n);
  for(int i=0;i<n*n;i++)id[i] = i;

  int p = 0;
  vi ans = sequence(p);
  
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++) cout << ans[i*n+j] + 1 << " \n"[j==n-1];
  }
}