Under construction

Still being built. Things may change

King's Heir

Interview

Time limit2sMemory limit256 MB

Summary
Given the king's death date and each son's birth date, find the youngest son whose 18th birthday is on or before the death date, or print -1.
Level

Easy3 of 10

Topics
Implementation, Math
Solved
No attempts yet

Problem

King Fert XIII died suddenly. The people of the Flatland Kingdom are waiting for a new king, but there is a problem. Fert had far too many sons.

Fert had nn sons, and he loved every newborn son more than all of his earlier sons. Each time a son was born, he wrote a new testament naming the newborn as his heir.

Only a son who is at least 18 years old at the moment of the king's death can become the new king. The ministers are trying to find the correct new king and keep getting it wrong. Help them.

Input

The first line contains three integers dd, mm and yy, the day, the month and the year of the king's death, with 1≤d≤311 \le d \le 31, 1≤m≤121 \le m \le 12 and 1≤y≤99991 \le y \le 9999. Day dd is guaranteed to exist in month mm. Every month in Flatland has the same number of days as in our calendar, except that the Flatland calendar has no leap years, so February always has 28 days.

The second line contains the number of the king's sons nn (1≤n≤1001 \le n \le 100). The ii-th of the following nn lines contains three integers did_i, mim_i and yiy_i, the birth date of the ii-th son. All dates are correct, and no son was born on or after the day of the king's death. The king had no twins, so no two sons share a birth date.

Output

Print one integer, the number of the son who becomes the king, or −1-1 if no son is at least 18 years old.

The sons are numbered from 1 to nn in the order they appear in the input. The youngest son who is at least 18 years old at the moment of the king's death becomes the king. A son whose 18th birthday falls exactly on the day of the king's death can become the king.

Examples2

  1. Example 1

    Input
    22 10 2016
    7
    28 2 1999
    22 7 1995
    21 10 1998
    23 10 1998
    3 9 2000
    1 4 2013
    17 12 2004
    
    Expected output
    3
    
  2. Example 2

    Input
    22 10 2016
    1
    28 2 1999
    
    Expected output
    -1