sudoku

Numim tablou Sudoku o matrice cu $n^2$ elemente ce conține doar cifrele $1$, $2$ și $3$ astfel încât în fiecare pătrat format din $2×2$ elemente alăturate să existe toate cele $3$ cifre și oricare două elemente alăturate pe linie sau pe coloană să fie distincte. Fiecărui tablou Sudoku $i$ se asociază un număr obținut prin scrierea cifrelor în ordine, începând cu prima linie.

De exemplu, tabloul Sudoku din imaginea alăturată are asociat numărul: 2132132132213211321321321.

Se definește șirul $S(n)$ ca fiind un șir ordonat, format din toate tablourile Sudoku cu $n^2$ elemente, {$s_1, s_2, s_3, \cdots$}. Pentru orice pereche $(s_i, s_j)$ din $S(n)$ cu $i \lt j$, numărul asociat tabloului Sudoku si este strict mai mic decât numărul asociat tabloului Sudoku $s_j$.

Pentru $n = 2$, șirul $S(2)$ conține, în ordine, tablourile Sudoku:

Cerință

Date fiind două numere naturale $n$ și $k$ să se determine:

• numărul tablourilor Sudoku din șirul $S(n)$;
• tabloul Sudoku aflat pe poziția $k$ în șirul $S(n)$.

Date de intrare

Fișierul sudoku.in conține pe prima sa linie două numere naturale $n$ și $k$ separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire sudoku.out va conține:

pe prima linie un număr natural ce reprezintă numărul tablourilor Sudoku din șirul $S(n)$
pe următoarele $n$ linii se găsesc câte $n$ cifre, separate prin câte un spațiu, ce reprezintă, în ordine, liniile tabloului Sudoku aflat pe poziția $k$ în șirul $S(n)$.

Restricții și precizări

• $2 \leq n \leq 32$;
• $1 \leq k \lt 10^{19}$;
• Pentru rezolvarea corectă a cerinței $1$ se acordă $20\%$ din punctaj, iar pentru rezolvarea corectă cerinței $2$ se acordă $80\%$ din punctaj.
• Acordarea punctajului pentru a doua cerință se face numai dacă în fișierul de ieșire există un răspuns pentru prima cerință, indiferent de corectitudinea acestuia.

Exemplul

sudoku.in

2 6

sudoku.out

12
2 1
3 2

Explicație

Șirul $S(2)$ conține $12$ tablouri Sudoku, pe poziția $6$ în șir aflându-se tabloul:

• $\begin{pmatrix} 2 & 1 \\ 3 & 2 \end{pmatrix}$