After days of reckless spending, Zawaex has found himself in some deep trouble, and is close to going into debt. He currently has ~M~ dollars left and he finds a list of ~N~ events that he had predicted would happen to him over the next few days. The ~i~th event can be characterized by a single integer ~d_i~, the amount of money in dollars that he would gain from it. (If ~d_i~ was negative, he would instead lose money). If Zawaex's amount of money were to become negative after an event, he would instead "borrow" enough money from his friend so that he would end up with ~0~ dollars after the event. Since Zawaex has a horrible memory, he doesn't know which events have already happened to him. He also doesn't know when he will be able to find employment and get out of this financial crisis. As such, he wants to know how many times he would need to "borrow" money from a friend and how much money he would be left with at the end for ~Q~ different scenarios where a scenario is defined as a contiguous subsequence of the original ~N~ events. Being uncertain about his future, Zawaex has turned to you for help.

Input Specification

The first line contains three space-separated integers, ~N~, ~M~, and ~Q~.
The second line contains ~N~ space-separated integers, ~d_1, d_2, \dots, d_N~.
~Q~ lines will follow, each of which contains two space-separated integers, ~l_i~ and ~r_i~, denoting the scenario that is the contiguous subsequence between the ~l_i~th and ~r_i~th events.

Output Specification

For each query, output on a new line two space-separated integers, the amount of money that he will be left with in the end and the number of times that Zawaex has to "borrow" money from his friend.

Constraints

In all subtasks,
~1 \le N,Q \le 300\,000~
~1 \le M,|d_i| \le 10^9~

Subtask 1 [10%]

~1 \le N,Q \le 2000~

Subtask 2 [30%]

It is only necessary to determine the amount of money Zawaex will end up with at the end.
For this subtask, your answer will be accepted as long as the first integer in each line is correct. Note that you must still print two integers on each line.

Subtask 3 [60%]

No additional constraints.

Sample Input

5 10 5
4 -7 -8 2 -3
1 5
2 3
1 3
2 4
3 5

Sample Output

0 2
0 1
0 1
2 1
1 0

Explanation for Sample Output

For the first query, he ends up with ~14~ dollars after the first event, and then needs to "borrow" money after the third event. The ~2~ dollars he gains from the fourth event is not enough for the ~3~ dollars he stands to lose from the fifth event, thus he needs to borrow money once again.

For the second subtask only,

0 42384
0 -535
0 3283
2 1232
1 325

would also be considered correct output (only the first integer of each line is output correctly; the second integer on each line were chosen arbitrarily).