시민권 신청

캐나다에서는 영주권자로 입국(landing)한 뒤, 신청일 바로 직전의 1460일(약 4년) 동안 캐나다에 최소 1095일(약 3년) 이상 거주했다면 시민권을 신청할 수 있다. 신청일 당일은 이 기간에 포함하지 않는다.

캐나다 밖으로 여행한 날은 캐나다에 거주한 날로 인정되지 않는다.

만약 이 1460일 기간 중, 영주권자로 입국하기 이전부터 (예: 유학 등으로) 이미 캐나다에 거주하고 있었다면, 입국일 이전의 그 거주 기간은 최대 730일까지 — 즉 입국일로부터 730일을 넘지 않는 기간만 — 절반으로(소수점 이하 버림) 인정된다. 예를 들어 입국 전 대기 기간이 101일이었다면 50일로 인정된다.

정리하면, 입국일 이전의 거주일은 (입국일로부터 730일을 넘지 않는 한) 반나절로 계산되고, 입국일 당일은 하루로 온전히 계산된다.

이 문제에서는 시민권을 신청할 수 있는 가장 이른 날짜를 구한다.

입력은 여러 개의 테스트 케이스로 이루어지며, 파일의 끝까지 읽는다.

각 케이스는 다음과 같이 주어진다.

• 첫째 줄: 캐나다 거주를 시작한 날짜
• 둘째 줄: 영주권자로 입국한 날짜
• 셋째 줄: 캐나다 밖으로 떠난 여행의 횟수를 나타내는 정수 $N$ ($0 \le N \le 100$)
• 이어지는 $N$개의 줄: 각 줄에 공백으로 구분된 두 날짜가 주어지며, 각각 캐나다 밖 여행의 시작 날짜와 끝 날짜(양 끝 포함)를 나타낸다. 시작 날짜부터 끝 날짜까지는 캐나다 밖에 있는 것으로 본다.

거주 시작 날짜는 입국 날짜보다 늦지 않으며, 각 여행의 시작 날짜는 끝 날짜보다 늦지 않고, 어느 여행도 200일을 넘지 않는다고 가정해도 된다. 어느 여행도 거주 시작 날짜나 입국 날짜를 포함하지 않으며, 두 여행이 서로 겹치지 않고, 거주 시작 날짜 이전에 시작하는 여행도 없다.

모든 날짜는 월/일/연도(Month/Day/Year) 형식의 유효한 날짜이며, 1980년 1월 1일부터 2020년 12월 31일 사이(양 끝 포함)에 있다.

각 케이스마다, 시민권을 신청할 수 있는 가장 이른 날짜를 입력과 같은 월/일/연도 형식으로 한 줄에 출력한다.