Description

Little Z has recently become obsessed with jigsaw puzzles, but with limited intelligence, he always fails to complete the full picture. The game works like this: first, Little Z is given some puzzle pieces. He then tries to rearrange these pieces so that they form a $4 \times 4$ square, as shown below. Note that Little Z cannot rotate or flip the pieces.

Little Z gets the pieces shown in Figure 1, and after rearranging them, he obtains the $4 \times 4$ square shown in Figure 2.

Since Little Z is really not good at this, please write a program to help him solve the problem.

Input Format

The input contains multiple test cases; read until EOF.

For each test case, the first line contains a positive integer $N$, the number of pieces. Then $N$ pieces follow. For each piece, the first line contains two positive integers $r$ and $c$, the number of rows and columns of this piece. Then there are $r$ lines, each containing $c$ characters '0' or '1'; '1' means the piece occupies that cell, and '0' means the cell is empty. It is guaranteed that each piece is a single connected component (i.e., the '1's are connected), and there is no row or column consisting entirely of '0's.

Output Format

If it is impossible to form a square, output "No solution". If there are multiple solutions, output "Yes, many!". Otherwise, output "Yes, only one!", and then output a $4 \times 4$ matrix $H$, where $H_{i,j}$ denotes the index of the piece at position $(i, j)$. Piece indices start from $1$.

4
2 3
111
101
4 2
01
01
11
01
2 1
1 1
3 2
10
10
11
4
1 4
1111
1 4
1111
1 4
1111
1 4
1111
4
1 4
1111
1 4
1111
1 4
1111
2 3
111
001

Yes, only one!
1112
1412
3422
3442
Yes, many!
No solution

Hint

Constraints

• For $30\%$ of the test cases, $N < 5$.
• For $100\%$ of the test cases, $N \le 16$.

Translated by ChatGPT 5