Otilia si Burbucel, fiind in fata unei gramezi de N pietre si neavand ce face, stabilesc regulile unui nou joc. Cei doi copii vor ca jocul sa fie simplu asa ca impun doar trei reguli:

1.  Primul jucator are voie sa ia din gramada cel mult K piese

2.  Cu exceptia primei mutari, fiecare jucator are voie sa ia maxim P*t pietre, unde t este numarul de pietre care au fost substituite din gramada la mutarea precedenta

3. Pierde cel care muta ultimul (cel care ia ultimele pietre din gramada)

Cei doi au jucat multe jocuri, Burbucel fiind intotdeauna cel care alege numerele N, K si P si Otilia primul jucator care muta. Otilia a observat ca alegerile lui Burbucel se repeta dupa M jocuri (alegerea numarul M+1 este identica cu alegerea numarul 1, alegerea numarul M+2 este identica cu alegerea numarul 2, etc.). Ea ar vrea sa stie daca poate castiga sau nu pentru fiecare dintre primele M alegeri ale lui Burbucel. Motivul este usor de intuit: Otilia nu vrea sa-i dea ocazia lui Burbucel sa castige asa ca va renunta pe jocurile unde nu are strategie de castig.

Cerinta

Scrieti un program care rezolva dilema Otiliei.

Date de intrare

Pe prima linie a fisierului otilia.in se afla M, numarul de alegeri ale lui Burbucel. Urmatoarele M linii contin cate trei numere, N, K si P reprezentand o alegere a lui Burbucel (N – numarul de pietre din gramada, K – numarul maxim de pietre pe care le poate lua Otilia la prima mutare, P – factorul cu care se inmulteste numarul de pietre luate la mutarea precedenta rezultand astfel numarul maxim de pietre care se pot substitui la mutarea curenta).

Date de iesire

Fisierul otilia.out contine M linii, pe linia i aflandu-se 1 daca Otilia castiga la alegerea numarul i a lui Burbucel sau 0 daca ea pierde  (alegerile sunt numerotate de la 1 la M in ordinea in care se gasesc in fisierul de intrare).

Restrictii

• 1 <= M <= 30 000
• 1 <= N <= 5 000 000
• 1 <= K <= N
• 1 <= P <= 10
• Pentru 50% din teste N <= 500 000 pentru toate alegerile lui Burbucel

Exemplu

Silviu Ionut Ganceanu
Universitatea Politehnica Bucuresti
Contact: tzi_ganci@hotmail.com