Easy problem II

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

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
14
32

Source

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