라틴 방진

크기가 $N$인 라틴 방진은 $N \times N$ 행렬이며, 각 칸에는 $1$ 이상 $N$ 이하의 정수가 들어간다. 같은 행이나 같은 열에 있는 두 칸의 값은 서로 달라야 한다.

Alice는 크기 $N$인 라틴 방진을 가지고 있고, 이 행렬에 변환을 여러 번 순서대로 적용했다. 각 변환은 행렬에서 서로 다른 두 행 또는 서로 다른 두 열을 맞바꾼다. 첫 번째 변환은 원래 행렬에 적용되고, 두 번째 변환은 첫 번째 변환의 결과에 적용된다. 이렇게 모든 변환을 적용한 최종 결과는 $N \times N$ 행렬이다.

Alice는 행렬을 보여주지 않고 변환 목록만 알려준다. 모든 변환을 적용했을 때 최종 행렬과 같아지는 원래 행렬이 존재하는지 판단하라. 존재한다면 원래 행렬의 가능한 내용 하나를 출력한다.

첫 줄에 라틴 방진의 크기 $N$ ($2 \le N \le 500$)과 변환의 개수 $T$ ($1 \le T \le 10^5$)가 정수로 주어진다.

다음 $T$개의 줄에는 적용되는 순서대로 변환이 하나씩 주어진다. 각 줄은 문자 $X$와 두 정수 $I$, $J$ ($1 \le I, J \le N$, $I \ne J$)로 이루어진다. $X$가 R이면 $I$번 행과 $J$번 행을 맞바꾸고, C이면 $I$번 열과 $J$번 열을 맞바꾼다.

원래 행렬이 존재하여 모든 변환을 적용하면 최종 행렬과 같아진다면, 그러한 행렬을 $N$개의 줄에 나누어 출력한다. 각 줄에는 정수 $N$개를 출력한다. 가능한 행렬 중 아무것이나 한 가지를 출력하면 된다.

그러한 행렬이 존재하지 않으면 별표 * 한 글자만 담긴 한 줄을 출력한다.