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 cu 0.
• Dacă merge spre camera din stânga, din camera (L,C) în camera (L,C-1), notează trecerea cu 1.
• Dacă merge spre camera de sus, din camera (L,C) în camera (L-1,C), notează trecerea cu 2.
• Dacă merge spre camera de jos, din camera (L,C) în camera (L+1,C), notează trecerea cu 3.

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, unde maxP este numărul maxim de trasee posibile pentru N.
• 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