Description

Xiao W and Xiao Y both enjoy a “point-picking game.” In the game, each of the two players produces a number as their “score” through some operation, and the player with the larger score wins. The rules of the “point-picking game” are as follows:

1. At the start of the game, you are given a positive integer sequence with $n$ elements, $U=(u_1, u_2, \cdots, u_n)$.
2. An index sequence $I=(i_1, i_2, \cdots, i_m)$ of $U$ is an integer sequence satisfying $1 \leq i_1 < i_2 < \cdots < i_m \leq n$ (where $m$ can be $0$, i.e., the sequence can be empty), and its corresponding subsequence of $U$ is $V=(u_{i_1}, u_{i_2}, \cdots, u_{i_m})$.
3. The score $D(I)$ corresponding to the index sequence $I=(i_1, i_2, \cdots, i_m)$ is defined as $D(I)=\sum_{p=1}^m u_{i_p} \times (-1)^p$.
4. During the game, the two players each choose an index sequence, and the one whose chosen index sequence corresponds to a larger score $D(I)$ wins.

However, in every game, Xiao W can always compute, accurately and flawlessly, the optimal index sequence that maximizes the score. To make the game more competitive, they added the following extra rules:

Ex1. Xiao W may choose a non-empty interval $[l, r]$ and increase $u_l, u_{l+1}, \cdots, u_r$ by an integer $c$ simultaneously; the new sequence replaces the original sequence $U$.

Ex2. When they play a “point-picking game” on the current sequence $U$, Xiao Y is allowed, after Xiao W has chosen the optimal index sequence $I_W=(i_1, i_2, \cdots, i_m)$, to modify $I_W$ any number of times. Each modification follows the rules below: (1) Arbitrarily choose a positive integer $k$ satisfying $2k+1 \leq 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, after some number of modifications by Xiao Y to the index sequence $I_W$ chosen by Xiao W, the corresponding score is less than or equal to $0$, then Xiao Y wins.

Now, given the information about Xiao W’s Ex1 operations, for each “point-picking game,” please help them compute: a) What is the score of the optimal index sequence that Xiao W can initially choose? b) What is the minimum number of modification operations Xiao Y needs in order to win, i.e., to make $D(I_W) \leq 0$?

Input Format

The first line of the input file joy.in contains a positive integer $T$, the number of groups of testdata. Then follow $T$ groups of data.

For each group of data, the first line contains two integers $n$ and $q$, denoting the number of elements in $U$ and the number of events, respectively.

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

The following $q$ lines each describe an event (given in chronological order). The first number in each line is either $0$ or $1$, indicating the type of the event.

If it is $0$: after the $0$ there are three integers $l$, $r$, and $c$ (all separated by single spaces), meaning Xiao W increases $u_l, u_{l+1}, \cdots, u_r$ by $c$.

If it is $1$: the two players play a “point-picking game,” and you need to output the corresponding result.

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

Output Format

The output file is joy.out. For each group of testdata, for each “point-picking game” in order, output one line containing two integers separated by a single space, $D_{max}$ and $X$, where

• $D_{max}$ is the score of the optimal index sequence that Xiao W can choose for the current sequence $U$;
• $X$ is the minimum number of modification operations that Xiao Y needs to win. If Xiao Y cannot win no matter how many operations are performed, output -1.

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

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 1 
5 -1 
0 0 
4 -1 
4 -1 

Hint

Scoring rules:

• A test point contains multiple groups of testdata. For that test point:
  • If all $D_{max}$ are correct but some $X$ is incorrect, you get 3 points.
  • If all $X$ are correct but some $D_{max}$ is incorrect, you get 7 points.
  • If all answers are correct, you get 10 points.

Sample explanation:

• The input contains two groups of testdata.
• In the first group: In the first “point-picking game,” the optimal index sequence is $(1, 2, 4, 5)$. Xiao Y needs only one modification: choose $k=1$ and non-negative integers $z_1=1$, $z_2=0$. After the modification, the index sequence becomes $(1, 3, 4, 5)$, and Xiao Y wins.
• In the third “point-picking game,” the sequence $U$ is $(9, 8, 6, 5, 3)$. Xiao W chooses the empty sequence as the optimal index sequence, yielding a score of $0$. In this case, Xiao Y cannot make any modification (nor is any modification needed), and Xiao Y already wins.

Constraints:

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

Translated by ChatGPT 5