타카하시의 기차 퍼즐 놀이 1
시간 제한1초메모리 제한512 MB
회전할 수 없는 4가지 블록으로 높이 r(최대 2), 너비 c인 직사각형을 빈틈없이 채우고, 행 문자열을 이어 붙여 사전순 k번째 문자열을 구한다.
문제
타카하시는 컴퓨터로 기차 퍼즐 게임을 하고 있었습니다. 반복된 퍼즐 게임에 질렸던 타카하시는 여러분들에게 다음과 같은 질문을 하였습니다.
[그림 1] 왼쪽 위부터 시계 방향으로 번, 번, 번, 번 블록
[그림 2] 덮이지 않는 공간이 하나 이상 있는 경우
세로 길이가 이고 가로 길이가 인 직사각형 모양의 퍼즐이 있어. 퍼즐에는 번부터 번까지 회전할 수 없는 가지 블록이 있고, 각 블록은 제한 없이 쓸 수 있어. 블록들을 퍼즐 영역 내부에 빈틈없이 채우려고 해. 블록들을 모두 채운 후에, 행 열에 있는 블록에 아래와 같은 규칙으로 문자를 하나 쓸 거야.
- 번 블록이 있으면 문자 를 적는다.
행 열에 있는 문자부터, 행 열까지 쓰여 있는 문자까지 차례대로 이어서 만든 문자열을 이라고 할 거야. 나는 부터 까지 차례대로 이어 붙여서 문자열 을 만들려고 해. 채울 수 있는 방법이 여러 가지라면 문자열 도 여러 개 나올 수 있겠지? 나는 이 중, 사전순으로 번째인 문자열을 알고 싶어.
타카하시의 질문을 해결해 주세요.
입력
첫 번째 줄에 가 주어집니다.
두 번째 줄부터 개의 줄에 걸쳐 , , 가 공백으로 구분되어 주어집니다.
출력
개의 줄에 걸쳐 문제의 답을 아래와 같이 한 줄에 하나씩 출력해 주세요.
- 세로 길이가 이고 가로 길이가 인 직사각형 모양의 퍼즐을 채울 수 있는 방법이 없거나 답이 되는 문자열 이 없다면,
-1을 출력해 주세요. - 그렇지 않으면 사전순으로 번째인 문자열 을 만들기 위해 사용했던 을 개의 줄에 걸쳐서 다음 조건에 맞춰 출력해 주세요.
- 번째 줄에 를 출력합니다.
각 질문에 대한 답은 개행으로 구분합니다.
제한
- 입력으로 주어지는 모든 수는 정수입니다.
- 테스트 케이스에 있는 모든 의 합은 을 넘지 않습니다.