Description

lhm has a polygon formed by $n$ rectangles of width $1$ arranged horizontally. The height of the $i$-th rectangle is $a_i$. Now he will perform $k$ operations. In each operation, the height of one rectangle of width $1$ is decreased by $1$. After each operation, find the maximum area of a sub-rectangle (obviously, the sub-rectangle must be a continuous segment).

Note that in all cases, the height is always $\geq 0$.

Since lhm is too weak, he wants to ask the smart you to help him solve it.

Input Format

The input has a total of $k + 2$ lines.
The first line contains two integers $n, k$, with meanings as described above.
The second line contains $n$ integers $a_i$, where the $i$-th integer represents the height of the $i$-th rectangle.
The next $k$ lines each contain one integer $\operatorname{id}'$. The operation index is $\operatorname{id}=\operatorname{id}'\bigoplus \operatorname{lastans}$, where $\operatorname{lastans}$ is the answer to the previous query, and initially $\operatorname{lastans}=0$.

Output Format

The output has a total of $k$ lines.
Each line contains one integer, which is the required answer for each query.

5 2
2 3 1 3 2
2
6

5
4

Hint

This problem uses bundled testdata.

For $100\%$ of the data, $1\le n,k\le 5\times 10^5$, $1\leq a_i\leq 10^9$. It is guaranteed that $\operatorname{id}'$ is within the range of long long.

Translated by ChatGPT 5