Guessing Game

Byteman and Bitman play the following game. Bitman secretly writes down a sequence of $1{,}000{,}000{,}000$ zeros and ones. Byteman's goal is to guess this sequence.

Byteman repeatedly asks Bitman questions of the form:

Is the sum of the subsequence that begins at the $b$-th element and ends at the $e$-th element of your sequence even or odd?

After playing for a while, Byteman began to suspect that Bitman was answering dishonestly. He would like to know how many of his questions, counting from the first, can still be answered consistently.

Write a program that computes the greatest number $m$ for which there exists a sequence of zeros and ones consistent with Bitman's answers to the first $m$ questions.

The first line contains one integer $n$ ($0 \le n \le 100{,}000$), the number of Byteman's questions.

Each of the following $n$ lines describes one question together with Bitman's answer as three integers $b$, $e$, and $s$ ($1 \le b \le e \le 1{,}000{,}000{,}000$, $s \in \{0, 1\}$) separated by single spaces. Here $b$ and $e$ are the positions of the first and last elements of the subsequence in that question. $s = 0$ means the answer was that the sum is even, and $s = 1$ means it is odd.

Output a single integer $m$: the greatest value such that a sequence of zeros and ones consistent with the first $m$ answers exists.