note:The difference is that in this version,operation 11 is different,�,�≤2×105n,m≤2×105,��≤��+1xj≤xj+1.
For a given sequence of �n intergers �a.
There are two types of operations:
1����(1≤�≤�≤�)1lrxj(1≤l≤r≤n) — for each �∈[�,�]i∈[l,r] ,change ��=∣��−��∣ai=∣ai−xj∣.
2��(1≤�≤�≤�)2lr(1≤l≤r≤n) — output ans=∑�=����ans=i=l∑rai
tips:Due to the large input data, it may be necessary to FastIO.
The input consists of multiple test cases. The first line contains a single integer �(1≤�≤5)T(1≤T≤5) — the number of test cases.
The first line of each test case contains two integers �n and �,(1≤�≤2×105,1≤�≤2×105)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≤��≤107)(0≤ai≤107)
The next �m line contains some integers ���,�,�,�opt,l,r,x (1≤���≤2,1≤�≤�≤�,0≤�≤107)(1≤opt≤2,1≤l≤r≤n,0≤x≤107) — indicating the operations.
1
5 5
1 2 3 4 5
1 1 5 3
2 1 2
2 2 4
1 2 3 5
2 1 53
2
14