뿌요뿌요 쌓기

사진은 뿌요뿌요의 플레이 화면이다. 이 화면은 12 × 6 격자를 쓰고, 뿌요의 색은 4종류이다.

뿌요뿌요는 Compile Co., Ltd.가 만든 비디오 게임이고 1991년에 처음 나왔다. 이 회사는 2003년에 부도가 났지만, 뿌요뿌요 팀은 Sonic Team으로 자리를 옮겨 지금도 뿌요뿌요를 만든다.

뿌요뿌요는 두 사람이 각자의 격자에 뿌요를 쌓아 겨루는 게임이다. 규칙은 다음과 같다.

• 게임은 빈 격자에서 시작한다.
• 뿌요는 둥근 슬라임 같은 물체이고, 화면 위쪽에서 격자 아래쪽으로 떨어진다.
• 뿌요마다 색이 있고, 색은 $K$종류이다.
• 뿌요는 두 개씩 쌍으로 조작한다.
• 뿌요 쌍은 컨트롤러로 좌우로 옮기거나, 가로 방향과 세로 방향으로 돌리거나, 떨어뜨릴 수 있다.
• 뿌요 쌍을 떨어뜨리면 두 뿌요가 하나씩 떨어지고, 각 뿌요는 다른 뿌요에 닿거나 격자 바닥에 닿을 때까지 내려간다.
• 뿌요는 격자 바깥에도 쌓을 수 있지만, 격자의 위쪽으로만 벗어날 수 있다.
• 같은 색 뿌요가 상하좌우로 4개 이상 이어진 덩어리를 그룹이라고 하고, 그룹이 만들어지면 그 뿌요는 사라진다. 이것을 터뜨리기라고 한다.
• 뿌요 쌍 하나를 떨어뜨려 그룹이 둘 이상 동시에 만들어지면, 그 그룹은 함께 터진다.
• 그룹이 터진 뒤에는 남은 뿌요가 바닥이나 다른 뿌요에 닿을 때까지 내려간다. 그러다 새 그룹이 생기면 그 그룹도 같은 방식으로 터지고 다시 내려간다. 이렇게 이어지는 것을 체인이라고 한다.
• 체인이 끝나기 전에는 새 뿌요를 놓을 수 없다.

Sonic Team이 PPAP (Puyo Puyo Algorithm for Printing)을 만들어 달라고 부탁했다. 게임 소프트웨어에 들어가는 기능은 아니고, 특별한 행사에서 쓰는 프로그램이다.

$R \times C$ 격자의 최종 상태가 주어진다. 각 칸에는 어떤 색의 뿌요가 있거나 칸이 비어 있다. 뿌요 쌍을 차례로 떨어뜨려 이 최종 상태를 만들어야 한다. 최종 상태에서 모든 뿌요는 격자 안에 있어야 한다. 뿌요의 색도, 떨어뜨리는 위치도 마음대로 정할 수 있다.

첫째 줄에 정수 $R$, $C$, $K$가 공백으로 구분되어 주어진다.

다음 $R$개의 줄에 만들어야 하는 최종 상태가 주어진다. 각 줄에는 공백으로 구분된 $C$개의 정수가 주어지고, 먼저 나오는 줄이 격자의 위쪽 행이다. 1 이상 $K$ 이하의 수는 뿌요의 색이고, 0은 빈 칸이다.

최종 상태를 250번 이하의 낙하로 만들 수 있는 입력만 주어진다. 그래서 각 열의 뿌요는 바닥부터 빈 칸 없이 쌓여 있고, 같은 색 뿌요가 4개 이상 이어진 곳은 없다.

첫째 줄에 떨어뜨린 뿌요 쌍의 개수 $D$를 출력한다.

다음 $D$개의 줄에 뿌요 쌍을 하나씩 어떻게 떨어뜨렸는지 네 정수로 출력한다.

