뒤섞인 이미지 복원

쿼드트리는 디지털 이미지를 압축된 형태로 저장할 때 흔히 쓴다. 크기가 $n \times n$인 이미지가 있고, $n$은 2의 거듭제곱이며 $1 \le n \le 16$이다. 이 이미지의 쿼드트리 부호화는 다음과 같이 만든다. 노드가 루트 하나뿐인 쿼드트리에서 시작하고, 이 노드에 이미지 전체인 $n \times n$ 영역을 대응시킨다. 그다음 아래 과정을 재귀적으로 반복한다.

1. 현재 노드의 영역에 있는 픽셀의 명암값이 모두 $p$로 같으면 이 노드를 리프로 만들고 값 $p$를 부여한다.
2. 그렇지 않으면 현재 노드에 자식 노드 네 개를 붙인다. 영역을 크기가 같은 정사각형 사분면 네 개로 나누고 각 사분면을 자식 하나에 대응시킨다. 알고리즘은 각 자식 노드에서 다시 재귀한다.

과정이 끝나면 모든 내부 노드는 자식이 정확히 네 개이고, 모든 리프는 그 리프가 맡은 영역의 명암값을 값으로 가진다. 아래는 이미지 하나와 그 쿼드트리 부호화의 예이다.

자식 네 개는 왼쪽부터 차례로 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 사분면을 나타낸다.

쿼드트리의 노드에는 다음 규칙으로 번호를 붙인다.

• 루트의 번호는 $0$이다.
• 번호가 $k$인 노드의 자식은 왼쪽부터 $4k+1$, $4k+2$, $4k+3$, $4k+4$이다.

쿼드트리로 부호화한 이미지는 비밀번호로 암호화할 수 있다. 영역을 분할할 때마다 가지 네 개의 순서를 바꾸는데, 바꾸는 방식은 노드마다 다를 수 있고 비밀번호와 노드 번호가 완전히 결정한다.

부호화 프로그램의 "비밀번호 저장" 기능을 켜 두고 여러 이미지에 같은 비밀번호를 쓰는 사람이 있다. 잘 고른 시험 이미지 하나를 부호화한 결과를 보면, 같은 비밀번호로 부호화한 다른 이미지는 비밀번호 없이도 복호화할 수 있다. 이 시험 이미지의 픽셀은 $0$부터 $n^2-1$까지 서로 다른 명암값을 가지고, 왼쪽에서 오른쪽으로 그리고 위에서 아래로 증가하는 순서로 놓여 있다. 아래 그림은 $n = 16$인 경우이다.

당신은 부호화 프로그램에 접근해서 시험 이미지를 부호화했다. 그 출력이 주어질 때, 같은 비밀번호로 부호화한 다른 이미지를 복호화하는 프로그램을 작성하라.

첫째 줄에 테스트 케이스의 개수를 나타내는 양의 정수가 주어진다. 각 테스트 케이스는 $n$이 적힌 줄로 시작하고, 이어서 시험 이미지의 쿼드트리 부호화와 복호화할 비밀 이미지의 쿼드트리 부호화가 차례로 주어진다.

쿼드트리 부호화는 트리의 리프 노드 개수인 양의 정수 $m$이 적힌 줄로 시작한다. 이어지는 $m$개 줄은 다음 형태이다.

k intensity

번호가 $k$인 노드가 리프이고 그 값이 intensity라는 뜻이다. 적히지 않은 노드는 내부 노드이거나 쿼드트리에 없다.

모든 명암값은 $0$ 이상 $255$ 이하이다. 각 쿼드트리 부호화는 위에서 설명한 부호화 알고리즘이 만든 올바른 출력이다.

각 테스트 케이스마다 Case x를 한 줄에 출력하고 빈 줄을 하나 출력한다. 여기서 $x$는 $1$부터 세는 테스트 케이스 번호이다. 그다음 복호화한 이미지의 명암값을 한 줄에 한 행씩 출력한다. 각 명암값은 너비가 $4$인 칸에 오른쪽 정렬로 출력하고 칸 사이에 공백을 더 넣지 않는다. 테스트 케이스 사이에는 빈 줄을 하나 넣는다.