Două veverițe gemene au descoperit un depozit de alune care are o formă foarte ciudată. Mai precis, depozitul are forma unei matrice N x N
cu N
impar. Fiecare poziție din matrice este o cameră și în fiecare cameră se află câte o alună. Camerele sunt numerotate cu numărul de linie și numărul de coloană. Prima veveriță, pe numele ei Chip, se găsește inițial în camera (1,1)
, iar a doua, pe numele ei Dale, în camera (N,N)
. Veverițele vor să culeagă toate alunele și să se întâlnească în camera din centrul depozitului. Pentru aceasta, ele vor parcurge camerele trecând din una în alta fără să treacă vreodată printr-o cameră prin care a mai trecut una dintre ele. Ele se pot deplasa dintr-o cameră în alta (evident, fără să iasă din depozit și fără să intre într-o camera deja vizitată). Când trece dintr-o cameră într-alta, Chip își notează traseul astfel:
- Dacă merge spre camera din dreapta, din camera
(L,C)
în camera(L,C+1)
, notează trecerea cu0
. - Dacă merge spre camera din stânga, din camera
(L,C)
în camera(L,C-1)
, notează trecerea cu1
. - Dacă merge spre camera de sus, din camera
(L,C)
în camera(L-1,C)
, notează trecerea cu2
. - Dacă merge spre camera de jos, din camera
(L,C)
în camera(L+1,C)
, notează trecerea cu3
.
Interesant este că la orice trecere a lui Chip dintr-o cameră în alta, Dale se va muta exact în sens opus, adică:
- Dacă Chip merge spre dreapta, Dale merge spre stânga.
- Dacă Chip merge spre stânga, Dale merge spre dreapta.
- Dacă Chip merge în sus, Dale merge în jos.
- Dacă Chip merge în jos, Dale merge în sus.
Meticulos, Chip își calculează și își notează în ordine lexicografică toate traseele posibile prin care pot fi culese toate alunele din depozit. De exemplu, pentru N = 9
, traseul de pe poziția P = 12345
este notat astfel:
0000311113333333000211200000022213312213
și corespunde schemei de mai jos:
Cerința
Cunoscând N
, să se răspundă la Q
întrebări de forma: “Ce traseu a notat Chip pe poziția P
?”
Date de intrare
Fișierul de intrare veverite.in
conține pe prima linie numerele N
și Q
cu semnificația de mai sus. Pe următoarele Q
linii se găsesc întrebările. Astfel, pe linia i + 1
se găsește un singur număr P[i]
.
Date de ieșire
Fișierul de ieșire veverite.out
va conține Q
linii. Fiecare linie conține un șir de caractere 0, 1, 2 sau 3, neseparate prin spațiu. Șirul de pe linia i
va conține codificarea traseului lui Chip corespunzător poziției P[i]
.
Restricții și precizări
3 ≤ N ≤ 9
N
este impar.1 ≤ Q ≤ 1.000
1 ≤ P[i] ≤ maxP
, undemaxP
este numărul maxim de trasee posibile pentruN
.- Pentru 4 puncte,
N = 3
- Pentru 7 puncte,
N = 5
- Pentru 8 puncte,
N = 7
,P[i] ≤ 10
- Pentru 13 puncte,
N = 7
,P[i] ≤ 564
- Pentru 19 puncte,
N = 9
,P[i] ≤ 10
- Pentru 21 puncte,
N = 9
,P[i] ≤ 1.000
- Pentru 28 puncte,
N = 9
,P[i] ≤ 93.866
Exemplul 1:
veverite.in
5 3 1 2 3
veverite.out
000031111300 000031303112 000033311120
Exemplul 2:
veverite.in
9 1 12345
veverite.out
0000311113333333000211200000022213312213