Description

note:The difference is that in this version,operation 1 is different,n, m ≤ 105, x can take any possible value. For a given sequence of n intergers a. There are two types of operations:

1 l r x (1 ≤ l ≤ r ≤ n) — for each i ∈ [l, r] ,change ai =

2 l r (1 ≤ l ≤ r ≤ n) — output ans = Σ ai i=l

Input

The input consists of multiple test cases. The first line contains a single integer T (1 ≤ T ≤ 1) — the number of test cases. The first line of each test case contains two integers n and m, (1 ≤ n ≤ 105, 1 ≤ m ≤ 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
14
32