배열 정리하기

준호는 크기가 $N \times N$인 이차원 배열 $A$를 가지고 있다. 준호가 가진 배열 $A$는 다음과 같은 성질을 가진다:

1. $A\_{0,0}$과 $A\_{N-1, N-1}$을 양 끝으로 가진다.
2. $0 \leq a \leq N^2-1$를 만족하는 각 정수 $a$가 정확히 한 번씩 배열의 원소로 등장한다.

준호는 배열을 정리하려고 한다. 정리된 배열이란 $0 \leq i,j \leq N-1$인 모든 정수 순서쌍 $(i,j)$에 대해 $A\_{i,j} = i \times N+j$를 만족하는 배열을 말한다.

배열을 정리하기 위해, 준호는 다음 중 원하는 연산을 골라 할 수 있다:

• $1$ $x$ $y$: $(0 \leq x \leq N-1; 0 \leq y \leq N-2)$을 만족하는 $(x, y)$를 골라, $A\_{x,y}$를 $A\_{x,y}+A\_{x,y+1}$로 바꾼다.
• $2$ $x$ $y$: $(0 \leq x \leq N-1; 0 \leq y \leq N-2)$을 만족하는 $(x, y)$를 골라, $A\_{x,y}$를 $A\_{x,y}-A\_{x,y+1}$로 바꾼다.
• $3$ $x$ $y$: $(0 \leq x \leq N-1; 1 \leq y \leq N-1)$을 만족하는 $(x, y)$를 골라, $A\_{x,y}$를 $A\_{x,y}+A\_{x,y-1}$로 바꾼다.
• $4$ $x$ $y$: $(0 \leq x \leq N-1; 1 \leq y \leq N-1)$을 만족하는 $(x, y)$를 골라, $A\_{x,y}$를 $A\_{x,y}-A\_{x,y-1}$로 바꾼다.
• $5$ $x$ $y$: $(0 \leq x \leq N-2; 0 \leq y \leq N-1)$을 만족하는 $(x, y)$를 골라, $A\_{x,y}$를 $A\_{x,y} \oplus A\_{x+1,y}$로 바꾼다.
• $6$ $x$ $y$: $(1 \leq x \leq N-1; 0 \leq y \leq N-1)$을 만족하는 $(x, y)$를 골라, $A\_{x,y}$를 $A\_{x,y} \oplus A\_{x-1,y}$로 바꾼다.

단, 연산 도중 배열의 원소가 $-2^{31}$보다 작아지거나, $2^{31}-1$보다 커지면 안 된다.

이때 $-2^{31}$부터 $2^{31}-1$사이의 두 정수 $a$와 $b$에 대해 $a \oplus b$ 연산은 $32$비트 부호 있는 정수 자료형에서의 XOR(exclusive OR)로 정의된다. 이에 대해선 노트를 참고하라.

준호가 제한을 만족하며 주어진 연산을 최대 $400\\,000$회 하여 배열 $A$를 정리된 배열로 바꾸는 방법을 구해보자. 가능한 방법이 여러 가지라면, 아무 방법이나 구해보자.

연산의 횟수를 최소화 할 필요는 없음에 유의하라.

첫째 줄에 배열의 크기를 나타내는 $N$이 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐 $i+2$번째 줄에 $N$개의 정수 $A\_{i,0}, \cdots, A\_{i,N-1}$이 공백으로 구분되어 주어진다.

첫째 줄에 준호가 배열 $A$를 정리하기 위한 연산 횟수 $q$를 출력한다. $(0 \leq q \leq 400\\,000)$

둘째 줄부터 $q$개의 줄에 걸쳐 준호가 배열에 $i$번째로 적용한 연산의 번호와 선택한 $x$와 $y$를 $i+1$번째 줄에 공백으로 구분하여 출력한다.

모든 가능한 입력에 대해 주어진 제한 안에 $A$를 정리할 수 있음을 보일 수 있다.

• 주어지는 모든 수는 정수이다.
• $2 \leq N \leq 50$
• $0 \le A\_{i,j} \le N^2-1$ $(0 \le i,j \le N-1)$
• $A\_{i, j}$는 모두 서로 다르다.

아래 내용은 $32$비트 부호 있는 정수 자료형에서의 비트 표현 방법에 대해 설명합니다.

$0$과 양수는 그 값을 그대로 이진수로 표현합니다.

음수는 $2$의 보수로 변환하여 저장됩니다. $2$의 보수 표현 방법은 다음과 같습니다:

1. 양수의 이진수로 변환합니다.
2. $1$의 보수(모든 비트를 반전)로 변환합니다.
3. $1$을 더하여 $2$의 보수를 구합니다.

예를 들어 $-5$를 $32$비트 $2$의 보수로 표현해 봅시다.

1. $5$는 $00000000 \\, 00000000 \\, 00000000 \\, 00000101$입니다.
2. 1의 보수를 구합니다. $1$의 보수는 모든 비트를 반전시킨 값입니다: $11111111 \\, 11111111 \\, 11111111 \\, 11111010$
3. $2$의 보수를 구합니다. $1$의 보수에 $1$을 더하면 $2$의 보수가 됩니다: $11111111 \\, 11111111 \\, 11111111 \\, 11111011$

따라서, $-5$는 $2$의 보수 방식으로 $11111111 \\, 11111111 \\, 11111111 \\, 11111011$으로 표현됩니다.

아래 내용은 $32$비트 부호 있는 정수 자료형에서의 XOR(exclusive OR)연산에 관해 설명합니다.

두 정수의 XOR 연산은 각 비트 자리에서 서로 다르면 $1$, 같으면 $0$이 되는 비트 연산입니다. 예를 들어

$11111110 \\, 00000000 \\, 00000000 \\, 00000101 \oplus 00001111 \\, 00000000 \\, 01111000 \\, 00000101$을 계산하면

$11110001 \\, 00000000 \\, 01111000 \\, 00000000$이 됩니다.