P16524 The First Day of the Rest of My Life

 >Pressing the shutter again and again without thinking.\ >Is it to capture the happiness at that moment?\ >Or to capture who I was at that moment?

There is a sequence $s$ with $n$ elements. There are $q$ operations. Each operation is one of the following two types: 1. Query. Given $l$, $r$, and $V$, compute: $$\max^r_{i=l-1} \left (\sum^i_{\substack{k=l \\ |s_k| \le V}}s_k + \sum^r_{\substack{k=i+1 \\ |s_k| > V}}s_k \right)$$ 2. Point update. Given $w$ and $k$, set $s_w$ to $k$.

This problem is **forced online**. For $l$, $r$, or $w$ in each operation, let the answer to the previous query be $last$. Initially, $last=0$. Then decrypt as follows: - $l \gets (l \otimes |last|) \mod n +1$ - $r \gets (r \otimes |last|) \mod n +1$ - $w \gets (w \otimes |last|) \mod n +1$ Here, $\otimes$ is the bitwise XOR operation. If $l>r$, please swap $l$ and $r$. The first line contains two integers $n$ and $q$. The second line contains $n$ integers representing $s_i$. The next $q$ lines each contain either `1 l r V` or `2 w k`, representing an operation.

For each query, output one integer per line as the answer.

### Constraints Let $G$ be the maximum value among all $\lvert s_i \rvert,\lvert V \rvert,\lvert k \rvert$ within a test point. For $100\%$ of the data, it is guaranteed that: $1 \le n \le 5 \times 10^4$, $1 \le l,r \le n$, $1 \le w \le n$, $\lvert s_i \rvert,\lvert V \rvert,\lvert k \rvert \le 10^8$, and $V \ge 0$. | Subtask | Score | $n \le$ | $q \le$ | $G \le$ | Special Property | |:-:|:-:|:-:|:-:|:-:|:-:| | $1$ | $5$ | $5$ | $10$ | $10$ | None | | $2$ | $5$ | $200$ | < | $10^3$ | ^ | | $3$ | $10$ | $10^3$ | < | $10^5$ | ^ | | $4$ | $15$ | $5 \times 10^3$ | < | ^ | ^ | | $5$ | $15$ | $5 \times 10^4$ | < | $10^8$ | A | | $6$ | $10$ | ^ | ^ | ^ | B | | $7$ | $40$ | ^ | ^ | ^ | None | Special Property A: There are no update operations. Special Property B: $s_i \ge 0$. Translated by ChatGPT 5