Alice and Bob's Parity Game

Alice and Bob are playing a game. Bob writes down a binary sequence consisting of 0's and 1's. Alice then asks Bob several questions. In each question, Alice selects a segment of the sequence from position L to R (1-indexed) and asks whether the number of 1's in that segment is odd or even. Bob answers with 0 (for even) or 1 (for odd).

Define a function \(f(i)\) as the parity (0 or 1) of the number of 1's among the first \(i\) numbers in the sequence. Then the answer to a query with parameters \(L\) and \(R\) gives the constraint \[ f(R)-f(L-1)\equiv p \pmod{2}, \] where \(p\) is 0 for even and 1 for odd.

Alice wants to verify Bob's answers. She considers the queries sequentially and finds the earliest query such that there exists a binary sequence satisfying all the previous queries but no binary sequence can satisfy all the previous queries together with the current one. Your task is to help Alice: Determine the index (1-indexed) of the first query that is inconsistent with the previous answers. If all queries are consistent, output -1.

inputFormat

The first line contains an integer \(n\) (the number of queries). Each of the next \(n\) lines contains three integers \(L\), \(R\) and \(p\) where \(1 \le L \le R\) and \(p\) is either 0 or 1 representing the parity (0 for even, 1 for odd) of the sum of the segment from position \(L\) to \(R\).

outputFormat

Output a single integer: the index (1-indexed) of the first query that is inconsistent with the previous ones. If all queries are consistent, output -1.

sample

3
1 1 0
1 2 1
2 2 1

-1