Background

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?

Problem Description

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

Input Format

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.

Output Format

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

5 5
-2 1 3 -4 8
1 1 5 3
2 1 7
2 3 -6
1 2 4 5
1 1 5 2

0
11
12

Hint

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$		None
$2$		$200$	<	$10^3$	^
$3$	$10$	$10^3$		$10^5$
$4$	$15$	$5 \times 10^3$		^
$5$		$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