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

There are two types of operations:

$1 \quad l \quad r \quad x_j \qquad (1 ≤ l ≤ r ≤ n, x_j \le x_{j+1})$ — for each $i \in [l, r]$, change $a_i = |a_i − x_j|$.

$2 \quad l \quad r \qquad (1 ≤ l ≤ r ≤ n)$ — output ans = $\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 ≤ T ≤ 5$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$, ($1 ≤ n ≤ 2 \cdot 10^5$, $1 ≤ m ≤ 2 \cdot 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.

Output

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

Example

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

Limitation

Time limit: 9 second

Memory limit: 512 megabytes