W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Byteman is playing the following game with Bitman. Bitman writes down a sequence consisting of zeros and ones. Byteman's task is to guess Bitman's sequence. He can achieve this goal by asking Bitman questions of the form: 'Is the sum of a subsequence of your sequence, that begins at the -th element and ends at the -th element of the sequence, even or odd?'. After playing the game for some time, Byteman started suspecting that Bitman was cheating. He would like to know at which moment did Bitman first answer his question in an inconsistent way, so he asked you for help.
Write a program which:
The first line of the input contains one integer (), the number of Byteman's questions. Each of the following lines describes one question with the corresponding Bitman's answer in the form of three integers , and (, ), separated by single spaces. and are the indices of the first and the last element of the subsequence in Byteman's question. means that Bitman answered that the sum was even and that it was odd.
The first and only line of the output should contain one integer, the greatest value of such that there exists a sequence of zeros and ones that is consistent with Bitman's answers to the first Byteman's questions.
For the input data:
5 3 3 0 2 5 1 1 4 0 2 5 0 1 5 1
the correct result is:
3
An example of a sequence consistent with three first questions from the sample input is .
Task author: Jakub Lacki.