34072번 - 배열 정리하기 스페셜 저지

문제

준호는 크기가 $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$이 됩니다.