Farmer Bajtazar has purchased a field with an area of $n$ ares, where he intends to sow grass. The mown and dried grass will serve as fodder for the animals raised on Bajtazar's farm.

A mixture of $n$ grass species will be sown on the field, with each species occupying a total of 1 are of land. For the $i$-th species, it is known that a blade of grass of this species grows by $a_i$ centimeters per day, regardless of weather conditions or soil fertility. It is also known that mowing one centimeter of grass on an area of one are yields exactly 1 kilogram of hay.

Bajtazar has a mower that can be set to cut grass to any height $b$ — with this setting, every blade of grass taller than $b$ centimeters will be cut to a height of exactly $b$ centimeters.

Bajtack law requires that after each mowing, the amount of hay obtained from the mown grass must be documented. Bajtazar is faced with a choice: he must either buy a scale or write a program that, based on the dates of mowing and the mower settings, estimates the weight of the hay obtained after each mowing. The latter option seemed more convenient and cheaper to him.

We assume that the grass is sown on day 0 at midnight and is always mown at midnight. We also assume that the time required to mow the field to any height $b$ is negligibly small.

Input

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 500\,000$), representing the area of Bajtazar's field in ares (and simultaneously the number of grass species sown) and the number of mowings, respectively. The second line contains a sequence of $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) representing the growth rates of the successive grass species.

The next $m$ lines contain descriptions of the mowings performed by Bajtazar: the $i$-th mowing is described by two integers $d_i$ and $b_i$ ($1 \le d_i \le 10^{12}$, $0 \le b_i \le 10^{12}$) in the $i$-th of these lines, meaning that on day $d_i$, Bajtazar cut the grass to a length of $b_i$ centimeters. You may assume that the mowing descriptions are given in chronological order, i.e., $d_1 < d_2 < \dots < d_m$.

Furthermore, you may assume that Bajtazar will never allow a situation where the grass at any point in the field exceeds a height of $10^{12}$ centimeters.

Output

You should output exactly $m$ lines. The $i$-th line should contain the total weight of hay (in kilograms) obtained after the $i$-th mowing.

Examples

Input 1

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

Output 1

6
6
18
0

Note

Explanation of the example: The heights of the grass blades of species 1, 2, 3, 4 before and after the successive mowings are shown in the table below.