A și B participă la un joc cu următoarele reguli:

• întotdeauna începe jucătorul A;
• el primește un număr natural n mai mare decât 1;
• jucătorul care este la mutare poate să scadă 1 din număr, sau să îl împartă la 2 (rezultatul fiind partea întreagă a împărțirii), apoi acest număr este dat adversarului, care va proceda la fel;
• jocul se va termina atunci când un jucător a ajuns la numărul 1.

Avem două tipuri de joc, în funcție de cum se termină:
1. Câștigă cel care primește de la adversar numărul 1;
2. Pierde cel care primește de la adversar numărul 1.

Un meci este format din mai multe game-uri consecutive, toate fiind de același tip. Vom considera, că cei doi jucători cunosc acest principiu înainte de începerea meciului și că vor juca optim de fiecare dată. De exemplu, dacă jocul este de tipul 1 (câștigă cel care primește 1) și game-ul începe cu valoarea n = 4, atunci A va câștiga, pentru că împarte la 2, iar B indiferent că scade 1 sau împarte la 2, îi va da lui A numărul 1, deci A va câștiga.
Dacă jocul este de tipul 2 și game-ul începe cu valoarea n = 4, atunci A va pierde, pentru că indiferent că scade 1 și îi dă lui B numărul 3, sau împarte la 2 și îi dă lui B numărul 2, B va împărți acest număr la 2 (3 / 2 = 1, 2 / 2 = 1) și îi va da lui A numărul 1, deci A va pierde.

Cerința

Cunoscând tipul T al jocului, numărul G al game-urilor, respectiv valoarea de pornire pentru fiecare game, să se răspundă pentru fiecare caz în parte, dacă jucătorul A va câștiga (1) sau va pierde (0).

Date de intrare

Fișierul standard de intrare va conține pe prima linie două numere naturale T și G separate prin spațiu, reprezentând tipul tuturor jocurilor (1 sau 2) respectiv numărul de game-uri. Următoarele G linii vor conține câte un număr natural ce reprezintă câte o valoare de pornire.

Date de ieșire

Fișierul standard de ieșire va conține G linii, pe fiecare linie se va scrie valoarea 1 – dacă numărul este câștigător pentru jucătorul A, sau valoarea 0 – dacă numărul este pierzător pentru jucătorul A, în ordinea citirii valorilor din fișierul de intrare.

Restricții și precizări

• T poate fi 1 sau 2;
• 0 < G < 10;
• 1 < valoare de pornire < 2.000.000.000.

Exemplul 1:

Intrare

1 4
2
3
4
2019

Ieșire

0
1
1
1

Explicație

avem joc de tipul T = 1,
meciul este format din G = 4 game-uri
2 – pierzător pentru A (0)
3 – câștigător pentru A (1)
4 – câștigător pentru A (1)
2019 – câștigător pentru A (1)

Exemplul 2:

Intrare

2 4
2
3
4
123456789

Ieșire

1
1
0
1

Explicație

avem joc de tip T = 2 și G = 4
2 – câștigător
3 – câștigător
4 – pierzător
123456789 – câștigător