Example

Input

3 2
R1


Output

3 1 2
4 5 6
7 8 9
#include <bits/stdc++.h>
#define REP(i, a, n) for (ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

ll N, L;
string S;
ll p = 0;

vector<vector<ll>> sl(vector<vector<ll>> &a, ll r) {
  vector<vector<ll>> b(a);
  REP(i, 0, N) b[r][i] = a[r][(i + 1) % N];
  return b;
}

vector<vector<ll>> sr(vector<vector<ll>> &a, ll r) {
  vector<vector<ll>> b(a);
  REP(i, 0, N) b[r][i] = a[r][(i + N - 1) % N];
  return b;
}

vector<vector<ll>> su(vector<vector<ll>> &a, ll c) {
  vector<vector<ll>> b(a);
  REP(i, 0, N) b[i][c] = a[(i + 1) % N][c];
  return b;
}

vector<vector<ll>> sd(vector<vector<ll>> &a, ll c) {
  vector<vector<ll>> b(a);
  REP(i, 0, N) b[i][c] = a[(i + N - 1) % N][c];
  return b;
}

vector<vector<ll>> mg(vector<vector<ll>> &a, vector<vector<ll>> &b) {
  vector<vector<ll>> c(N, vector<ll>(N));
  REP(i, 0, N) REP(j, 0, N) {
    ll y = b[i][j] / N, x = b[i][j] % N;
    c[i][j] = a[y][x];
  }
  return c;
}

vector<vector<ll>> pw(vector<vector<ll>> &a, ll n) {
  if (n == 0) {
    vector<vector<ll>> e(N, vector<ll>(N));
    REP(i, 0, N) REP(j, 0, N) e[i][j] = i * N + j;
    return e;
  }
  if (n % 2 == 0) {
    vector<vector<ll>> b = mg(a, a);
    return pw(b, n / 2);
  } else {
    vector<vector<ll>> b = pw(a, n - 1);
    return mg(a, b);
  }
}

ll number() {
  ll n = 0;
  while (p < L && isdigit(S[p])) {
    n = n * 10 + (S[p++] - '0');
  }
  return n;
}

vector<vector<ll>> sequence() {
  vector<vector<ll>> ret(N, vector<ll>(N));
  REP(i, 0, N) REP(j, 0, N) ret[i][j] = i * N + j;

  while (p < L) {
    char c = S[p++];
    if (c == 'L') {
      ret = sl(ret, number() - 1);
    } else if (c == 'R') {
      ret = sr(ret, number() - 1);
    } else if (c == 'U') {
      ret = su(ret, number() - 1);
    } else if (c == 'D') {
      ret = sd(ret, number() - 1);
    } else if (c == '(') {
      vector<vector<ll>> a = sequence();
      vector<vector<ll>> b = pw(a, number());
      ret = mg(ret, b);
    } else if (c == ')') {
      break;
    }
  }

  return ret;
}

int main(void) {
  cin >> N >> L >> S;

  vector<vector<ll>> s = sequence();
  REP(i, 0, N) {
    REP(j, 0, N) cout << s[i][j] + 1 << (j + 1 != N ? " " : "\n");
  }
}
