CF2255E2.What Will Remain at the End? (Hard Version)

This is the hard version of the problem. The only difference between the two versions is the set of allowed values for the initial array and for $x$ in operations of type $1$. In this version, these values can be any integers in $[-10^9, 10^9]$. You can make hacks only if both versions of the problem are solved.

Before her final sortie, Chtholly asks Willem three questions.

The second is this: what will remain if the sky truly reaches its end?

Willem cannot answer her directly. Instead, he opens a chronicle containing $n$ records, numbered from $1$ to $n$. Each record holds an integer: a positive value represents hope, while a negative value represents despair.

The initial contents of the chronicle form an array $a_1,a_2,\ldots,a_n$, called version $0$. Chtholly then performs $q$ operations. For each $1\le i\le q$, the $i$-th operation creates a new version $i$ from version $i-1$.

Each operation has one of the following four types:

• $\texttt{1 l r x}$: set $a_k\gets x$ for every $l\le k\le r$.
• $\texttt{2 l r}$: set $a_k\gets -a_k$ for every $l\le k\le r$.
• $\texttt{3 l r}$: set $a_k\gets\max(a_k,0)$ for every $l\le k\le r$.
• $\texttt{4 p}$: consider the value at position $p$ in every previous version $0,1,\ldots, i-1$. Let these values be $b_0,b_1,\ldots,b_{i-1}$. Find the maximum sum over all non-empty subarrays$^{\text{∗}}$ of this sequence.

If the operation is of type $1$, $2$, or $3$, the specified modification is applied to version $i-1$ to obtain version $i$. An operation of type $4$ does not modify the array, so version $i$ is identical to version $i-1$.

The operations are encoded and must be processed in order. Their decoding depends on $\mathrm{lastans}$, which is updated after every operation of type $4$.

Help Willem answer every operation of type $4$.

$^{\text{∗}}$An array $c$ is a subarray of an array $b$ if $c$ can be obtained from $b$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

这是该问题的困难版本。两个版本的唯一区别在于初始数组和类型 1 操作中 $x$ 的允许取值范围。在本版本中，这些值可以是区间 $[-10^9, 10^9]$ 内的任意整数。仅当两个版本的问题均被解决时，才允许进行 Hack。

在她最后一次出击前，Chtholly 向 Willem 提出了三个问题。

第二个问题是：若天空真的抵达尽头，将剩下什么？

Willem 无法直接回答她。相反，他打开了一本记载着 $n$ 条记录的编年史，记录编号从 $1$ 到 $n$。每条记录保存一个整数：正值代表希望，负值代表绝望。

编年史的初始内容构成一个数组 $a_1,a_2,\ldots,a_n$，称为第 $0$ 版本。随后 Chtholly 执行 $q$ 次操作。对每个 $1\le i\le q$，第 $i$ 次操作基于第 $i-1$ 版本生成一个新的第 $i$ 版本。

每次操作属于以下四种类型之一：

• $\texttt{1 l r x}$：对每个满足 $l\le k\le r$ 的 $k$，令 $a_k\gets x$。
• $\texttt{2 l r}$：对每个满足 $l\le k\le r$ 的 $k$，令 $a_k\gets -a_k$。
• $\texttt{3 l r}$：对每个满足 $l\le k\le r$ 的 $k$，令 $a_k\gets\max(a_k,0)$。
• $\texttt{4 p}$：考虑位置 $p$ 在所有先前版本 $0,1,\ldots,i-1$ 中的取值。设这些值为 $b_0,b_1,\ldots,b_{i-1}$。求该序列的所有非空子数组$^{\text{∗}}$ 的最大和。

若操作类型为 $1$、$2$ 或 $3$，则对第 $i-1$ 版本应用指定修改以得到第 $i$ 版本。类型 $4$ 的操作不修改数组，因此第 $i$ 版本与第 $i-1$ 版本完全相同。

这些操作经过编码，必须按顺序处理。其解码依赖于变量 $\mathrm{lastans}$，该变量在每次类型 $4$ 的操作后更新。

请帮助 Willem 回答每一次类型 $4$ 的操作。

