Задача №111127. Геном Ньютона
На планете Олимпия завершено изучение генома обитателей Олимпийской галактики. Оказалось, что расшифрованный геном может быть представлен в виде набора целых чисел, которые могут повторяться. В представлении генома талантливой личности содержится среди прочих единственное число, которое встречается нечетное количество раз и задает номер определенного генетически обусловленного таланта. Разработанное оборудование получает представление генома в виде набора множеств чисел. Каждое множество задается четверкой чисел s, f, a, b. Такому множеству принадлежат a последовательных целых чисел начиная с s, следующие b чисел множеству не принадлежат, следующие a снова принадлежат, и т.д. Все числа множества не превышают f. Например, множество (s = 1, f = 10, a = 2, b = 1) содержит числа {1, 2, 4, 5, 7, 8, 10}, а множество (s = 5, f = 50, a = 1, b = 19) числа {5, 25, 45}. Напишите программу, которая по представлению генома в виде набора множеств чисел установит, обладает ли его владелец каким-то генетически обусловленным талантом, и определит его номер.
Первая строка входных данных содержит количество множеств N (1 ≤ N ≤ 200 000) в наборе. Последующие N строк задают сами множества. Каждое множество задается четверкой чисел — s, f, a, b, (1 ≤ s, f, a, b < 109, s ≤ f). Гарантируется, что представление генома содержит не больше одного числа, которое встречается нечетное количество раз.
Единственная строка выходного файла должна содержать целое число, которое встречается нечетное количество раз в представлении генома, либо 0, если такого числа не существует.
4
7 59 1 9
7 82 1 49
17 50 1 29
27 27 1 1
37