소셜 미디어에서 소식을 접한다면, 백신으로 사람들에게 칩을 심거나 불소로 체액을 오염시키는 등의 계획을 가진 여러 비밀 조직에 관한 음모론을 이미 몇 가지 들어 보았을 것이다. 젊은 Martin은 최근 바로 그런 조직 중 하나의 도움으로 유명한 크로아티아 신문의 사장 자리를 얻었다.

그 조직이 신문에 관심을 가진 데에는 이유가 있었다. 조직은 모든 구성원에게 느리고 비효율적으로 메시지를 보내면서, 동시에 가능한 한 많은 음모론을 만들어 낼 방법이 필요했다. 어떤 수비학적이고 신비로운 특성 때문에 조직은 Martin에게 메시지를 보내는 데 특이한 매체를 사용하라고 지시했다. 기사 본문에 메시지를 숨기는 대신 신문의 퍼즐란에 숨겨야 한다. 더 정확히 말하면 스도쿠 퍼즐에 숨겨야 한다.

스도쿠 퍼즐은 $9\times9$개의 칸으로 이루어진 격자이며, 일부 칸에는 1부터 9까지의 숫자가 적혀 있다. 퍼즐은 9개의 행, 9개의 열, 그리고 크기가 $3\times3$인 정사각형 블록 9개로 나뉜다. 모든 칸을 1부터 9까지의 숫자로 채우되, 어떤 행, 열, 블록에서도 숫자가 중복되지 않으면 퍼즐을 푼 것으로 간주한다.

Martin의 임무는 $N$개의 단어 $s_i$로 이루어진 수열을 $N$개의 스도쿠 퍼즐로 인코딩한 뒤, 그 퍼즐들을 다시 단어로 디코딩하는 프로그램을 작성하는 것이다.

신문의 퍼즐 제작자들은 Martin이 아무 스도쿠 퍼즐이나 신문에 싣도록 허락하지 않을 것이다. 대신 Martin이 제안한 풀린 퍼즐에서 원하는 난이도에 따라 일정 개수의 숫자를 지워 퍼즐을 만들 것이다. 따라서 Martin의 프로그램은 단어들을 이미 풀린 스도쿠 퍼즐로 인코딩해야 한다.

Martin의 상사들은 조직의 모든 구성원이 이런 퍼즐을 풀 수 있어야 한다고 생각한다. 따라서 디코딩을 담당하는 프로그램 부분 역시 모든 칸이 채워진 퍼즐만 디코딩하면 된다.

Martin은 프로그래밍에 능숙하지 않으므로, 여러분에게 그런 프로그램을 작성해 달라고 부탁한다.

입력

첫 번째 줄에는 자연수 $M$과 $N$이 주어진다 ($M=1$ 또는 $M=2$, $1\le N\le30$). $M=1$이면 프로그램은 $N$개의 문자열을 스도쿠 퍼즐로 인코딩해야 하고, $M=2$이면 $N$개의 스도쿠 퍼즐을 다시 문자열로 디코딩해야 한다.

$M=1$이면 다음 $N$개 줄 중 $i$번째 줄에는 자연수 $l_i$와 문자열 $s_i$가 하나씩 주어진다 ($1\le|s_i|=l_i\le15$). 문자열 $s_i$는 영어 알파벳 소문자로만 이루어진다.

$M=2$이면 다음 $9N$개의 줄에 디코딩해야 하는 스도쿠 퍼즐을 나타내는 $9\times9$ 행렬 $N$개가 주어진다. 행렬은 항상 유효한 퍼즐이다. 즉, 문자 1부터 9로 이루어져 있고, 어떤 $3\times3$ 블록, 행, 열에서도 숫자가 중복되지 않는다.

출력

$M=1$이면 $9N$개의 줄에 입력의 문자열 $s_i$를 인코딩한 값을 나타내는 스도쿠 퍼즐 $N$개를 출력한다. 출력한 퍼즐은 문자 1부터 9로만 이루어져야 하며, 행, 열, $3\times3$ 블록에서 숫자가 중복되어서는 안 된다.

$M=2$이면 $N$개의 줄에 입력의 스도쿠 퍼즐을 디코딩한 문자열들을 출력한다.

서브태스크

여러분의 프로그램은 두 단계로 평가된다. 먼저 $M=1$인 공식 입력으로 실행된다. 프로그램의 출력이 $N$개의 유효한 행렬로 이루어진 수열이면, 두 번째 단계에서는 첫 번째 단계에서 출력한 행렬들을 입력으로 하여 프로그램을 다시 실행한다. 프로그램이 두 번째 단계에서 출력한 문자열들이 공식 입력의 문자열들과 같으면, 그 공식 입력에 대한 점수를 모두 받는다.

프로그램의 실행 시간은 두 평가 단계의 실행 시간을 합한 값이다.

예제

입력 1

1 1
6 sudoku

출력 1

139245678
628137459
457689123
214356897
375498216
896712345
541873962
763921584
982564731

입력 2

2 1
139245678
628137459
457689123
214356897
375498216
896712345
541873962
763921584
982564731

출력 2

sudoku