Macduff, overwhelmed by the vast amount of health potions, gets transported to another dimension! However, this place takes place underwater, where the special water allows them to breathe, look around, and move as if walking on land. Macduff, becoming entranced by the magical water, is totally, utterly, shocked.

I CAN BREATHE!! I can see! I- I can do everything! I could cure cancer, solve world hunger- Wait ...

However, in that split second, he loses sight of Macbeth!

Knowing that Macbeth is somewhere over the ~N~ positions in front of him, he wants to know the range of the direction which Macbeth is headed in. Thankfully, he mysteriously knows the individual weight, ~A_i~, of each position. He also just so happens to know that Macbeth weighs ~W~.

Macduff suspects ~Q~ ranges which Macbeth could be in, and so he wants to know the sum of each range, from ~l_i~ to ~r_i~. Out of all these ranges, he also wants to know the smallest sum that is greater than or equal to Macbeth's weight, or uh oh if this sum doesn't exist.

Constraints

~1 \le l_i \le r_i \le N~

Subtask 1 [50%]

~1 \le N, Q \le 10^2~

~1 \le A_i, W \le 10^2~

Subtask 2 [50%]

~1 \le N, Q \le 10^6~

~1 \le A_i, W \le 10^9~

Input Specification

The first line will contain integer N, W, and Q, representing the number of positions, Macbeth's weight, and the number of questions that Macduff might have respectively.

The next line will contain N integers, representing the weight of the ~i~th position.

The next ~Q~ lines will contain two numbers, ~l_i~ and ~r_i~, the left and right range (inclusive). These numbers will be 1-indexed.

Output Specification

Print ~Q~ lines, representing the total sum of the positions from ~l_i~ to ~r_i~ for each query.

The next line should contain the smallest sum given by the ranges that is greater than or equal to Macbeth's weight, or uh oh if none exists.

Sample Input 1

5 100 10
10 50 100 30 90
1 4
2 5
1 3
2 2
4 5
1 4
3 5
2 5
5 5
2 4

Sample Output 1

190
270
160
50
120
190
220
270
90
180
120

Sample Input 2

2 1000000000 1
10 10
1 2

Sample Output 2

20
uh oh