Description

note:The difference is that in this version,operation 1 is different,n, m ≤ 2 × 105,xj ≤ xj+1. For a given sequence of n intergers a. There are two types of operations: 1 l r xj (1 ≤ l ≤ r ≤ n) — for each i ∈ [l, r] ,change ai = |ai − xj|. 2 l r (1 ≤ l ≤ r ≤ n) — output ans = Σ ai i=l 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 × 105, 1 ≤ m ≤ 2 × 105) — the length of sequence and the number of operations. The next line contains n integer ai (0 ≤ ai ≤ 107) The next m line contains some integers opt, l, r, x (1 ≤ opt ≤ 2, 1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 107) — indicating the operations.

ouput

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

Example

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

ouput：

3
2
14