Citizenship Application

In Canada, once you have landed as a permanent resident, you may apply for citizenship if, during the 1460 days (about 4 years) immediately before the day you apply, you have lived in Canada for at least 1095 days (about 3 years). The day of application itself is not counted.

Any day spent travelling outside Canada does not count as a day of living in Canada.

If, during that 1460-day window, you were already living in Canada before you landed as a permanent resident (for example, as a student), then up to 730 days of that pre-landing time — that is, time no more than 730 days before the landing date — counts as half, rounded down. For example, 101 days of pre-landing residence count as 50 days.

Put another way, a day of residence before the landing date counts as half a day (as long as it is no more than 730 days before landing), while the landing date itself counts as a full day.

Your task is to determine the first day on which an application for citizenship can be made.

The input consists of several test cases and is read until end of file.

For each case:

• The first line contains the starting date of residence in the country.
• The second line contains the landing date as a permanent resident.
• The third line contains an integer $N$ ($0 \le N \le 100$), the number of trips taken outside Canada.
• Each of the next $N$ lines contains two dates separated by a space: the start and end date (inclusive) of a trip outside Canada. You are considered to be outside Canada from the start date through the end date.

You may assume the starting date of residence is no later than the landing date, that each trip's start date is no later than its end date, and that no trip lasts longer than 200 days. No trip includes the starting date of residence or the landing date, no two trips overlap, and no trip begins before the starting date of residence.

All dates are given as Month/Day/Year, are valid, and fall between January 1, 1980 and December 31, 2020 inclusive.

For each case, print on its own line the first date (in the same Month/Day/Year format as the input) on which an application for citizenship can be made.