veverite

Două veverițe gemene au descoperit un depozit de alune care are o formă foarte ciudată. Mai precis, depozitul are forma unei matrice $N \times 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 cameră 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ță

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 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 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

• $3 \leq N \leq 9$ și $N$ este impar.
• $1 \leq Q \leq 1\ 000$.
• $1 \leq P_i \leq maxP$, unde $maxP$ este numărul maxim de trasee posibile pentru $N$.

Exemple

veverite.in

5 3
1
2
3

veverite.out

000031111300
000031303112
000033311120

veverite.in

9 1
12345

veverite.out

0000311113333333000211200000022213312213