Example

Input

3 2
R1


Output

3 1 2
4 5 6
7 8 9
#include <cstdio>
#include <cstdint>
#include <cctype>
#include <cassert>
#include <string>
#include <vector>
#include <algorithm>

class Permutation {
  size_t n;
  std::vector<std::vector<size_t>> body;

public:
  Permutation(size_t n): n(n), body(n, std::vector<size_t>(n)) {
    size_t k=0;
    for (size_t i=0; i<n; ++i)
      for (size_t j=0; j<n; ++j)
        body[i][j] = k++;
  }
  Permutation(size_t n, char shift, size_t k): Permutation(n) {
    if (shift == 'L') {
      size_t tmp=body[k][0];
      for (size_t j=1; j<n; ++j)
        body[k][j-1] = body[k][j];
      body[k][n-1] = tmp;
    } else if (shift == 'R') {
      size_t tmp=body[k][n-1];
      for (size_t j=n-1; j--;)
        body[k][j+1] = body[k][j];
      body[k][0] = tmp;
    } else if (shift == 'U') {
      size_t tmp=body[0][k];
      for (size_t i=1; i<n; ++i)
        body[i-1][k] = body[i][k];
      body[n-1][k] = tmp;
    } else if (shift == 'D') {
      size_t tmp=body[n-1][k];
      for (size_t i=n-1; i--;)
        body[i+1][k] = body[i][k];
      body[0][k] = tmp;
    }
  }

  Permutation& operator *=(const Permutation& other) {
    Permutation tmp(n);
    for (size_t i=0; i<n; ++i)
      for (size_t j=0; j<n; ++j) {
        size_t ii=other[i][j]/n;
        size_t jj=other[i][j]%n;
        tmp[i][j] = (*this)[ii][jj];
      }

    body = std::move(tmp.body);
    return *this;
  }

  Permutation& operator ^=(uintmax_t iexp) {
    Permutation tmp(n);
    for (Permutation dbl=*this; iexp; iexp>>=1) {
      if (iexp & 1) tmp *= dbl;
      dbl *= dbl;
    }
    body = std::move(tmp.body);
    return *this;
  }

  const std::vector<size_t>& operator [](size_t i) const {
    return body[i];
  }

  std::vector<size_t>& operator [](size_t i) {
    return body[i];
  }

  void print() const {
    for (size_t i=0; i<n; ++i)
      for (size_t j=0; j<n; ++j)
        printf("%zu%c", body[i][j]+1, j+1<n? ' ':'\n');
  }
};

uintmax_t parse_int(const std::string& s, size_t& i) {
  uintmax_t res=s[i]-'0';
  while (++i < s.length() && isdigit(s[i]))
    res = res*10+s[i]-'0';
  return res;
}

Permutation parse(const std::string& s, size_t& i, size_t n) {
  Permutation res(n);
  while (i < s.length() && s[i] != ')') {
    if (s[i] == '(') {
      Permutation tmp=parse(s, ++i, n);
      assert(s[i] == ')');
      tmp ^= parse_int(s, ++i);
      res *= tmp;
    } else {
      char shift=s[i];
      size_t number=parse_int(s, ++i);
      Permutation tmp(n, shift, number-1);
      res *= tmp;
    }
  }
  return res;
}

int main() {
  size_t N, L;
  char buf[1024];
  scanf("%zu %zu %s", &N, &L, buf);
  std::string S=buf;

  size_t i=0;
  parse(S, i, N).print();
}
