Fişierul intrare/ieşire:	aliniate.in, aliniate.out	Sursă	Algoritmiada 2019 Runda Finala
Autor	Alexandru Petrescu, Tamio-Vesa Nakajima	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	0.5 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Aliniate

In arhitectura sistemelor, conceptul de "aliniare" a tipurilor de date este relevant; mai exact, un tip de date primitiv trebuie sa fie pozitionat la o adresa multiplu a lungimii sale (de exemplu, un intreg de 4 bytes trebuie sa fie pe o pozitie multiplu de 4). Asta e chiar util in unele implementari (de exemplu, un nod dintr-un std::set trebuie sa se gaseasca pe o pozitie multiplu de 8; astfel, pointerii din acel nod catre alti fii mereu au 0 pe ultimii 3 biti, iar implementarea din stl al acestui container foloseste acei biti pentru a stoca informatii). Aceasta problema foloseste acest concept.

Patronul firmei GazAliniat vede valoare doar in lucrurile aliniate. El considera ca o subsecventa [x, y], de lungime putere a lui 2, este aliniata daca si numai daca y - x + 1 il divide pe x. El are in fata lui un sir de 10⁹ valori intregi, indexate de la 0. El alege cel mult 100.000 subsecvente aliniate, si calculeaza produsul valorilor din din acele subsecvente, modulo 2³², notand aceste valori. Din nefericire, adversarul sau Hideyoshi, seful Universitatii Petrol si Gaze a metropolei B i-a furat secventa, si a modificat cateva dintre produsele notate. Patronul se intreaba acum: "Boss, oare exista un mod de a alege cele 10⁹ valori astfel incat produsele sa coincida cu cele notate?"

Date de intrare

Fişierul de intrare aliniate.in contine, pe primul rand, numarul T de teste din fisierul dat. Urmeaza cele T teste.
Un test va contine, pe primul rand, numarul N de produse notate.
Vor urma pe urmatoarele N numere cate un triplet x y z care semnifica: "produsul valorilor de la x la y, modulo 2³², este z".

Date de ieşire

În fişierul de ieşire aliniate.out va contine T randuri, fiecare continand rezultatul pentru cate un test, in ordine.
Pentru fiecare test, daca exista un sir de 10⁹ valori care satisfac restrictiile date, sa se afiseze 1; altfel, sa se afiseze 0.

Restricţii

• 1 ≤ T ≤ 10.
• 0 ≤ x ≤ y ≤ 10⁹
• Subsecventele date sunt aliniate.
• 0 ≤ z < 2³².
• 1 ≤ N ≤ 50.000.
• Suma N-urilor in toate testele dintr-un fisier este cel mult 100.000.
• Pentru 5 puncte, subsecventele din input nu se intersecteaza, si N ≤ 100.
• Pentru alte 15 puncte, N ≤ 100.
• Pentru alte 30 puncte, valorile din sir sunt impare.
• Primul test din feedback corespunde primului subtask, cel de al doilea test din feedback corespunde celui de al doilea subtask, cel de al treilea si cel de al patrulea test din feedback corespunde celui de al treilea subtask.

Exemplu

Explicaţie

Restrictiile din primul test sunt satisfacute prin a alege valorile 1, 2, 1, ....

Cum se trimit solutii?