시민권

오랫동안 다른 나라로 이사한 당신은 이제 시민권을 신청하기로 했다. 새 나라는 모든 신청자에게 엄격한 거주 요건을 둔다. 신청하려면 과거 $y$년 연속으로, 해마다 최소 $d$일 동안 그 나라에 실제로 체류해야 한다. 이 연도들은 신청일부터 거꾸로 센 12개월 기간으로 계산한다.

이 문제에서는 달력의 한 해가 12개월, 365일이고, 각 달의 날수는 아래 표와 같다고 가정한다.

예를 들어 2024-09-19에 신청한다면, 2023-09-19부터 2024-09-18까지, 2022-09-19부터 2023-09-18까지, 이런 식으로 $y$개의 기간 각각에서 최소 $d$일을 그 나라에 있어야 한다.

당신은 이미 $y$년 이상 그 나라에서 살았지만 여행을 많이 다녀서, 거주 요건을 충족하는지 확신하지 못한다. 여행 기록이 주어졌을 때 시민권 신청서를 제출할 수 있는 가장 이른 날짜를 찾는 프로그램을 작성하라.

첫 줄에 세 정수 $n$, $y$, $d$가 주어진다 ($1 \le n \le 500$, $1 \le y \le 1000$, $1 \le d \le 365$). $n$은 출국한 횟수이고, $y$와 $d$는 위에서 설명한 거주 요건이다.

이어서 $n$개의 줄이 주어지며, 각 줄에는 YYYY-MM-DD 형식의 날짜 두 개가 주어진다. 연도 YYYY는 0000 이상 5000 이하, 월 MM은 01 이상 12 이하, 일 DD는 01 이상 31 이하이다. 각 줄의 두 날짜 사이 기간은 양 끝을 포함해서 출국해 있던 기간이다. 입력의 모든 날짜는 오름차순으로 정렬되어 있다. 같은 날짜가 나올 수 있는 경우는 같은 줄 안의 두 날짜뿐이다. 주어진 날짜는 모두 유효한 날짜이다.

신청할 수 있는 가장 이른 날짜를 YYYY-MM-DD 형식으로 출력한다. 이 날짜는 입력의 마지막 날짜보다 뒤여야 한다.