Description

Farmer Byteasar bought a piece of land with area $n$ mu, and he wants to grow grass on it.

On each mu of land, he plants a unique type of grass. The grass on the $i$-th mu grows by $a_i$ centimeters every day.

Byteasar will harvest $m$ times. The $i$-th harvest happens on day $d_i$, and he cuts off all parts whose height is greater than or equal to $b_i$.

Byteasar wants to know, for each harvest, what the total height of grass obtained is. Can you help him?

Input Format

The first line contains two positive integers $n, m$, representing the number of mu and the number of harvests.

The second line contains $n$ positive integers. The $i$-th number is $a_i$, describing the growth rate of the grass on each mu.

In the next $m$ lines, each line contains two integers $d_i, b_i$, describing each harvest in order.

Output Format

Output $m$ lines. Each line contains one integer, answering in order the total height of grass obtained in each harvest.

4 4
1 2 4 3
1 1
2 2
3 0
4 4

6
6
18
0

Hint

For $100\%$ of the testdata, $1 \le n, m \le 5 \times 10^5$, $1 \le a_i \le 10^6$, $1 \le d_i \le 10^{12}$, $0 \le b_i \le 10^{12}$.

The testdata guarantees that $d_1 < d_2 < \dots < d_m$, and at any time, the height of the grass on any mu never exceeds $10^{12}$.

Translated by ChatGPT 5