Building a Binary Grid

$Q$ binary strings of length $N$ are given. Construct one $N \times N$ binary grid.

A path is a sequence of distinct cells $(p_1,p_2,\cdots,p_k)$ such that every pair of consecutive cells shares a side.

Every given string must appear along at least one path of length $N$ in the constructed grid. Print the grid and one corresponding path for each string.

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, first print the constructed binary grid in $N$ lines.

Then, for $i=1,2,\cdots,Q$ in order, print $2N$ integers $r_1$ on one line. These are the cells of a path spelling , in order.

• $1 \leq T \leq 20$
• $2 \leq N \leq 100$
• $1 \leq Q \leq 10\,000$