Little W and Little Y both enjoy playing a "Point-Matching Game." In the game, two people each generate a number as their "score" through certain operations, and the person with the higher score wins. The rules of the "Point-Matching Game" are as follows:

1. At the start of the game, a sequence of $n$ positive integers $U = (u_1, u_2, \dots, u_n)$ is given.
2. An index sequence $I = (i_1, i_2, \dots, i_m)$ of $U$ is defined as a sequence of integers satisfying $1 \le i_1 < i_2 < \dots < i_m \le n$ (where $m$ can be 0, meaning the sequence can be empty), and its corresponding subsequence of $U$ is $(u_{i_1}, u_{i_2}, \dots, u_{i_m})$.
3. The score $D(I)$ corresponding to the index sequence $I = (i_1, i_2, \dots, i_m)$ is defined as: $$D(I) = \sum_{p=1}^{m} u_{i_p} * (-1)^p$$
4. When playing the game, both people choose an index sequence, and the person whose chosen index sequence has the higher score $D(I)$ wins.

However, in every game, Little W is always able to accurately calculate the optimal index sequence with the maximum score. To make the game more competitive, they have established the following additional rules:

Ex1. Little W can choose a non-empty interval $[l, r]$ and increase $u_l, u_{l+1}, \dots, u_r$ by an integer $c$ simultaneously, and the new sequence will replace the original sequence $U$.

Ex2. When they play a "Point-Matching Game" with the current sequence $U$, Little Y is allowed to perform any number of modification operations on the optimal index sequence $I_W = (i_1, i_2, \dots, i_m)$ chosen by Little W. Each modification operation follows these rules: (1) Choose any positive integer $k$ satisfying $2k+1 \le m$, and two non-negative integers $z_1, z_2$ satisfying $i_{2k} + z_1 < i_{2k+1} - z_2$; (2) Change $i_{2k}$ to $i_{2k} + z_1$, and change $i_{2k+1}$ to $i_{2k+1} - z_2$.

If the score corresponding to the index sequence $I_W$ chosen by Little W becomes less than or equal to 0 after some modification operations by Little Y, then Little Y wins.

Given the information about the Ex1 operations performed by Little W, please help them calculate for each "Point-Matching Game": a) What is the score corresponding to the optimal index sequence that Little W can initially choose? b) What is the minimum number of modification operations Little Y needs to perform to win? That is, to make $D(I_W) \le 0$.

Input

The first line of the input file contains a positive integer $T$, representing the number of test cases. This is followed by $T$ sets of data.

The first line of each data set contains two integers $n$ and $q$, representing the number of elements in $U$ and the number of events, respectively.

The next line contains $n$ positive integers separated by spaces, where the $i$-th integer is the $i$-th element $u_i$ of the initial sequence.

The next $q$ lines each represent an event (input in the order of occurrence). The first number of each line is either 0 or 1, representing the type of event.

If it is 0: there are three more integers $l, r$, and $c$ following 0 (each of these four numbers is separated by a space), indicating that Little W increases $u_l, u_{l+1}, \dots, u_r$ by $c$.

If it is 1: it indicates that the two people play a "Point-Matching Game," and you need to output the corresponding results.

The input data guarantees that all elements in sequence $U$ are always positive integers.

Output

For each test case, output one line containing two integers $D_{\max}$ and $X$ separated by a space for each "Point-Matching Game," where:

$D_{\max}$ is the score corresponding to the optimal index sequence that Little W can choose for the current sequence $U$; $X$ is the minimum number of modification operations Little Y needs to perform to win. If Little Y cannot win regardless of the number of operations, output -1.

The data guarantees that the optimal index sequence is always unique.

Subtasks

For 10% of the data, $n, q \le 13$; For 30% of the data, $n, q \le 1000$; For another 20% of the data, $T=1$ and $n \le 40000$; For 100% of the data, $T \le 3$ and $n, q \le 10^5$, while the initial sequence $U$ satisfies $0 < u_i < 2^{31}$ and $|c| < 10^5$.

Examples

Input 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

Output 1

3 1 
5 -1 
0 0 
4 -1 
4 -1

Note

The input data contains two test cases.

In the first test case: During the first "Point-Matching Game," the optimal index sequence is $(1, 2, 4, 5)$. Little Y only needs to perform one modification operation: choose $k=1$, and non-negative integers $z_1=1, z_2=0$. After this modification operation, the index sequence becomes $(1, 3, 4, 5)$, and Little Y wins.

During the third "Point-Matching Game," the sequence $U$ is $(9, 8, 6, 5, 3)$, and the optimal index sequence chosen by Little W is the empty sequence, resulting in a score of 0. In this case, Little Y cannot perform any modification operations (nor does Little Y need to perform any), and Little Y has already won directly.