Sharp Eyes

A multiset of integers is described by several arithmetic progressions. A line A C B contributes every integer A, A+B, A+2B, ... that is not greater than C.

Across the whole multiset, at most one integer appears an odd number of times; every other integer appears an even number of times. Find the integer that appears an odd number of times.

The first line contains the number of progressions N, where 1 <= N <= 20,000.

Each of the next N lines contains three integers A C B. Each value is between 1 and 2,147,483,647, inclusive. A line means that every integer A + kB with k >= 0 and A + kB <= C is included in the multiset.

If an integer appears an odd number of times, print that integer and its multiplicity separated by a space.

If no such integer exists, print NOTHING.

For a value x, count how many generated elements are less than or equal to x. The prefix count is even before the odd-multiplicity value and odd from that value onward, so the parity of this prefix count can be used with binary search.