题目背景

#47 已经修复了，可以提交。并没有申请到重测，请自行重新提交此题。

一次次不假思索地按下快门。
是为了抓住当时的快乐？
还是抓住当时的自己？

题目描述

有一个 $n$ 个元素的序列 $s$。

有 $q$ 次操作，每次操作为以下两种之一：

1. 询问。给出 $l$、$r$、$V$，查询：

$$\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. 单点修改。给出 $w$ 和 $k$，将 $s_w$ 设为 $k$。

输入格式

本题强制在线，对于每次操作的 $l$、$r$ 或 $w$，记上一次查询的答案为 $last$。初始 $last=0$。

则解密为：

• $l \gets (l \otimes |last|) \mod n +1$
• $r \gets (r \otimes |last|) \mod n +1$
• $w \gets (w \otimes |last|) \mod n +1$

其中 $\otimes$ 是按位异或运算，若 $l>r$ 请交换 $l$ 和 $r$。

第一行两个整数 $n$ 和 $q$。

第二行 $n$ 个整数表示 $s_i$。

接下来 $q$ 行，每行 1 l r V 或 2 w k，表示一种操作。

输出格式

对于每个询问，一行一个整数表示答案。

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

提示

数据范围

以下设 $G$ 表示测试点内所有 $\lvert s_i \rvert,\lvert V \rvert,\lvert k \rvert$ 的最大值。

对于 $100\%$ 的数据，保证：$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$，$V \ge 0$。

Subtask	分值	$n \le$	$q \le$	$G \le$	特殊性质
$1$	$5$	$5$	$10$		无
$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$				无

特殊性质 A：没有修改操作。

特殊性质 B：$s_i\ge 0$。