01 격자 만들기

길이 $N$의 이진 문자열이 $Q$개 주어진다. $N \times N$ 이진 격자를 하나 만들어야 한다.

격자 위의 경로란 서로 다른 칸들의 순서열 $(p_1,p_2,\cdots,p_k)$로, 연속한 두 칸이 항상 상하좌우로 인접한 것을 말한다.

주어진 각 이진 문자열이 격자 위의 길이 $N$인 경로를 따라 순서대로 한 번 이상 나타나도록 격자를 구성하고, 각 문자열에 해당하는 경로 하나를 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

각 테스트 케이스마다 먼저 $N$개의 줄에 걸쳐 만든 이진 격자를 출력한다.

이어서 $i=1,2,\cdots,Q$의 순서대로 한 줄에 $2N$개의 정수 $r_1\ c_1\ r_2\ c_2\ \cdots\ r_N\ c_N$을 출력한다. 이는 $S_i$가 나타나는 경로의 칸 좌표를 순서대로 뜻한다.

가능한 답이 여러 가지라면 아무거나 출력해도 된다.

• $1 \leq T \leq 20$
• $2 \leq N \leq 100$
• $1 \leq Q \leq 10\,000$
• $S_i$는 길이 $N$의 이진 문자열이다.
• 모든 테스트 케이스에 대한 $NQ$의 합은 $1\,000\,000$ 이하이다.