După șase ani de lucru, Charles a terminat de curățat instalațiile pentru producerea negrului de fum din Copșa Mică. Pentru a se ține departe de mesele de Blackjack, el s-a angajat la CERN, unde va lucra la noul accelerator de particule numit Even Larger Hadron Collider (ELHC).
ELHC are forma unui tunel circular cu o circumferință de kilometri, fiind un număr prim. De-a lungul tunelului sunt plasați senzori numerotați de la la , distanța dintre doi senzori consecutivi fiind de exact kilometru.
Un experiment efectuat în ELHC constă în studierea unei particule de tip , . Dacă această particulă este ridicată la nivelul de energie și este lansată din dreptul senzorului în direcția senzorului , ea va parcurge exact kilometri prin tunel și apoi se va dezintegra, declanșând în acel moment senzorul în dreptul căruia are loc dezintegrarea particulei.
Se consideră că experimentul are date complete dacă, lansând particule de tip ridicate la toate nivelurile de energie de la la , este posibil să declanșăm toți senzorii s numerotați cu valori între și , adică toți senzorii din tunel mai puțin senzorul .
Cerință
Dându-se perechi de numere și , determinați dacă experimentul pentru studierea particulei de tip într-un tunel de circumferință produce date complete.
Date de intrare
Fișierul de intrare elhc.in
conține pe prima linie un număr , reprezentând numărul de experimente care vor fi efectuate. Pe fiecare din următoarele linii se află câte două numere și separate printr-un spațiu, reprezentând efectuarea unui experiment cu o particulă de tip într-un tunel de circumferință .
Date de ieșire
În fișierul de ieșire elhc.out
se va afla o singură linie cu biți scriși unul după altul, adică fără spații între ei. Al -ulea bit este dacă pentru cel de-al -lea experiment putem obține date complete, și în caz contrar.
Restricții și precizări
- ;
- ;
- este un număr prim;
- Subtask 1 - 7 puncte - ;
- Subtask 2 - 14 puncte - ;
- Subtask 3 - 53 puncte - ;
- Subtask 4 - 26 puncte - nu există restricții suplimentare.
Exemplu
elhc.in
6
2 3
3 5
2 7
3 7
3 11
5 11
elhc.out
110100
Explicație
Fișierul de intrare conține experimente.
A doua particulă are tipul și va fi lansată printr-un tunel de circumferință , cu senzori numerotați de la la . Ridicată la nivelurile de energie , , , respectiv , și lansată de fiecare dată din dreptul senzorului , particula va călători , , , respectiv de kilometri și va declanșa senzorii , , , respectiv . Aceștia sunt toți senzorii pe care trebuie să-i declanșăm, prin urmare experimentul produce date valide, deci al doilea bit din șirul afișat este .
A treia particulă are tipul și va fi lansată printr-un tunel de circumferință . Ridicată la nivelurile de energie , , , , , respectiv , și lansată de fiecare dată din dreptul senzorului , particula va declanșa senzorii , , , , , respectiv . Deoarece nu declanșăm senzorii , și , experimentul nu are date complete, deci al treilea bit din șirul afișat este .