Unscrambling Images

Quadtrees are commonly used to store digital images in a compact form. Take an $n \times n$ image where $n$ is a power of two and $1 \le n \le 16$. Its quadtree encoding is built as follows. Start with a quadtree that has exactly one node, the root, and associate the whole $n \times n$ region with that node. Then repeat the following recursively.

1. If every pixel in the region of the current node has intensity $p$, the node becomes a leaf and receives the value $p$.
2. Otherwise four nodes are added as children of the current node. The region splits into four equal square quadrants and each quadrant goes to one child. The algorithm recurses on every child node.

When the process terminates, every internal node has exactly four children, and every leaf carries a value that is the intensity of the region belonging to that leaf. The pictures below show an image together with its quadtree encoding.

The four children stand for the upper left, upper right, lower left, and lower right quadrants, in that order from left to right.

Every node of a quadtree gets a number by these rules.

• The root is numbered $0$.
• If a node is numbered $k$, its children from left to right are numbered $4k+1$, $4k+2$, $4k+3$, $4k+4$.

A password can encrypt an image encoded as a quadtree: every time a subdivision happens, the four branches are reordered. The reordering may differ at each node, and the password together with the node number determines it completely.

Some people switch on the "save password" option of the encoding program and reuse one password for many images. Encode one well chosen test image, look at the output, and any other image encoded with the same password can be decoded without the password. In that test image every pixel has a distinct intensity from $0$ to $n^2-1$, laid out left to right and top to bottom in increasing order. The figure below shows the layout for $n = 16$.

You gained access to the encoding program and used it to encode the test image. Given that output, decode any other image encoded with the same password.

The first line has a positive integer, the number of test cases. Each test case starts with a line holding $n$, followed by the quadtree encoding of the test image and then the quadtree encoding of the secret image to be decoded.

Each quadtree encoding starts with a line holding a positive integer $m$, the number of leaf nodes in the tree. The next $m$ lines have the form

k intensity

which says that node number $k$ is a leaf whose associated value is intensity. Nodes that are not listed are internal nodes or absent from the quadtree.

Every intensity is between $0$ and $255$ inclusive. Every quadtree encoding is a valid output of the encoding algorithm described above.

For each test case print the line Case x, where $x$ is the number of the test case counting from $1$, and then print a blank line. After that print the intensities of the decoded image one row per line. Right justify each intensity in a field of width $4$ and put no extra spaces between fields. Put one blank line between consecutive test cases.