Alan has recently made a deal with a Nigerian prince, and is now faced with ~N~ boxes full of gold. The boxes are equally distant from each other, with the ~N^{th}~ box closest to him. However he has not come prepared, and his truck only has space for 2 boxes of gold.

Each of the boxes of gold has a value ~A_i~, which is the value of the gold contained in it.

Unfortunately, Alan is also extremely lazy, and the boxes with greater value are also heavier due to their higher gold content. Thus, for each step Alan takes with a box, the value of taking that box decreases, as he loses the will to continue.

Alan has decided that the optimal way for him to choose 2 boxes is to maximize ~(A_i + A_j)\cdot i\cdot j~, where ~i~ and ~j~ are the indices of the boxes he takes. This way, he believes he will get the maximum revenue to effort ratio.

The Nigerian Prince is very sketchy, however, and Alan doesn't know the exact value of any box at any given time. He does have an estimate of the value of each box which changes over time.

There will be ~Q~ queries in which Alan will re-evaluates the value of box ~x_j~, and decides it is more likely to be of value ~v_j~. For each query, Alan would like to know the maximal value of ~(A_i+A_j)\cdot i\cdot j~ he can obtain. Can you help Alan?

Input Specification

The first line of input will contain two integers ~N\ (1 \leq N \leq 5\cdot 10^5)~, and ~Q\ (1 \leq Q \leq 5\cdot 10^5)~, the number of boxes and queries.

The next line will contain ~N~ integers ~A_i\ (1 \leq A_i \leq 10^6)~, the original values of the gold boxes.

The next ~Q~ lines will contain 2 integers ~x_j\ (1 \leq x_j \leq N)~, and ~v_j\ (1 \leq v_j\leq 10^6)~.

Ouput Specification

You are to output ~Q~ lines, the answers to Alan's queries.

Subtasks

Subtask 1 (5%)

~N,Q \leq 500~

Subtask 2 (15%)

~N,Q \leq 3000~

Subtask 3 (30%)

~Q = 10~

Subtask 4 (50%)

No further constraints.

Sample Input

5 5
1 5 5 3 1
2 5
1 1
3 3
4 1
2 1

Sample Output

96
96
80
60
60