• 첫 번째 수는 쌍을 가로로 놓으면 0, 세로로 놓으면 1이다.
• 두 번째 수는 가로로 놓을 때는 왼쪽 뿌요가 떨어지는 열 번호, 세로로 놓을 때는 두 뿌요가 떨어지는 열 번호이다. 열 번호는 왼쪽부터 1부터 센다.
• 세 번째 수는 왼쪽 뿌요 또는 위쪽 뿌요의 색이다.
• 네 번째 수는 오른쪽 뿌요 또는 아래쪽 뿌요의 색이다.

세로로 놓은 쌍은 아래쪽 뿌요가 먼저 떨어지고, 위쪽 뿌요가 그 위에 쌓인다.

최종 상태를 만드는 순서는 여러 가지이므로, 다음 규칙으로 만든 순서 하나만 정답으로 인정한다.

열 $j$의 높이 $h_j$는 최종 상태에서 열 $j$에 있는 뿌요의 개수이고, 열 $j$의 아래에서 $i$번째 뿌요의 색을 $c_i$라고 하자. 열을 높이가 작은 것부터, 높이가 같으면 열 번호가 작은 것부터 정렬하고, 그 순서대로 각 열을 다음과 같이 채운다.

• $i$를 1, 3, 5, ...로 늘려가면서 $i + 1 \le h_j$ 인 동안 네 정수 $1$, $j$, $c_{i+1}$, $c_i$를 출력한다. 이 낙하가 아래에서 $i$번째 칸과 $i + 1$번째 칸을 채운다.
• $h_j$가 홀수이면 맨 위 칸 하나가 남는다. $c_{h_j}$가 1이 아니면 $v = 1$, $c_{h_j}$가 1이면 $v = 2$로 두자. 네 정수 $1$, $j$, $v$, $c_{h_j}$를 출력해 맨 위 칸을 채우고 색이 $v$인 뿌요 하나를 그 위에 남긴 다음, 네 정수 $1$, $j$, $v$, $v$를 두 번 출력한다. 색이 $v$인 뿌요 다섯 개가 이 열에 세로로 이어져 터지므로, 열 $j$에는 최종 상태만 남는다. $K \ge 3$이므로 $v$는 항상 쓸 수 있는 색이다.
• $h_j = 0$인 열에서는 아무것도 출력하지 않는다.

$D$는 이렇게 출력한 줄의 개수이다.

• $3 \le K \le 6$
• $R = C = 4$ 또는 $R = C = 20$
• $D \le 250$

첫 번째 예제에서 뿌요는 다음과 같이 떨어진다. 아래 그림은 여섯 줄인데, 아래 네 줄이 격자이고 위 두 줄은 격자 위쪽 바깥이다. 두 열의 높이가 모두 1이므로 열 번호가 작은 2열을 먼저 채운다.

0 0 0 0    0 0 0 0    0 0 0 0    0 2 0 0    0 0 0 0
0 0 0 0    0 0 0 0    0 0 0 0    0 2 0 0    0 0 0 0
0 0 0 0    0 0 0 0    0 2 0 0    0 2 0 0    0 0 0 0
0 0 0 0 -> 0 0 0 0 -> 0 2 0 0 -> 0 2 0 0 -> 0 0 0 0
0 0 0 0    0 2 0 0    0 2 0 0    0 2 0 0    0 0 0 0
0 0 0 0    0 1 0 0    0 1 0 0    0 1 0 0    0 1 0 0

네 번째 그림에서 색이 2인 뿌요 다섯 개가 세로로 이어져 터지고, 색이 1인 뿌요만 남는다. 이어서 4열을 같은 방법으로 채운다.

0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 2    0 0 0 0
0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 2    0 0 0 0
0 0 0 0    0 0 0 0    0 0 0 2    0 0 0 2    0 0 0 0
0 0 0 0 -> 0 0 0 0 -> 0 0 0 2 -> 0 0 0 2 -> 0 0 0 0
0 0 0 0    0 0 0 2    0 0 0 2    0 0 0 2    0 0 0 0
0 1 0 0    0 1 0 1    0 1 0 1    0 1 0 1    0 1 0 1