The Genome of Newton#79
On the planet Olympia, the study of the genomes of the inhabitants of the Olympia galaxy has been completed. It was found that the decoded genome can be represented as a multiset of integers (numbers may be repeated). In the genome of a gifted individual, among all numbers, there is exactly one that occurs an odd number of times—this number indicates a particular genetically determined talent.
The specialized equipment receives the genome as a collection of sets. Each set is defined by four integers: , , , . For each set, it includes consecutive integers starting from , then skips the next integers, then includes the next integers, and so on, until all numbers exceed . All numbers in a set do not exceed . For example, the set (s = 1, f = 10, a = 2, b = 1) contains the numbers 1, 2, 4, 5, 7, 8, 10; the set (s = 5, f = 50, a = 1, b = 19) contains .
Write a program that, given the description of the genome as such a collection of sets, determines whether there exists a number that occurs an odd number of times (and outputs it), or confirms that no such number exists.
The first line contains the number of sets (1 \leq N \leq 10\,000). Each of the next lines contains four integers , , , (1 \leq s, f, a, b < 10^9; \ s \leq f), describing a single set. It is guaranteed that there is at most one number in the genome that occurs an odd number of times.
Output the integer that occurs an odd number of times in the genome, or 0 if no such number exists.
Example 1