【题目描述】

现在有一个长度为 n 的整数序列 a1 , a2 , ..., an ，你需要支持两种操作：
1. 给定 l, r，将 al , al+1 , ..., ar 内的所有数字都加上一个整数 d；
2. 询问在序列中选一个长度为偶数的子序列，子序列的偶数项的和减去奇数项的和最大是多少，同时在保 证最大的前提下，子序列的长度最短是多少。
形式化地，即你需要选择一个子序列 i1 , i2, ..., im ，在保证 m 是偶数的前提下使得 $\sum_{j=1}^m (-1)^ja_{ij}$最大且 m 最小。

【输入格式】

输入第一行为一个整数 T，表示数据组数。
对于每一组数据：
第一行为两个整数 n, q，表示序列长度与操作次数。
第二行为 n 个整数，表示初始序列 a1 ~an。
接下来 q 行，每行表示一个询问：
1. 如果第一个整数为 0，则后面接着三个整数 l, r, d，表示在区间 [l, r] 内的数都加上 d；
2. 如果第一个整数为 1，则表示一次询问。

【输出格式】

对于每个询问，输出一行两个整数，表示子序列的偶数项减去奇数项的最大值，以及在保证最大的前提下 子序列的最小长度。

【样例数据】

样例输入    
2
5 9
9 10 7 6 8
1
0 4 5 2
0 3 5 4
1
0 2 5 -2
0 3 5 -3
0 4 5 -2
0 5 5 -4
1
4 3
2 4 3 5
1
0 3 3 3
1    
样例输出
3 4
5 2
0 0
4 4
4 2

【样例解释】

样例有两组数组，对于第一组数据：
1. 第一个询问时序列为 [9,10,8,6,8]，最优的子序列是 [9,10,6,8]，结果为-9+10-6+8=3，长度为 4；
2. 第二个询问时序列为 [9,10,11,12,14]，最优的子序列是 [-9,14]，结果为-9+14=5，长度为 2；
3. 第三个询问时序列为 [9,8,6,5,3]，最优的子序列为 []，结果为 0，长度为 0；

【数据范围】

1. 对于 10% 的测试点，1 ≤ n, q ≤ 20；
2. 对于 30% 的测试点，1 ≤ n, q ≤ 1000；
3. 对于另外 20% 的测试点，T = 1, 1 ≤ n ≤ 4 × 10^4 , 1 ≤ q ≤ 10^5 ；
4. 对于 100% 的测试点，T ≤ 5, 1 ≤ n, q ≤ 10^5 , |d| ≤ 10^5 ，且任意时刻 0 < ai < 2^31。