note:The difference is that in this version,operation 1 is different,$n,m≤2×10^5,x_j≤x_j+1$.

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

There are two types of operations:

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

$2\ l\ r(1≤l≤r≤n)$ — output $ans=∑_{i=l}^ra_i$

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

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

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

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

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

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