Problem Description

**note:The difference is that in this version,operation $1$ is different,$n,m \leq 10^5$, $x $ can take any possible value.**

For a given sequence of $n$ intergers $a$.

There are two types of operations:

$1 \quad l \quad r \quad x \quad (1≤ l ≤ r ≤ n)$ — for each $i \in [l,r] $ ,change $a_i = \begin{cases} x - a_i &\text{if } a_i < x \\\\
x + a_i &\text{if } a_i \geq x \end{cases}$.

$2 \quad l \quad r \quad (1≤ l ≤ r ≤ n)$ — output $\text{ans}=\displaystyle\sum_{i=l}^{r}{a_i}$

Input

The input consists of multiple test cases. The first line contains a single integer $T(1 \leq T \leq 1)$ — the number of test cases.

The first line of each test case contains two integers $n$ and $m,(1 \leq n \leq 10^5,1 \leq m \leq 10^5)$— the length of sequence and the number of operations.

The next line contains $n$ integer $a_i(0 \leq a_i \leq 10^7)$

The next $m$ line contains some integers $\text{opt},l,r,x$ $(1 \leq \text{opt} \leq 2,1 \leq l \leq r \leq n,0 \leq x \leq 10^7)$ — indicating the operations.

Output

For each query, output an interger in a single line indicating the $\text{ans}$.

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

3
14
32