Fişierul intrare/ieşire:	chocolate.in, chocolate.out	Sursă	ad-hoc
Autor	Din Folclor	Adăugată de	Mihai Calancea •klamathix
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Chocolate

Fie o tableta de ciocolata de N linii si M coloane. Bucata de ciocolata de pe pozitia (X, Y) este otravita. Consideram urmatorul joc:

Exista 2 jucatori care muta alternativ.
In momentul in care un jucator se afla la mutare, acesta isi alege un numar K nenul si face unul din urmatorii pasi:

1. Mananca primele K linii din tableta.
2. Mananca ultimele K linii din tableta.
3. Mananca primele K coloane din tableta.
4. Mananca ultimele K coloane din tableta.

Jucatorul care mananca bucata de ciocolata otravita este considerat pierzator.

Considerand ca cei doi joaca optim, exista strategie sigura de castig pentru jucatorul care face prima mutare?

Date de intrare

Fişierul de intrare chocolate.in va contine pe prima linie un numar T.
Urmatoarele T linii contin cate un caz, de forma: N M X Y.

Date de ieşire

Fişierul de ieşire chocolate.out va cotine exact T linii. Linia i va contine numarul 1 daca jucatorul care muta primul are strategie sigura de castig pentru jocul respectiv sau 0 in caz contrar.

Restricţii

• 1 ≤ T ≤ 10
• 3 ≤ N, M ≤ 1000000
• Pentru teste in valoare de 60 de puncte: X = 1, Y = 1. Cu alte cuvinte, bucata otravita se afla in coltul tabletei.
• Pentru restul testelor (in valoare de 40 de puncte), X si Y se afla STRICT in interiorul tabletei.

Exemplu

Explicaţie

In primul caz ciocolata este formata doar din bucata otravita. In mod evident, primul jucator pierde, fiindca este obligat sa manance cel putin o linie sau o coloana.

In cel de al doilea caz, primul jucator poate manca ultimele 2 coloane ale tabletei. Cel de-al doilea jucator va pierde, din acelasi motiv pentru care primul jucator pierde primul caz.

Cel de-al treilea caz este putin mai complicat :).

Cum se trimit solutii?