Example

Input

3 2
R1


Output

3 1 2
4 5 6
7 8 9
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

typedef vector<int> MATRIX;

int N,SIZE,length;
char buf[1001];

int getLoc(int row,int col){
	return N*row+col;
}

MATRIX calc(MATRIX left,MATRIX next_loc){

	MATRIX ret(SIZE);

	for(int i = 0; i < SIZE; i++){
		ret[i] = next_loc[left[i]];
	}

	return ret;

}

MATRIX pow(MATRIX next_loc,int count){

	MATRIX ret(SIZE);

	for(int i = 0; i < SIZE; i++)ret[i] = i;

	while(count > 0){
		if(count%2 == 1){
			ret = calc(ret,next_loc);
		}
		next_loc = calc(next_loc,next_loc);
		count /= 2;
	}

	return ret;
}


MATRIX calcNextLoc(int left,int right){

	MATRIX first_loc(SIZE),next_loc(SIZE),work(SIZE);
	for(int i = 0; i < SIZE; i++)first_loc[i] = i;

	int index = left;

	while(index <= right){

		if(buf[index] == '('){

			int depth = 0,next_right;

			for(int i = index; i <= right; i++){
				if(buf[i] == '(')depth++;
				else if(buf[i] == ')'){
					depth--;
					if(depth == 0){
						next_right = i;
						break;
					}
				}
			}
			next_loc = calcNextLoc(index+1,next_right-1);

			int count = 0;

			for(index = next_right+1;buf[index] >= '0' && buf[index] <= '9'; index++){
				count = 10*count+buf[index]-'0';
			}

			if(count > 1){
				next_loc = pow(next_loc,count);
			}

			for(int i = 0; i < SIZE; i++)work[i] = next_loc[first_loc[i]];
			for(int i = 0; i < SIZE; i++)first_loc[i] = work[i];

		}else{

			int next_right;
			for(next_right = index; next_right <= right && buf[next_right] != '('; next_right++);
			next_right--;

			int num,k;

			for(int i = 0; i < SIZE; i++)next_loc[i] = i;

			for(int i = index; i <= next_right;){

				num = 0;
				for(k = i+1; buf[k] >= '0' && buf[k] <= '9'; k++){
					num = 10*num+buf[k]-'0';
				}

				num--;

				switch(buf[i]){
				case 'L':

					work[getLoc(num,N-1)] = next_loc[getLoc(num,0)];

					for(int col = 1; col < N; col++){
						work[getLoc(num,col-1)] = next_loc[getLoc(num,col)];
					}
					for(int col = 0; col < N; col++){
						next_loc[getLoc(num,col)] = work[getLoc(num,col)];
					}

					break;
				case 'R':

					work[getLoc(num,0)] = next_loc[getLoc(num,N-1)];

					for(int col = 0; col < N-1; col++){
						work[getLoc(num,col+1)] = next_loc[getLoc(num,col)];
					}
					for(int col = 0; col < N; col++){
						next_loc[getLoc(num,col)] = work[getLoc(num,col)];
					}

					break;
				case 'U':

					work[getLoc(N-1,num)] = next_loc[getLoc(0,num)];

					for(int row = 1; row < N; row++){
						work[getLoc(row-1,num)] = next_loc[getLoc(row,num)];
					}

					for(int row = 0; row < N; row++){
						next_loc[getLoc(row,num)] = work[getLoc(row,num)];
					}

					break;
				case 'D':

					work[getLoc(0,num)] = next_loc[getLoc(N-1,num)];

					for(int row = 0; row < N-1; row++){
						work[getLoc(row+1,num)] = next_loc[getLoc(row,num)];
					}

					for(int row = 0; row < N; row++){
						next_loc[getLoc(row,num)] = work[getLoc(row,num)];
					}

					break;
				}
				i = k;
			}

			index = next_right+1;
			for(int i = 0; i < SIZE; i++){
				work[next_loc[i]] = i;
			}

			for(int i = 0; i < SIZE; i++){
				next_loc[i] = work[i];
			}

			for(int i = 0; i < SIZE; i++){
				work[i] = next_loc[first_loc[i]];
			}

			for(int i = 0; i < SIZE; i++){
				first_loc[i] = work[i];
			}
		}
	}
	return first_loc;
}


int main(){

	scanf("%d %d",&N,&length);
	SIZE = N*N;

	scanf("%s",buf);

	MATRIX ans(SIZE),final_loc(SIZE);
	final_loc = calcNextLoc(0,length-1);

	for(int i = 0; i < SIZE; i++){
		ans[final_loc[i]] = i+1;
	}

	for(int row = 0; row < N; row++){
		printf("%d",ans[getLoc(row,0)]);
		for(int col = 1; col < N; col++){
			printf(" %d",ans[getLoc(row,col)]);
		}
		printf("\n");
	}

	return 0;
}


