Example

Input

3 2
R1


Output

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

vector<int> change(const vector<int>& a, const vector<int>& b) {
	int n = a.size();
	vector<int> res(n);
	for (int i = 0; i < n; i++) {
		res[i] = a[b[i]];
	}
	return res;
}

vector<int> Pow(vector<int> a, int x) {
	int n = a.size();
	vector<int> res(n);
	for (int i = 0; i < n; i++) {
		res[i] = i;
	}
	while (x) {
		if (x & 1) {
			res = change(res, a);
		}
		a = change(a, a);
		x >>= 1;
	}
	return res;
}

int it, len;
int N, L;
string S;

vector<int> sequence();
vector<int> repetition();
vector<int> operation();
int number();

vector<int> sequence() {
	vector<int> res(N * N);
	for (int i = 0; i < N * N; i++) {
		res[i] = i;
	}
	while (it < len && S[it] != ')') {
		if (S[it] == '(') {
			res = change(res, repetition());
		}
		else {
			res = change(res, operation());
		}
	}
	return res;
}

vector<int> repetition() {
	assert(S[it++] == '(');
	auto res = sequence();
	assert(S[it++] == ')');
	return Pow(res, number());
}

vector<int> operation() {
	vector<int> res(N * N);
	for (int i = 0; i < N * N; i++) {
		res[i] = i;
	}
	auto tmp = res;
	char c = S[it++];
	int cnt = number() - 1;
	switch (c) {
	case 'L':
		for (int i = 0; i < N; i++) {
			res[cnt * N + i] = tmp[cnt * N + (i + 1) % N];
		}
		break;
	case 'R':
		for (int i = 0; i < N; i++) {
			res[cnt * N + i] = tmp[cnt * N + (i + N - 1) % N];
		}
		break;
	case 'U':
		for (int i = 0; i < N; i++) {
			res[i * N + cnt] = tmp[(i + 1) % N * N + cnt];
		}
		break;
	case 'D':
		for (int i = 0; i < N; i++) {
			res[i * N + cnt] = tmp[(i + N - 1) % N * N + cnt];
		}
		break;
	}
	return res;
}

int number() {
	int res = 0;
	while (it < len && isdigit(S[it])) {
		res = res * 10 + S[it++] - '0';
	}
	return res;
}

int main()
{
	cin >> N >> L >> S;
	len = S.size();
	vector<int> tmp = sequence();
	vector<int> res(N * N);
	for (int i = 0; i < N * N; i++) {
		res[i] = i + 1;
	}
	res = change(res, tmp);
	for (int i = 0; i < N * N; i++) {
		cout << res[i] << " \n"[(i + 1) % N == 0];
	}
	return 0;
}