28300번 - 응원단

문제

UCPC 대학교 내에서 열리는 체육대회의 응원단에 $N^2$($N$은 짝수)명의 단원이 참가할 예정이다. 응원단장은 먼저 $N^2$명의 단원을 $N$개의 행(가로줄)과 $N$개의 열(세로줄)로 구성된 $N\times N$의 격자 형태로 배치했다. 그리고 $i$행 $j$열에 위치한 응원단의 번호를 $A_{i,j}$라 할 때, $A_{i,j}=(i-1)\times N+j$번의 번호를 부여하는 방식으로 각 단원에게 1ドル$번부터 $N^2$번까지 번호를 매겼다.

$N=4$일 때 응원단의 상태

응원단은 경기가 진행될 동안 $Q$번의 응원 패턴을 수행하기로 했다. 수행할 응원 패턴의 종류는 총 5ドル$가지이다.

• $RO$: (홀수 행 이동) 홀수 행에 위치한 단원들의 열을 1ドル$ 증가시킨다. 열이 $N$을 초과한 단원은 동일한 행의 1ドル$열로 이동한다. 즉, $i$가 홀수인 모든 $i$에 대해 $A_{i,j}$를 $A_{i,((j-2)\mod N) +1}$로 바꾼다.
• $RE$: (짝수 행 이동) 짝수 행에 위치한 단원들의 열을 1ドル$ 증가시킨다. 열이 $N$을 초과한 단원은 동일한 행의 1ドル$열로 이동한다. 즉, $i$가 짝수인 모든 $i$에 대해 $A_{i,j}$를 $A_{i,((j-2)\mod N) +1}$로 바꾼다.
• $CO$: (홀수 열 이동) 홀수 열에 위치한 단원들의 행을 1ドル$ 증가시킨다. 행이 $N$을 초과한 단원은 동일한 열의 1ドル$행으로 이동한다. 즉, $j$가 홀수인 모든 $j$에 대해 $A_{i,j}$를 $A_{((i-2)\mod N) +1,j}$로 바꾼다.
• $CE$: (짝수 열 이동) 짝수 열에 위치한 단원들의 행을 1ドル$ 증가시킨다. 행이 $N$을 초과한 단원은 동일한 열의 1ドル$행으로 이동한다. 즉, $j$가 짝수인 모든 $j$에 대해 $A_{i,j}$를 $A_{((i-2)\mod N) +1,j}$로 바꾼다.
• $S$ $r_1$ $c_1$ $r_2$ $c_2$: (교체) $r_1$행 $c_1$열에 위치한 단원과 $r_2$행 $c_2$열에 위치한 단원이 서로 자리를 바꾼다.

단원의 수와 경기가 진행되는 동안 수행한 응원 패턴 $Q$개가 순서대로 주어졌을 때, 응원 패턴을 모두 수행한 뒤의 응원단의 최종 상태를 출력하자.

입력

첫 번째 줄에 $N,ドル $Q$가 공백으로 구분되어 주어진다. $(2\leq N\leq 1\ 000,N$은 짝수,1ドル\leq Q\leq 500\ 000)$

두 번째 줄부터 $Q$개의 줄에 각 줄마다 위의 5가지 응원 패턴 중 하나가 순서대로 주어진다. $(1\leq r_1,c_1,r_2,c_2\leq N,(r_1,c_1)\neq(r_2,c_2))$

입력으로 주어지는 모든 수는 정수이다.

출력

$N$개의 줄에 걸쳐 응원단의 최종 상태를 출력한다. $i$번째 줄에는 $i$행 1ドル$열부터 $i$행 $N$열까지 위치한 단원의 번호를 의미하는 $N$개의 정수를 공백으로 구분하여 출력한다.

제한

힌트