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$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N\ Q$ $S_1$ $S_2$ $\vdots$ $S_Q$

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\ c_1\ r_2\ c_2\ \cdots\ r_N\ c_N$ on one line. These are the cells of a path spelling $S_i$, in order.

If there are multiple solutions, print any of them.

• $1 \leq T \leq 20$
• $2 \leq N \leq 100$
• $1 \leq Q \leq 10\,000$
• $S_i$ is a binary string of length $N$.
• The sum of $NQ$ over all test cases does not exceed $1\,000\,000$.