The Genome of Newton
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.
The Task
Write the program GENOME, 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.
Specifications
Input
There is the quantity of plurals N (1 ≤ N ≤ 10 000) in a set in the first line of inputfile. Next N lines set plurals. Every plural is set of four numbers – s, f, a, b, (1 ≤ s, f, a, b < 109; s ≤ f). It is guaranteed, that no more presentation to the genome contains one number which meets just one time.
Output
There is one integer in the one line of outputfile. It is number which meets just one time in presentation to the genome, or 0, if such number does not exist.
The Comment
Names of input and output files have to be written including to the requirements of the checking system.
Problem information
Time Limit: 0.3 secondsMemory Limit: 64 MB
Balls for the passed test: 9.09091
Complexity: 67% 18/54
Example
Example input4 7 59 1 9 7 82 1 49 17 50 1 29 27 27 1 1 |
Example output37 |
| ← Islands | Problems | Discounts → |