Problem Description

**note:The difference is that in this version,operation $1$ is different,$n,m \leq 2\times 10^5$,$x_j \leq x_{j+1}$.**

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

There are two types of operations:

$1\quad l \quad r \quad x_j \quad (1≤ l ≤ r ≤ n)$ — for each $i \in [l,r] $ ,change $ a_i = | a_i - x_j |$.

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

tips:Due to the large input data, it may be necessary to FastIO.

Input

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

The first line of each test case contains two integers $n$ and $m,(1 \leq n \leq 2\times 10^5,1 \leq m \leq 2\times 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 $opt,l,r,x$ $(1 \leq 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
2
14