你搬到另一个国家已经很久了，现在你决定成为该国的公民。该国对所有申请人都有严格的居住要求。要申请公民身份，你必须在过去 $y$ 个连续年份中，每年在该国实际居住至少 $d$ 天。这些年份是从申请日期开始向后推算的 12 个月周期。

Image via Rawpixel, CC0

对于本题，假设一个日历年有 12 个月，共 365 天，每个月的天数如下：

例如，如果你在 2024-09-19 申请，你必须在 2023-09-19 到 2024-09-18、2022-09-19 到 2023-09-18 等共 $y$ 个 12 个月的周期内，每个周期在该国居住至少 $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 ($0000 \le YYYY \le 5000, 01 \le MM \le 12, 01 \le DD \le 31$)。你在这两个日期之间（含这两个日期）离开了该国。

输入中的所有日期均按升序排列。仅在同一行内的日期可能相等。所有给定的日期都是有效的。

输出格式

输出你满足居住要求的最早日期。该日期必须在输入中最后一个日期之后。

样例

输入格式 1

3 5 240
2022-02-28 2022-10-01
2022-11-11 2022-11-11
2023-12-30 2024-01-01

输出格式 1

2024-05-31

输入格式 2

3 5 240
2011-11-11 2012-12-12
2022-02-28 2022-10-01
2025-01-01 2025-06-30

输出格式 2

2028-02-26