시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 0 0 0 0.000%

문제

Absenteeism is a habitual pattern of absence from a duty or obligation without good reason.

Wikipedia

Alex works at work. $n$ employees work together with him. Unlike Alex, they strictly follow their schedule: the $i$-th employee comes to work at the time moment $a_i$ and leaves at the time moment $b_i$ ($a_i < b_i$).

Alex has to come to work not earlier the time moment 0, leave not later the time moment $m$ and work for $k$ hours a day ($k \le m$). But, of course, he wants to work as less as possible. The problem is, his colleagues don't like lazy people, and if one of them discovers that Alex works less than $k$ hours a day, they complain to the boss and Alex will be fired.

In other words, let's say Alex comes to work at the time moment $x$ and leaves work at the time moment $y$, where $0 \le x < y \le m$. Then Alex is in danger if at least one of the following conditions is satisfied:

  • $y - x < k$, and there exists an employee $i$ such that $a_i \le x$ and $y \le b_i$ (the segment $[x, y]$ is entirely nested into $[a_i, b_i]$) --- in this case the $i$-th employee sees how Alex works less than $k$ hours with their own eyes;
  • there exists an employee $i$ such that $x < a_i \le y \le b_i$, and $y < k$ --- in this case the $i$-th employee sees how Alex leaves work earlier than the time moment $k$;
  • there exists an employee $i$ such that $a_i \le x \le b_i < y$, and $x > m - k$ --- in this case the $i$-th employee sees how Alex comes to work later than the time moment $m - k$;
  • there exists an employee $i$ such that $y < a_i$ or $b_i < x$ (the segments $[x, y]$ and $[a_i, b_i]$ don't intersect), and $a_i \le k$ and $b_i \ge m - k$ --- in this case the $i$-th employee doesn't see Alex at work at all, but it's exactly the reason they conclude Alex couldn't work for $k$ hours.

What is the minimal time Alex can spend at work such that nobody of his colleagues complains to the boss?

입력

The first line contains three integers $n$, $m$, $k$ ($1 \le n \le 10^5$, $1 \le m \le 10^9$, $1 \le k \le m$) --- the number of employees working together with Alex, the day length and the number of hours Alex has to work in a day.

Each of the following $n$ lines contains two integers $a_i$ and $b_i$ ($0 \le a_i < b_i \le m$) --- the moments of time when the $i$-th employee comes to work and leaves work.

출력

If Alex is able to not come to work at all, output "-1 -1".

Otherwise, output two integers $x$, $y$ ($0 \le x < y \le m$, $y - x \le k$) --- the moments of time when Alex should come to work and leave work, so that nobody of his colleagues complain to the boss and the working time is minimal.

If there are several possible solutions, output any of them.

예제 입력 1

2 20 10
0 12
8 20

예제 출력 1

7 13

예제 입력 2

2 20 18
0 10
10 20

예제 출력 2

2 18