eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Геном Ньютона

Геном Ньютона

Лимит времени 0.3 секунд
Лимит использования памяти 64 MiB

На планете Олимпия завершено изучение генома обитателей Олимпийской галактики. Оказалось, что расшифрованный геном может быть представлен в виде набора целых чисел, которые могут повторяться. В представлении генома талантливой личности содержится среди прочих единственное число, которое встречается нечетное количество раз и задает номер определенного генетически обусловленного таланта.

Разработанное оборудование получает представление генома в виде набора множеств чисел. Каждое множество задается четверкой чисел 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 < 10^9; s ≤ f). Гарантируется, что представление генома содержит не больше одного числа, которое встречается нечетное количество раз.

Выходные данные

Вывести целое число, которое встречается нечетное количество раз в представлении генома, либо 0, если такого числа не существует.

Пример

Входные данные #1
4
7 59 1 9
7 82 1 49
17 50 1 29
27 27 1 1
Выходные данные #1
37
Автор Тарас Галковский
Источник 2008 XXI Всеукраинская олимпиада по информатике, Львов, Апрель 5 - 11, тур 1