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

There are two types of operations:

$1 \quad l \quad r \quad x \qquad (1 ≤ l ≤ r ≤ n)$ — for each $i \in [l, r]$, if $a_i < x$, change $a_i = x - a_i$, else change $a_i = x + a_i$.

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

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 ≤ 10^5$, $1 ≤ m ≤ 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
14
32

Limitation

Time limit: 8 second

Memory limit: 512 megabytes