Little Lana and little Fran are visiting a chocolate factory. They have seen how chocolate is made, tasted many chocolates, and now they want to buy some of the chocolates.

In the shop, there are ~n~ different chocolates, and the ~i~-th of them has the price ~c_i~. Lana and Fran want to buy ~m~ chocolates.

Fran found a way to split the cost in the shop:

• If the chocolate is cheaper than ~k~ kunas, Lana will pay for it.
• Otherwise, Lana will pay ~k~ kunas, and Fran will pay the rest, that is ~c_i - k~ kunas.

Let's denote ~l~ as the amount Lana has to pay, and ~f~ as the amount Fran has to pay. Lana, dissatisfied with Fran's deal, wants to spite Fran and choose the chocolates so the value of the expression ~l - f~ is as small as possible. Since Fran is hesitant and doesn't know how many he wants to buy, Lana wants to know the minimal value of the expression ~l - f~ for ~q~ different numbers ~k_i~ and ~m_i~.

Help her choose the chocolates and determine the minimum value of the expression ~l - f~ for each of the ~q~ queries.

Input Specification

The first line contains two integers ~n~ and ~q~ ~(1 \le n, q \le 10^5)~, the number of chocolates, and the number of queries.

The second line contains ~n~ integers ~c_1, c_2, \dots, c_n~ ~(1 \le c_i \le 10^9)~, the prices of the individual chocolates, in order.

The following ~q~ lines contain integers ~k_i~ and ~m_i~ ~(1 \le k_i \le 10^9, 1 \le m_i \le n)~, Fran's bound, and the number of chocolates they are going to buy.

Output Specification

Print ~q~ lines. In the ~i~-th line print the answer to Lana's ~i~-th query.

Constraints

Subtask	Points	Constraints
~1~	~15~	~n, q \le 1\,000~; ~c_i, k_i \le 10^6~
~2~	~20~	~k_1 = \dots = k_n~
~3~	~35~	No additional constraints.

Sample Input 1

5 2
1 9 22 10 19
18 4
5 2

Sample Output 1

34
-21

Explanation for Sample Output 1

In the first query, Lana can take chocolates with prices ~1~, ~9~, ~22~, and ~10~. Lana will pay ~38~ kunas, and Fran ~4~ kunas. The answer is ~38 - 4 = 34~.

In the second query, Lana will choose chocolates with prices ~22~ and ~19~. She will pay ~10~ kunas, and Fran will pay ~31~ kunas. The answer is ~10 - 31 = -21~.

Sample Input 2

7 4
1 5 4 3 7 11 9
5 4
5 7
7 3
4 5

Sample Output 2

4
16
7
1

Sample Input 3

3 3
5 6 7
10 1
5 3
3 3

Sample Output 3

5
12
0