trim

Pentru un număr natural nenul $x$ reprezentat pe $N$ biți definim operația $trim(x)$ prin care eventualii biți de $0$ de la stânga și de la dreapta numărului se elimină, nu și cei din interior. De exemplu, pentru $n = 6$ şi $x = 4 = 000100_2$, $trim(4) = 1_2$; dacă $n = 6$ şi $x = 10 = 001010_2$ atunci $trim(10) = 101_2 = 5$.

Să considerăm un număr natural $N$ şi şirul numerelor naturale cuprinse între $1$ şi $2^N -1$. Aceste numere se reprezintă pe exact $N$ biți. Fiecărui număr din șir i se aplică operația $trim$. Șirul se ordonează apoi după două criterii: primul este numărul biților de $1$, iar dacă două numere au același număr de biți de $1$, se vor ordona după al doilea criteriu, crescător după valori (în urma operației $trim$). La final biții din fiecare număr se concatenează. De exemplu, dacă $N = 3$, atunci șirul inițial este $1, 2, 3, 4, 5, 6, 7$. Se aplică operația $trim$ și se obține șirul: $1, 1, 3, 1, 5, 3, 7$. Ordonând mai întâi după numărul de biți de 1 și în caz de egalitate crescător se obține $1, 1, 1, 3, 3, 5, 7$. Concatenând biții numerelor se obține 1111111101111, secvență cu pozițiile de la stânga la dreapta numerotate de la $1$.

Cerință

Date numerele naturale $N$ și $T$, precum și numerele naturale $p_1, p_2, \ldots, p_T$, să se determine ce valoare are bitul de la acele poziții în șirul binar obținut?

Date de intrare

Fișierul de intrare conține pe prima linie numerele naturale $N$ și $T$, iar pe a doua linie, separate prin spații, numerele naturale $p_1, p_2, \ldots, p_T$.

Date de ieșire

Fișierul de ieșire va conține o succesiune de $T$ biți, fără spații, reprezentând răspunsul la fiecare întrebare.

Restricții și precizări

• $1 \leq N \leq 100$
• $2 \leq T \leq 100\ 000$
• $1 \leq p_1, p_2, \ldots, p_T \leq 10^{18}$
• Se garantează că $p_1, \ldots, p_T$ nu sunt mai mari decât numărul de biți din secvența creată.

Exemple

trim.in

3 10
7 1 2 3 4 5 6 8 9 10

trim.out

1111111101

Considerăm inițial numerele de la $1$ la $7$. După aplicația operației $trim$ și sortare, ele devin $1_2, 1_2, 1_2, 11_2, 11_2, 101_2, 111_2$. Așadar, după concatenare avem 1111111101111, iar elementele de pe pozițiile cerute sunt cele din exemplu.

trim.in

5 10
1 2 3 4 15 23 19 45 66 99

trim.out

1111011111

Considerăm inițial numerele de la $1$ la $31$. După aplicația operației $trim$ și sortare, ele devin
$1_2, 1_2, 1_2, 1_2, 1_2, 11_2, 11_2, 11_2, 11_2, 101_2, 101_2, 101_2, 1001_2, 1001_2, 10001_2 111_2, 111_2, 111_2, \\ 1011_2, 1011_2, 1101_2, 1101_2, 10011_2, 10101_2, 11001_2, 1111_2, 1111_2, 10111_2, 11011_2, 11101_2, 11111_2$.

Așadar, după concatenare avem 1111111111111101101101100110011000111111111110111011110111011001110101110011111111110111110111110111111 iar elementele de pe pozițiile cerute sunt cele din exemplu.