P8157 "PMOI-5" Fat Nerd Happy Water

When lhm was drinking Fat Nerd Happy Water, he came up with this idea, so he named it Fat Nerd Happy Water. ~~This problem is a weakened version. Please look forward to the strengthened version in Ynoi.~~ Special thanks: the verifier, Dual-Tube Fluorescent Lamp, crushed this problem’s std.

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.

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$.

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

**This problem uses bundled testdata.** | Subtask ID | Score | $n, k$ | | :-----------: | :---:| :-----------: | | 1 | 10 | $\leq 500$ | | 2 | 10 | $\leq 5000$ | | 3 | 40 | $\leq 10^5$ | | 4 | 40 | $\leq 5\times10^5$ | 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