Example

Input

3 2
R1


Output

3 1 2
4 5 6
7 8 9
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

using ll = long long int;
string S;
int pos;
int N, L;
vector<int> sequence() {
	vector<int> now;
	for (int i = 0; i < N*N; i++) now.push_back(i);
	while (pos < L && S[pos] != ')') {
		if (S[pos] == '(') {
			pos++;
			vector<int> ret = sequence();
			pos++;
			int num = 0;
			while (isdigit(S[pos])) {
				num *= 10;
				num += S[pos] - '0';
				pos++;
			}
			// (ret)num
			vector<vector<int>> d(30, vector<int>(N*N));
			d[0] = ret;
			for (int i = 1; i < 30; ++i) {
				// d[i]
				for (int j = 0; j < N*N; ++j) {
					d[i][j] = d[i - 1][d[i - 1][j]];
				}
			}

			// numを2べきで分解
			for (int i = 0; i < 30; ++i) {
				if (num & 1 << i) {
					for (int j = 0; j < N*N; ++j) {
						now[j] = d[i][now[j]];
					}
				}
			}
		}
		else {
			char shift = S[pos];
			pos++;
			int num = 0;
			while (isdigit(S[pos])) {
				num *= 10;
				num += S[pos] - '0';
				pos++;
			}
			num--;
			if (shift == 'L') {
				for (int i = 0; i < N*N; ++i) {
					int y = now[i] / N, x = now[i]%N;
					if (y == num) {
						if (x == 0) x = N - 1;
						else x--;
						now[i] = x + y*N;
					}
				}
			} else if (shift == 'R') {
				for (int i = 0; i < N*N; ++i) {
					int y = now[i] / N, x = now[i] % N;
					if (y == num) {
						if (x == N-1) x = 0;
						else x++;
						now[i] = x + y*N;
					}
				}
			}
			else if (shift == 'U') {
				for (int i = 0; i < N*N; ++i) {
					int y = now[i] / N, x = now[i] % N;
					if (x == num) {
						if (y == 0) y = N - 1;
						else y--;
						now[i] = x + y*N;
					}
				}
			}
			else if (shift == 'D') {
				for (int i = 0; i < N*N; ++i) {
					int y = now[i] / N, x = now[i] % N;
					if (x == num) {
						if (y == N-1) y = 0;
						else y++;
						now[i] = x + y*N;
					}
				}
			}
		}
	}
	return now;
}
int main() {
	cin >> N >> L;
	cin >> S;
	pos = 0;

	vector<int> ret = sequence();
	vector<vector<int>> ans(N, vector<int>(N));
	for (int i = 0; i < N*N; ++i) {
		int x = ret[i]%N, y = ret[i] / N;
		ans[y][x] = i+1;
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cout << ans[i][j] << (j == N-1 ? '\n' : ' ');
		}
	}
}
