F. Infinite Loop
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Bobo is trapped in an infinite time loop of a peculiar day! Each day consists of exactly $$$k$$$ hours, and every day, $$$n$$$ tasks arrive for Bobo to complete.

  • The $$$i$$$-th task of the day arrives at the beginning of the $$$a_i$$$-th hour and requires $$$b_i$$$ hours of uninterrupted effort to finish.
  • Bobo works diligently and always follows a disciplined approach: whenever there are unfinished tasks, Bobo works on the earliest received unfinished task.

At the beginning of the first day, Bobo starts with no tasks.

Your mission is to help Bobo answer $$$q$$$ queries. For the $$$i$$$-th query, you are given $$$x_i$$$, the day on which a task is received, and $$$y_i$$$, the index of the task received on that day. Your goal is to determine the exact day and hour when Bobo will complete the $$$y_i$$$-th taskof day $$$x_i$$$.

Input

The first line contains three space-separated integers, which are $$$n$$$ ($$$1 \leq n \leq 10^5$$$), $$$k$$$ ($$$1 \leq k \leq 10^8$$$), and $$$q$$$ ($$$1 \leq q \leq 10^5$$$), respectively.

The next $$$n$$$ lines each contain two space-separated integers, where the $$$i$$$-th line contains $$$a_i$$$ ($$$1 \leq a_i \leq k$$$) and $$$b_i$$$ ($$$1 \leq b_i \leq k$$$). It is guaranteed that $$$a_i$$$ is strictly monotonically increasing.

Then $$$q$$$ lines follow, each containing two space-separated integers, where the $$$i$$$-th line contains $$$x_i$$$ ($$$1 \leq x_i \leq 5 \times 10^5$$$) and $$$y_i$$$ ($$$1 \leq y_i \leq n$$$).

Output

Output $$$q$$$ lines, where the $$$i$$$-th line outputs two space-separated integers $$$d_i$$$ and $$$h_i$$$, indicating that the task for the $$$i$$$-th query is completed at the $$$h_i$$$-th hour on the $$$d_i$$$-th day.

Examples
Input
2 5 6
1 1
4 3
1 1
1 2
2 1
2 2
3 1
3 2
Output
1 1
2 1
2 2
3 1
3 2
4 1
Input
3 10 5
2 4
3 1
10 7
2 2
7 1
4 3
5 2
28 3
Output
3 1
8 10
6 2
6 7
34 10