Alan has recently made a deal with a Nigerian prince, and is now faced with boxes full of gold. The boxes are equally distant from each other, with the 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 , 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 , where and 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 queries in which Alan will re-evaluates the value of box , and decides it is more likely to be of value . For each query, Alan would like to know the maximal value of he can obtain. Can you help Alan?

#### Input Specification

The first line of input will contain two integers , and , the number of boxes and queries.

The next line will contain integers , the original values of the gold boxes.

The next lines will contain 2 integers , and .

#### Ouput Specification

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

#### Subtasks

##### Subtask 1 (5%)

##### Subtask 2 (15%)

##### Subtask 3 (30%)

##### 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
```

## Comments