ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1759. Long-Livers

Time limit: 0.5 second
Memory limit: 64 MB
British scientists have compiled a list of holders of the title “the oldest person currently alive.” For each of the long-livers, this list contains their date of birth and the period during which they were the oldest person alive in the world. Unfortunately, the list does not mention which of the long-livers lived the longest life, but it is not so difficult to determine such a person by the given data.

Input

The first line contains the number n of long-livers in the list (1 ≤ n ≤ 100). The list is given in the following n lines in the form of triples of dates d1, d2, d3, where d1 is the date of birth of a long-liver, d2 is the date starting from which this person was the oldest person alive in the world, and d3 is the date of death of this person. All the dates are given in the format “dd.mm.yyyy” and lie in the range from 01.01.1800 to 31.12.2009 (the British scientists use the Gregorian calendar). The dates in one line are separated by exactly one space. It is known that the date d2 is always greater than the date d1, and d3 is greater than d2. The date d2 always coincides with the date d3 from the preceding line of the list. All the dates of birth and all the dates of death are different.

Output

Output the number of the long-liver from the list who lived longer than the others. The lifetime should be measured in days, including both the day of birth and the day of death. The number of the long-liver must lie in the range from 1 to n. If there are several long-livers holding the record, output the number of the person who died earlier.

Sample

inputoutput
4
10.10.1873 27.12.1987 11.01.1988
18.11.1874 11.01.1988 14.02.1991
21.02.1875 14.02.1991 04.08.1997
29.08.1880 04.08.1997 16.04.1998
3

Notes

In the Gregorian calendar, the length of a non-leap year is 365 days and the length of a leap year is 366 days. Whether a year is a leap year is determined by the following rule:
  • A year with a number divisible by 4 is a leap year.
  • Further, a year with a number divisible by 100 is, by way of exception, a non-leap year.
  • Further, a year with a number divisible by 400 is still a leap year.
Problem Author: Alexander Ipatov
Problem Source: XI USU Open Personal Contest (March 13, 2010)