Example

Input

3 2
R1


Output

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

typedef string::const_iterator state;
typedef vector<vector<int>> my_matrix;
class parse_error{};
my_matrix matrix;
int n,l;
string s;

void consume(state &begin,char expected){
    if(*begin==expected) ++begin;
    else{
        cerr << "Exptected '" << expected << "' but got '" << *begin << "'" << endl;
        cerr << "Rest string is'";
        while(*begin) cerr << *begin++;
        cerr << "'" << endl;
        throw parse_error();
    }
}

void sequence(state&);
void repetition(state&);
void operation(state&);
int number(state&);

void sequence(state &begin){
    while(*begin){
        if(*begin=='(') repetition(begin);
        else if(*begin=='U' or *begin=='D' or *begin=='L' or *begin=='R') operation(begin);
        else break;
    }
}

void repetition(state &begin){
    consume(begin,'(');
    const auto backup1=begin;
    int depth=1;
    while(depth){
        if(*begin=='(') ++depth;
        if(*begin==')') --depth;
        ++begin;
    }
    --begin;
    consume(begin,')');
    int num=number(begin);
    const auto backup2=begin;

    const auto prev_matrix=matrix;
    rep(i,0,n) rep(j,0,n) matrix[i][j]=i*n+j;

    begin=backup1;
    sequence(begin);

    vector<vector<pair<int,int>>> perm(n,vector<pair<int,int>>(n)),v(n,vector<pair<int,int>>(n));
    rep(i,0,n) rep(j,0,n){
        perm[matrix[i][j]/n][matrix[i][j]%n]=make_pair(i,j);
        v[i][j]=make_pair(i,j);
    }

    while(num>0){
        if(num&1) rep(i,0,n) rep(j,0,n) v[i][j]=perm[v[i][j].first][v[i][j].second];
        const auto prev_perm=perm;
        rep(i,0,n) rep(j,0,n) perm[i][j]=prev_perm[perm[i][j].first][perm[i][j].second];
        num>>=1;
    }
    rep(i,0,n) rep(j,0,n) matrix[v[i][j].first][v[i][j].second]=prev_matrix[i][j];

    begin=backup2;
}

void operation(state &begin){
    char d=*begin;
    ++begin;
    int num=number(begin);
    if(d=='L'){
        //rotate(matrix[num-1].begin(),matrix[num-1].begin()+1,matrix[num-1].end());
        int prev=matrix[num-1][0];
        rep(i,0,n-1) matrix[num-1][i]=matrix[num-1][i+1];
        matrix[num-1][n-1]=prev;
    }
    if(d=='R'){
        //rotate(matrix[num-1].rbegin(),matrix[num-1].rbegin()+1,matrix[num-1].rend());
        int prev=matrix[num-1][n-1];
        for(int i=n-1; i>=1; --i) matrix[num-1][i]=matrix[num-1][i-1];
        matrix[num-1][0]=prev;
    }
    if(d=='U'){
        int prev=matrix[0][num-1];
        rep(i,0,n-1) matrix[i][num-1]=matrix[i+1][num-1];
        matrix[n-1][num-1]=prev;
    }
    if(d=='D'){
        int prev=matrix[n-1][num-1];
        for(int i=n-1; i>=1; --i) matrix[i][num-1]=matrix[i-1][num-1];
        matrix[0][num-1]=prev;
    }
}

int number(state &begin){
    int res=0;
    while(isdigit(*begin)){
        res*=10;
        res+=*begin-'0';
        ++begin;
    }
    return res;
}

void solve(){
    cin >> n >> l >> s;
    matrix.resize(n);
    rep(i,0,n){
        matrix[i].resize(n);
        rep(j,0,n) matrix[i][j]=i*n+j;
    }
    state begin=s.begin();
    sequence(begin);
    rep(i,0,n){
        rep(j,0,n){
            cout << matrix[i][j]+1;
            if(j!=n-1) cout << " ";
        }
        cout << endl;
    }
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}