注意：此版本与之前版本的区别在于操作 1 不同，$n, m \le 2 \times 10^5, x_j \le x_{j+1}$。

给定一个包含 $n$ 个整数的序列 $a$。

有两种操作：

1. $1 \ l \ r \ x_j$ ($1 \le l \le r \le n$) —— 对于每个 $i \in [l, r]$，将 $a_i$ 修改为 $a_i = |a_i - x_j|$。
2. $2 \ l \ r$ ($1 \le l \le r \le n$) —— 输出 $ans = \sum_{i=l}^{r} a_i$。

提示：由于输入数据量较大，可能需要使用快速输入输出（FastIO）。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 5$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 2 \times 10^5, 1 \le m \le 2 \times 10^5$)，分别表示序列长度和操作次数。

下一行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 10^7$)。

接下来的 $m$ 行，每行包含一些整数 $opt, l, r, x$ ($1 \le 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
2
14