Latin Squares

A Latin square of size $N$ is an $N \times N$ matrix where each entry is an integer between $1$ and $N$, and no two entries in the same row or column are equal.

Alice has a Latin square of size $N$ and applied a list of transformations to it. Each transformation swaps either two distinct rows or two distinct columns of the matrix. The transformations are applied in order: the first one is applied to the original matrix, the second to the result of the first, and so on. The final result is an $N \times N$ matrix.

Alice does not reveal the matrix, only the list of transformations. Determine whether an original matrix exists that becomes the final matrix after all transformations are applied. If one exists, output any possible content of the original matrix.

The first line contains two integers $N$ ($2 \le N \le 500$) and $T$ ($1 \le T \le 10^5$), the size of the Latin square and the number of transformations.

Each of the next $T$ lines describes one transformation, in the order they are applied. A line contains a character $X$ and two integers $I$ and $J$ ($1 \le I, J \le N$, $I \ne J$). If $X$ is R, rows $I$ and $J$ are swapped. If $X$ is C, columns $I$ and $J$ are swapped.

If an original matrix exists that becomes the final matrix after all transformations, output $N$ lines with $N$ integers each, representing any such matrix.

If no such matrix exists, output a single line containing the character * (asterisk).