$^{\text{∗}}$ 若数组 $c$ 可通过对数组 $b$ 删除开头若干（可能为零或全部）元素及结尾若干（可能为零或全部）元素而得到，则称 $c$ 是 $b$ 的一个子数组。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($1\le n,q\le5\cdot10^5$) — the length of the array and the number of operations.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^9\le a_i\le 10^9$) — the array in version $0$.

Each of the next $q$ lines describes one operation in one of the following encoded formats: The first integer on the line is the operation type.

• $\texttt{1 u v x}$ ($0\le u,v \lt 2^{64}$, $-10^9\le x\le 10^9$);
• $\texttt{2 u v}$ ($0\le u,v \lt 2^{64}$);
• $\texttt{3 u v}$ ($0\le u,v \lt 2^{64}$);
• $\texttt{4 u}$ ($0\le u \lt 2^{64}$).

The operations are encoded and must be processed in order. Their decoding depends on a value $\mathrm{lastans}$.

Initially, $\mathrm{lastans}=0$. After answering an operation of type $4$, set $\mathrm{lastans}$ to the least non-negative residue of its answer modulo $2^{64}$. Operations of all other types leave $\mathrm{lastans}$ unchanged.

For every encoded coordinate $y$, define $d(y)=\left(\left(y\oplus\mathrm{lastans}\right)\bmod n\right)+1$. Here, $\oplus$ denotes the bitwise XOR operation.

• For an operation $\texttt{1 u v x}$, let $l=\min(d(u),d(v))$ and $r=\max(d(u),d(v))$. The value $x$ is not encoded.
• For an operation $\texttt{2 u v}$ or $\texttt{3 u v}$, let $l=\min(d(u),d(v))$ and $r=\max(d(u),d(v))$.
• For an operation $\texttt{4 u}$, let $p=d(u)$.

The operation type is not encoded. Do not forget to update $\mathrm{lastans}$ after answering each operation of type $4$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot10^5$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $5\cdot10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1\le n,q\le5\cdot10^5$）——分别表示数组长度和操作次数。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^9\le a_i\le 10^9$）——表示版本 $0$ 的初始数组。

接下来的 $q$ 行，每行描述一个操作，格式为以下编码形式之一：每行第一个整数为操作类型。

• $\texttt{1 u v x}$（其中 $0\le u,v \lt 2^{64}$，$-10^9\le x\le 10^9$）；
• $\texttt{2 u v}$（其中 $0\le u,v \lt 2^{64}$）；
• $\texttt{3 u v}$（其中 $0\le u,v \lt 2^{64}$）；
• $\texttt{4 u}$（其中 $0\le u \lt 2^{64}$）。

这些操作是经过编码的，必须按顺序处理。其解码依赖于一个值 $\mathrm{lastans}$。

初始时，$\mathrm{lastans}=0$。在回答完类型为 $4$ 的操作后，将 $\mathrm{lastans}$ 更新为该答案对 $2^{64}$ 取模所得的最小非负剩余。其余所有类型的操作均不改变 $\mathrm{lastans}$ 的值。

对于任意编码坐标 $y$，定义 $d(y)=\left(\left(y\oplus\mathrm{lastans}\right)\bmod n\right)+1$。其中，$\oplus$ 表示按位异或运算。

• 对于操作 $\texttt{1 u v x}$，令 $l=\min(d(u),d(v))$，$r=\max(d(u),d(v))$；值 $x$ 未被编码。
• 对于操作 $\texttt{2 u v}$ 或 $\texttt{3 u v}$，令 $l=\min(d(u),d(v))$，$r=\max(d(u),d(v))$。
• 对于操作 $\texttt{4 u}$，令 $p=d(u)$。

操作类型本身未被编码。请勿忘记在每次回答类型为 $4$ 的操作后更新 $\mathrm{lastans}$。

保证所有测试用例的 $n$ 之和不超过 $5\cdot10^5$。

保证所有测试用例的 $q$ 之和不超过 $5\cdot10^5$。

For every operation of type $4$, output a single integer — the maximum sum of a non-empty subarray of the sequence of the values at position $p$ over all versions preceding this operation.

