Guessing Game

Memory limit: 32 MB

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:

• reads a description of Byteman's questions and Bitman's answers,
• computes the greatest number , for which Bitman's answers for the first questions are consistent.

Input

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.

Output

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.

Example

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.