Геном Ньютона
Геном Ньютона
На планете Олимпия завершено изучение генома обитателей Олимпийской галактики. Оказалось, что расшифрованный геном может быть представлен в виде набора целых чисел, которые могут повторяться. В представлении генома талантливой личности содержится среди прочих единственное число, которое встречается нечетное количество раз и задает номер определенного генетически обусловленного таланта.
Разработанное оборудование получает представление генома в виде набора множеств чисел. Каждое множество задается четверкой чисел 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 ≤ 10000
) в наборе. Последующие 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