Example

Input

3 2
R1


Output

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

int N, L; string S;

struct State { vector<vector<int>>v; };

State Initialize(int H, int W) {
	State S; S.v = vector<vector<int>>(H, vector<int>(W, 0));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) S.v[i][j] = i*W + j;
	}
	return S;
}
State Add(State A, State B) {
	State S = A;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int xx = B.v[i][j], x = xx / N, y = xx%N;
			S.v[i][j] = A.v[x][y];
		}
	}
	return S;
}
State Multiple(State A, long long x) {
	State B = A, C = Initialize(N, N);
	for (int i = 0; i < 30; i++) {
		if ((x / (1 << i)) % 2 == 1) { C = Add(C, B); }
		B = Add(B, B);
	}
	return C;
}
State parse(string S) {
	vector<string>vec; string T = ""; bool J = false; int depth = 0;
	for (int i = 0; i < S.size(); i++) {
		T += S[i];
		if (i == S.size() - 1 || (depth == 0 && S[i] >= '0' && S[i] <= '9' && (S[i + 1] == '(' || S[i + 1] == 'L' || S[i + 1] == 'R' || S[i + 1] == 'U' || S[i + 1] == 'D'))) {
			vec.push_back(T); T = "";
		}
		if (S[i] == '(' || S[i] == ')') J = true;
		if (S[i] == '(') depth++;
		if (S[i] == ')') depth--;
	}
	if (vec.size() == 1 && J == false) {
		// 1 回のケース
		char F = vec[0][0]; string Y = vec[0]; int R = stoi(Y.substr(1, Y.size() - 1));
		
		State V = Initialize(N, N);
		if (F == 'L') {
			vector<int>b(N, 0);
			for (int i = 0; i < N; i++) b[(i + N - 1) % N] = V.v[R - 1][i];
			for (int i = 0; i < N; i++) V.v[R - 1][i] = b[i];
		}
		if (F == 'R') {
			vector<int>b(N, 0);
			for (int i = 0; i < N; i++) b[(i + 1) % N] = V.v[R - 1][i];
			for (int i = 0; i < N; i++) V.v[R - 1][i] = b[i];
		}
		if (F == 'U') {
			vector<int>b(N, 0);
			for (int i = 0; i < N; i++) b[(i + N - 1) % N] = V.v[i][R - 1];
			for (int i = 0; i < N; i++) V.v[i][R - 1] = b[i];
		}
		if (F == 'D') {
			vector<int>b(N, 0);
			for (int i = 0; i < N; i++) b[(i + 1) % N] = V.v[i][R - 1];
			for (int i = 0; i < N; i++) V.v[i][R - 1] = b[i];
		}
		return V;
	}
	if (vec.size() == 1 && J == true) {
		// 繰り返し
		string U = vec[0]; int lx = 0, rx = 0, depth2 = 0;
		for (int i = 0; i < U.size(); i++) {
			if (U[i] == '(') {
				if (depth == 0) lx = i;
				depth++;
			}
			if (U[i] == ')') {
				depth--;
				if (depth == 0) rx = i;
			}
		}
		string V1 = U.substr(lx + 1, rx - lx - 1);
		string V2 = U.substr(rx + 1, U.size() - (rx + 1));
		int V3 = stoi(V2);
		State V0 = parse(V1);
		State V = Multiple(V0, V3);
		return V;
	}
	if (vec.size() != 1) {
		// 複数に分かれているやつ
		State V = Initialize(N, N);
		for (int i = 0; i < vec.size(); i++) {
			State F = parse(vec[i]);
			V = Add(V, F);
		}
		return V;
	}
}

int main() {
	cin >> N >> L >> S;
	State G = parse(S);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) { if (j)cout << " "; cout << G.v[i][j] + 1; }
		cout << endl;
	}
	return 0;
}
