타카하시의 기차 퍼즐 놀이 1

타카하시는 컴퓨터로 기차 퍼즐 게임을 하고 있었습니다. 반복된 퍼즐 게임에 질렸던 타카하시는 여러분들에게 다음과 같은 질문을 하였습니다.

[그림 1] 왼쪽 위부터 시계 방향으로 $1$번, $2$번, $4$번, $3$번 블록

[그림 2] 덮이지 않는 공간이 하나 이상 있는 경우

세로 길이가 $r$이고 가로 길이가 $c$인 직사각형 모양의 퍼즐이 있어. 퍼즐에는 $1$번부터 $4$번까지 회전할 수 없는 $4$가지 블록이 있고, 각 블록은 제한 없이 쓸 수 있어. 블록들을 퍼즐 영역 내부에 빈틈없이 채우려고 해. 블록들을 모두 채운 후에, $r$행 $c$열에 있는 블록에 아래와 같은 규칙으로 문자를 하나 쓸 거야.

• $b$번 블록이 있으면 문자 $b$를 적는다.

$r$행 $1$열에 있는 문자부터, $r$행 $c$열까지 쓰여 있는 문자까지 차례대로 이어서 만든 문자열을 $S_{r}$이라고 할 거야. 나는 $S_{1}$부터 $S_{r}$까지 차례대로 이어 붙여서 문자열 $R$을 만들려고 해. 채울 수 있는 방법이 여러 가지라면 문자열 $R$도 여러 개 나올 수 있겠지? 나는 이 중, 사전순으로 $k$번째인 문자열을 알고 싶어.

타카하시의 질문을 해결해 주세요.

첫 번째 줄에 $Q$가 주어집니다.

두 번째 줄부터 $Q$개의 줄에 걸쳐 $r$, $c$, $k$가 공백으로 구분되어 주어집니다.

$Q$개의 줄에 걸쳐 문제의 답을 아래와 같이 한 줄에 하나씩 출력해 주세요.

• 세로 길이가 $r$이고 가로 길이가 $c$인 직사각형 모양의 퍼즐을 채울 수 있는 방법이 없거나 답이 되는 문자열 $R$이 없다면, -1을 출력해 주세요.
• 그렇지 않으면 사전순으로 $k$번째인 문자열 $R$을 만들기 위해 사용했던 $S_{1}, .. , S_{r}$을 $r$개의 줄에 걸쳐서 다음 조건에 맞춰 출력해 주세요.
  • $i$번째 줄에 $S_{i}$를 출력합니다.

각 질문에 대한 답은 개행으로 구분합니다.

• $1 \leq Q \leq 10^{6}$
• $1 \leq r \leq 2$
• $1 \leq c \leq 10^{6}$
• $1 \leq k \leq 10^{18}$
• 입력으로 주어지는 모든 수는 정수입니다.
• 테스트 케이스에 있는 모든 $c$의 합은 $10^{6}$을 넘지 않습니다.