说明：此版本与上一版本的区别在于操作 1 不同，$n, m \le 10^5$，$x$ 可以取任意可能的值。

给定一个包含 $n$ 个整数的序列 $a$。 有两种操作：

1 $l \ r \ x$ ($1 \le l \le r \le n$) —— 对于每个 $i \in [l, r]$，将 $a_i$ 修改为： $$a_i = \begin{cases} x - a_i & \text{if } a_i < x \\ x + a_i & \text{if } a_i \ge x \end{cases}$$

2 $l \ r$ ($1 \le l \le r \le n$) —— 输出 $\text{ans} = \sum_{i=l}^{r} a_i$

输入格式

输入包含多组测试数据。第一行包含一个整数 $T(1 \le T \le 1)$ —— 测试数据的组数。 每组测试数据的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^5, 1 \le m \le 10^5$) —— 序列长度和操作次数。 下一行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 10^7$)。 接下来的 $m$ 行，每行包含若干整数 $\text{opt}, l, r, x$ ($1 \le \text{opt} \le 2, 1 \le l \le r \le n, 0 \le x \le 10^7$) —— 表示操作。

输出格式

对于每个查询，输出一个整数，表示答案。

样例

样例输入 1

1
5 5
1 2 3 4 5
1 1 5 3
2 1 2
2 2 4
1 2 3 5
2 1 5

样例输出 1

3
14
32