Un cuadrado latino de tamaño \(N\) es una matriz de \(N \times N\) con valores entre \(1\) y \(N\) sin repetidos en ninguna fila ni columna.

A una matriz se le aplica, en orden, una lista de \(T\) transformaciones; cada una intercambia dos filas distintas o dos columnas distintas. Determina si existe un cuadrado latino que quede igual después de aplicar todas las transformaciones, y si existe, muestra uno.

Entrada

La primera línea tiene dos enteros \(N\) \((2 \le N \le 500)\) y \(T\) \((1 \le T \le 10^5)\).

Cada una de las siguientes \(T\) líneas tiene un carácter \(X\) y dos enteros \(I\) y \(J\) \((1 \le I, J \le N,\ I \ne J)\): si \(X\) es R se intercambian las filas \(I\) y \(J\), y si es C, las columnas \(I\) y \(J\).

Salida

Si existe, \(N\) líneas con \(N\) enteros cada una: un cuadrado latino que no cambia con las transformaciones. Si hay varios, cualquiera es aceptado. Si no existe, una línea con el carácter *.

Ejemplo 1

Entrada

4 4
R 1 2
C 2 1
R 3 4
C 3 4

Salida

1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

Ejemplo 2

Entrada

4 3
R 1 2
R 1 2
R 2 1

Salida

*

Regional Latinoamericana 2024 del ICPC, problema L («Latin Squares»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.