B. Evacuation
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are $$$N+2$$$ towns in a straight line. The towns are numbered from $$$0$$$ through $$$N+1$$$ from left to right. Each town $$$i$$$ ($$$1 \leq i \leq N$$$) has a shelter which can contain up to $$$A_i$$$ people.

Currently, $$$S$$$ people are traveling together and visiting one of the towns. However, you don't know which town they are visiting.

You just got to know that there are $$$Q$$$ meteorites that can hit the towns. The $$$i$$$-th meteorite may strike towns $$$L_i,L_i+1,\cdots,R_i$$$. To ensure the safety of the travelers, for each meteorite, you want to calculate the **evacuation cost**.

The evacuation cost for a meteorite is calculated as follows:

  • The evacuation cost is the minimum total cost needed to make all travelers **safe** no matter which town they are visiting.
  • A person is safe if he/she is in a shelter or a town outside the effect of the meteorite.
  • It takes $$$1$$$ unit cost to move one person to an adjacent town (two towns are adjacent iff their numbers differ by exactly $$$1$$$).

Note that only moving people costs money, and other actions (like accommodating people in a shelter) don't. It is guaranteed that towns $$$0$$$ and $$$N+1$$$ will never be affected by meteorites, so it is always possible to make all travelers safe.

Write a program that, for each meteorite, calculates the evacuation cost for that meteorite.

Input

Input is given from Standard Input in the following format:

$$$N$$$ $$$S$$$

$$$A_1$$$ $$$A_2$$$ $$$\cdots$$$ $$$A_N$$$

$$$Q$$$

$$$L_1$$$ $$$R_1$$$

$$$L_2$$$ $$$R_2$$$

$$$\vdots$$$

$$$L_Q$$$ $$$R_Q$$$

Constraints:

  • $$$1 \leq N \leq 2 \times 10^5$$$
  • $$$1 \leq S \leq 10^{12}$$$
  • $$$0 \leq A_i \leq S$$$
  • $$$A_1+A_2+\cdots+A_N \leq 10^{12}$$$
  • $$$1 \leq Q \leq 2 \times 10^5$$$
  • $$$1 \leq L_i \leq R_i \leq N$$$
  • All values in input are integers.
Output

Print $$$Q$$$ lines. The $$$i$$$-th line should contain the evacuation cost for the meteorite $$$i$$$.

Example
Input
5 10
3 1 1 4 1
3
1 4
3 5
2 5
Output
14
10
13
Note
  • For the first meteorite, it takes $$$14$$$ unit costs when the travelers are visiting the town $$$2$$$.
  • For the second meteorite, it takes $$$10$$$ unit costs when the travelers are visiting the town $$$4$$$.
  • For the third meteorite, it takes $$$13$$$ unit costs when the travelers are visiting the town $$$3$$$.