Заявление на гражданство
В Канаде, после получения статуса постоянного жителя, вы можете подать заявление на гражданство, если прожили в стране не менее 1095 дней (примерно 3 года) в течение последних 1460 дней (примерно 4 года) перед подачей заявления (день подачи заявления не учитывается). Время, проведенное за пределами Канады, не засчитывается как проживание в стране. Если вы находились в Канаде до получения статуса постоянного жителя (например, для учебы) в течение 1460-дневного периода, это время может быть засчитано наполовину, округляя вниз (например, если вы прожили 101 день, это будет засчитано как 50 дней), но не более 730 дней. Таким образом, дни проживания до получения статуса считаются как полдня, если они приходятся на период до получения статуса (но не более чем за 730 дней до), или как полный день, если они совпадают с датой получения статуса.
В этой задаче вам нужно определить первый день, когда можно подать заявление на гражданство.
Входные данные
Входные данные состоят из нескольких случаев. Первая строка каждого случая содержит начальную дату проживания в стране, вторая строка — дату получения статуса постоянного жителя. Третья строка содержит целое число N (0 ≤ N ≤ 100), указывающее количество поездок за пределы Канады. Каждая из следующих N строк содержит две даты, разделенные пробелом, указывающие дату начала и окончания (включительно) поездки за пределы Канады. То есть, вы находитесь за пределами Канады с даты начала по дату окончания.
Вы можете предположить, что начальная дата проживания не позже даты получения статуса. Также можно предположить, что дата начала каждой поездки не позже даты окончания, и ни одна поездка за пределы Канады не будет длиться более 200 дней. Ваши поездки не включают начальную дату проживания и дату получения статуса, и никакие две поездки не пересекаются. Никакие поездки не происходят до начальной даты проживания. Все даты даны в формате Месяц/День/Год и являются допустимыми, и ни одна дата во входных данных не будет раньше 1 января 1980 года или позже 31 декабря 2020 года.
Выходные данные
Для каждого случая выведите в одной строке дату первого дня (в том же формате, что и во входных данных), когда можно подать заявление на гражданство.