D. Hackathon
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

VK often holds hackathons where programmers solve various problems. VK is now preparing a new hackathon in which anyone can try their hand at developing a unique and useful application or service for one of several tracks including Fintech, Culture, Media, and others.

As with any well-organized hackathon, to allow participants to fully dedicate themselves to solving the task at hand they are provided with a carefully organized venue. Pleasant bonuses often include food and drinks, which can be enjoyed over the several days that participants spend at the venue.

This time VK is organizing a new hackathon, and $$$m$$$ participants have gathered at the venue. For these $$$m$$$ participants the organizers have ordered $$$n$$$ pizzas which are arranged in a row and numbered from $$$1$$$ to $$$n$$$. It is known that:

  • each pizza consists of an infinite number of slices;
  • the first slice of the $$$i$$$-th pizza has a dough thickness of $$$a_i$$$, and each subsequent one is $$$1$$$ thicker than the previous (i.e., $$$a_i + 1$$$, $$$a_i + 2$$$, and so on);
  • the slices with the least dough thickness seem most attractive to participants;
  • any participant can approach the row of pizzas at any point, but afterwards can only move left (towards the pizzas with smaller numbers) to avoid collisions with other participants.

Periodically, participants get up from their places and approach the row of pizzas to take a slice. Participant number $$$i$$$ approaches the pizza numbered $$$s_i$$$ at time $$$t_i$$$, after which they immediately find the slice of pizza with the least dough thickness among pizzas from $$$1$$$ to $$$s_i$$$ and start moving towards it. It takes each participant the same amount of time to move between two adjacent pizzas — exactly $$$v$$$ seconds. Several participants can be near the same pizza at the same time.

As soon as a participant reaches the pizza they have chosen, they take the slice and return to their seat. If several participants have chosen the same slice and reach it simultaneously, the participant with the lower number takes the slice. If the slice a participant was counting on is taken by someone else, that participant immediately chooses a new target using the same algorithm: they look at all the pizzas from the first to their current position, select the minimum among them, and start moving towards it.

Formally, this process can be described as follows. At every whole number of seconds $$$t$$$:

  1. all participants who were already in the row at time $$$t - 1$$$ move by $$$\frac{1}{v}$$$ to the left;
  2. all participants with $$$t_i = t$$$ approach the pizza number $$$s_i$$$;
  3. time "stops";
  4. all participants standing at whole positions $$$p$$$ such that $$$a_p = \min(a_1, a_2, \ldots, a_p)$$$ are identified;
  5. for each such $$$p$$$, the participant with the minimum number standing at position $$$p$$$ takes the slice of pizza with thickness $$$a_p$$$ and leaves; $$$a_p$$$ is increased by $$$1$$$;
  6. after some slices of pizza are taken, it may happen that the minimum thickness of the slice that some participants can still get has changed, in which case the process repeats from step 4;
  7. otherwise, time "starts again" and the process moves to the next second.

Based on the information about participants' approaches to the pizzas, determine for each participant the thickness of the pizza slice they received and how much time they spent in the row.

Input

The first line of input contains three space-separated integers $$$n$$$, $$$m$$$, and $$$v$$$ — the number of pizzas, the number of participants and the time it takes each participant to move between adjacent pizzas ($$$1 \le n, m \le 10^5$$$; $$$1 \le v \le 10^9$$$).

The second line lists $$$n$$$ space-separated integers $$$a_i$$$ — the thickness of the first slice of each pizza ($$$0 \le a_i \le 10^9$$$).

In the $$$i$$$-th of the following $$$m$$$ lines, two integers $$$s_i$$$ and $$$t_i$$$ are given, separated by a space — the starting position and the time of the participant's approach to the row of pizzas ($$$1 \le s_i \le n$$$; $$$0 \le t_i \le 10^9$$$).

Output

Output $$$m$$$ lines, in the $$$i$$$-th of which print a pair of space-separated integers: the dough thickness of the pizza slice received by the $$$i$$$-th participant and the time it took the participant to reach it.

Scoring

Points for each subtask are awarded only if all tests of that subtask and the required subtasks are successfully passed.

SubtaskPointsConstraints Required subtasks
0–examples
18$$$\max(t_i) \le 10^4$$$; $$$n, m, v \le 100$$$0
210all $$$s_i$$$ are equal and all $$$t_i$$$ are equal
313$$$|a_i - a_j| \ge m$$$ for any $$$i \ne j$$$
419$$$n, m \le 1000$$$0, 1
516$$$m \le 1000$$$0, 1, 4
634none0 – 5
Examples
Input
5 3 1
1 2 3 4 5
5 1
3 2
2 4
Output
2 3
1 2
2 1
Input
7 7 3
1 5 3 2 5 4 1
5 4
2 3
4 2
1 6
7 8
3 2
2 4
Output
2 3
1 3
5 6
2 0
1 0
4 6
3 3
Note

In the first example, events will occur in the following order:

  1. The first participant appears at position $$$5$$$ at time $$$1$$$; their target is pizza number $$$1$$$.
  2. By the time $$$2$$$, the first participant is at position $$$4$$$, and the second participant appears at position $$$3$$$. Both will move towards pizza number $$$1$$$.
  3. In the third second, no changes occur, and the participants continue to move left.
  4. At time $$$4$$$: the second participant is near the first pizza, the first and third participants are together near the second. The second participant takes a slice of pizza with a thickness of $$$1$$$, $$$a_1$$$ becomes equal to $$$2$$$.
  5. The first and third participants immediately see that they will no longer get a slice of pizza with a thickness of $$$1$$$, but they can take one with a thickness of $$$2$$$ at their current position. The first, as the participant with the lower number, takes $$$a_2 = 2$$$, after which $$$a_2$$$ becomes equal to $$$3$$$.
  6. The remaining third participant can only move one more to the left and take $$$a_1 = 2$$$.