eolymp
bolt
Try our new interface for solving problems
Problems

The Genome of Newton

The Genome of Newton

Time limit 0.3 seconds
Memory limit 64 MiB

On a planet Olimpiya a study the genome of inhabitants of the Olympic galaxy is completed. It appeared that the genome which deciphered can be given as a set of integers which can repeat. In presentation of the genome of talented personality among other there is a one which meets one times and determines the number of the certain genetically conditioned talent.

The developed equipment gets presentation to the genome as a set of plurals of numbers. Every plural is set of four numbers s, f, a, b. There are a послідовних successive integers belong to such plural beginning from s, next b numbers is not belonged to the plural, followings and belong again, and etc. All of numbers in a plural are no more then f. For example, a plural (s = 1, f = 10, a = 2, b = 1) has numbers: 1, 2, 4, 5, 7, 8, 10, and plural (s = 5, f = 50, a = 1, b = 19) has numbers: 5, 25, 45.

Write the program, that after presentation to the genome as a set of plurals of numbers will set, whether his proprietor has some genetically conditioned talent, and will define his number.

Input data

There is the quantity of plurals N (1N10 000) in a set in the first line of input. Next N lines set plurals. Every plural is set of four numbers - s, f, a, b (1s, f, a, b < 10^9; s ≤ f). It is guaranteed, that no more presentation to the genome contains one number which meets just one time.

Output data

Print the number which meets odd number of times in genome presentation, or 0, if such number does not exist.

Examples

Input example #1
4
7 59 1 9
7 82 1 49
17 50 1 29
27 27 1 1
Output example #1
37
Author Taras Galkovskiy
Source 2008 XXI All-Ukrainian Informatics Olympiad, Lvov, April 5 - 11, Round 1