407877: GYM102916 A Absenteeism

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 ≤ m). But, of course, he wants to work as little 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 will 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 ≤ x < y ≤ 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 ≤ x and y ≤ 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 ≤ y ≤ 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 ≤ x ≤ 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 ≤ k and b_i ≥ 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 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁹, 1 ≤ k ≤ 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 ≤ a_i < b_i ≤ m) — the moments of time when the i-th employee comes to work and leaves work.

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

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

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

2 20 10
0 12
8 20

7 13

2 20 18
0 10
10 20

2 18