对于每个类型为 $4$ 的操作，输出一个整数——该操作之前所有版本中位置 $p$ 处的值所构成序列的非空子数组的最大和。

In the first test case, for the first operation, $\mathrm{lastans}=0$, so the encoded coordinate $1$ is decoded into position $2$. Only version $0$ is considered. The value at position $2$ is $-3$, hence the answer is $-3$.

Now $\mathrm{lastans}=2^{64}-3=18\,446\,744\,073\,709\,551\,613$. Therefore the encoded interval $[18\,446\,744\,073\,709\,551\,613,18\,446\,744\,073\,709\,551\,615]$ is decoded into $[1,3]$, and the encoded coordinate $18\,446\,744\,073\,709\,551\,612$ is decoded into position $2$.

Before the second query, the values at position $2$ in versions $0$, $1$, and $2$ are $-3$, $-3$, and $3$, respectively. Their maximum non-empty subarray sum is $3$.

Before the third query, the values at position $2$ in versions $0,1,\ldots,5$ form sequence $[-3,-3,3,3,3,-4]$. The three consecutive values equal to $3$ form a subarray with sum $9$.

Notice that the first, second, and third queries create versions $1$, $3$, and $6$, respectively, even though they do not change the array.

In the second test case, the first query asks about position $1$, so its answer is $1$. Then $\mathrm{lastans}=1$, and the encoded operation $\texttt{1 0 3 -1}$ is decoded into $\texttt{1 2 3 -1}$.

Before the second query, the values at position $3$ in versions $0$, $1$, and $2$ are $3$, $3$, and $-1$, respectively, so the answer is $6$.

Afterwards, $\mathrm{lastans}=6$. The encoded operations $\texttt{2 6 7}$ and $\texttt{3 7 4}$ are decoded into $\texttt{2 1 2}$ and $\texttt{3 2 3}$, respectively. Before the last query, the values at position $2$ in versions $0,1,\ldots,5$ form sequence $[-2,-2,-1,-1,1,1]$, whose maximum non-empty subarray sum is $2$.

在第一个测试用例中，对于第一次操作，$\mathrm{lastans}=0$，因此编码坐标 $1$ 被解码为位置 $2$。此时仅考虑版本 $0$。位置 $2$ 处的值为 $-3$，故答案为 $-3$。

此时 $\mathrm{lastans}=2^{64}-3=18\,446\,744\,073\,709\,551\,613$。因此，编码区间 $[18\,446\,744\,073\,709\,551\,613,\,18\,446\,744\,073\,709\,551\,615]$ 被解码为 $[1,\,3]$，而编码坐标 $18\,446\,744\,073\,709\,551\,612$ 被解码为位置 $2$。

在第二次查询之前，版本 $0$、$1$ 和 $2$ 中位置 $2$ 处的值分别为 $-3$、$-3$ 和 $3$，它们的最大非空子数组和为 $3$。

在第三次查询之前，版本 $0,1,\ldots,5$ 中位置 $2$ 处的值构成序列 $[-3,-3,3,3,3,-4]$。其中三个连续相等的值 $3$ 构成一个子数组，其和为 $9$。

注意：第一次、第二次和第三次查询分别创建了版本 $1$、$3$ 和 $6$，尽管它们并未改变数组。

在第二个测试用例中，第一次查询询问位置 $1$，因此其答案为 $1$。随后 $\mathrm{lastans}=1$，编码操作 $\texttt{1 0 3 -1}$ 被解码为 $\texttt{1 2 3 -1}$。

在第二次查询之前，版本 $0$、$1$ 和 $2$ 中位置 $3$ 处的值分别为 $3$、$3$ 和 $-1$，因此答案为 $6$。

此后，$\mathrm{lastans}=6$。编码操作 $\texttt{2 6 7}$ 和 $\texttt{3 7 4}$ 分别被解码为 $\texttt{2 1 2}$ 和 $\texttt{3 2 3}$。在最后一次查询之前，版本 $0,1,\ldots,5$ 中位置 $2$ 处的值构成序列 $[-2,-2,-1,-1,1,1]$，其最大非空子数组和为 $2$。