The Inspector's Odd-or-Even Bulb Notes

A festival strip holds light bulbs at positions 1, 2, ..., 10**9. Each bulb is either lit or dark, but nobody wrote down which. An inspector walked the strip and made a list of notes: claims[i] = [l, r, p] says that among the bulbs at positions l to r (inclusive) the number of lit bulbs is even if p == 0 and odd if p == 1.

Some notes may be wrong. Return the largest k such that the first k notes, claims[0] to claims[k - 1], can all be true at the same time for some choice of lit and dark bulbs. If every note fits, return len(claims).

Examples

Input:  claims = [[1, 3, 1], [4, 6, 0], [1, 6, 1], [2, 6, 0], [1, 1, 0]]
Output: 4
Explanation: the first four notes can all hold (for example only bulb 1 lit).
Note 4 says bulb 1 is dark, so bulbs 2..6 and bulbs 1..6 would hold the
same number of lit bulbs; notes 2 and 3 say one count is even and the other odd.

Input:  claims = [[5, 5, 1], [5, 5, 0], [1, 2, 0]]
Output: 1

Input:  claims = []
Output: 0

Constraints

• 0 <= len(claims) <= 6 * 10**4
• 1 <= l <= r <= 10**9, p is 0 or 1
• Target: about O(m * alpha(m)) time for m notes. Positions are far too large for an array over the strip, and re-checking all earlier notes each time is too slow.

Goals

• Turn a statement about a range into a statement about two prefix values
• Store the parity from each node to its parent and keep it correct through compression
• Detect the first statement that contradicts the earlier ones