Zgadywanka

Limit pamięci: 32 MB

Bajtazar gra z Bajtonim w następującą grę. Bajtoni losuje sobie ciąg składający się z 0 i 1 o długości cyfr. Zadaniem Bajtazara jest odgadnięcie ciągu, który wylosował Bajtoni. W tym celu może zadawać pytania typu: "Czy suma wyrazów ciągu od -tego do -tego jest parzysta?". Bajtoni chętnie udzielał odpowiedzi, jednak po pewnym czasie Bajtazar zaczął podejrzewać, że jego kolega oszukuje. Chciałby sprawdzić kiedy Bajtoni udzielił pierwszej odpowiedzi sprzecznej z poprzednimi, dlatego zwrócił się do Ciebie o pomoc.

Zadanie

Napisz program, który:

• wczyta opis pytań zadawanych przez Bajtazara oraz odpowiedzi Bajtoniego,
• obliczy największe takie , dla którego odpowiedzi Bajtoniego na pierwszych pytań są niesprzeczne,
• wypisze wynik na standardowe wyjcie.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (), oznaczajca liczbę pytań Bajtazara. Każdy z kolejnych wierszy zawiera opis jednego pytania Bajtazara oraz odpowiedzi Bajtoniego w postaci trzech liczb całkowitych , i (). Liczy i oznaczają, że Bajtazar zapytał o sumę wyrazów ciągu od -tego do -tego włącznie. Jeśli , to Bajtoni odpowiedział, że suma ta jest parzysta. Jeśli , Bajtoni powiedział, że suma jest nieparzysta.

Wyjście

Twój program powinien wypisać w pierwszym i jedynym wierszu standardowego wyjścia jedną liczbę całkowitą - największe takie , dla którego odpowiedzi Bajtoniego na pierwszych pytań są niesprzeczne.

Przykład

Dla danych wejściowych:

5
3 3 0
2 5 1
1 4 0
2 5 0
1 5 1

poprawną odpowiedzią jest:

3

Autor zadania: Jakub Łącki (zapożyczenie).