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

Разработанное оборудование получает представление генома в виде набора множеств чисел. Каждое множество задается четверкой чисел 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, если такого числа не существует.