Easy problem I

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}$.

Sample Input

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

Sample Output

3
2
14

Source

2023“钉耙编程”中国大学生算法设计超级联赛（1）