Заява на отримання громадянства#2758

Заява на отримання громадянства

1 секунда

64 мегабайти

Дуже легка

У Канаді після отримання статусу постійного мешканця ви можете подати заяву на громадянство. Для цього необхідно прожити в Канаді щонайменше $1095$ днів (близько $3$ років) протягом $1460$ днів (близько $4$ років), що безпосередньо передують даті подання заяви (сама дата подання не враховується). Будь-які дні, проведені поза межами Канади, не зараховуються до вимоги проживання. Крім того, якщо ви проживали в Канаді (наприклад, навчалися) до отримання статусу постійного мешканця протягом зазначених $1460$ днів (за умови, що це було максимум за $730$ днів до дати отримання статусу), ці дні до отримання статусу зараховуються як половина днів, заокруглена вниз (наприклад, $101$ день рахується як $50$ днів). Таким чином, дата початку проживання зараховується як половина дня, якщо вона передує даті отримання статусу (і максимум за $730$ днів до неї), або як цілий день, якщо збігається з датою отримання статусу.

У цій задачі вам потрібно визначити найранішу дату, коли ви можете подати заяву на отримання громадянства.

Вхідні дані

Вхід складається з кількох випадків. Для кожного випадку перший рядок містить дату початку проживання в країні. Другий рядок містить дату, коли ви стали постійним мешканцем. Третій рядок містить ціле число $N$ ( $0 \leq N \leq 100$ 0 \leq N \leq 100) — кількість подорожей поза межі Канади. Кожен із наступних $N$ рядків містить по дві дати, розділені пробілом, які позначають початок і кінець (включно) кожної подорожі. Вважається, що ви перебували поза Канадою з дати початку по дату завершення включно.

Ви можете вважати, що дата початку проживання не пізніше дати отримання статусу постійного мешканця. Також можна вважати, що дата початку кожної подорожі не пізніше її завершення, жодна подорож не триває понад $200$ днів, жодна подорож не включає дату початку проживання чи дату отримання статусу, і жодні дві подорожі не накладаються одна на одну. Жодна подорож не відбулася до початку проживання. Всі дати подаються у форматі Місяць/День/Рік і є коректними; жодна не передує 1 січня 1980 року і не перевищує 31 грудня 2020 року.

Вихідні дані

Для кожного випадку виведіть в одному рядку найранішу дату (у вхідному форматі), коли ви можете подати заяву на отримання громадянства.

Приклади

Приклад 1