Bessie is playing a video game where she needs to defeat a line of N enemies with initial HPs given by the list v1…vN (1≤N≤2⋅105,0≤vi≤109). In one attack, she can perform the following sequence of steps:
Choose i such that the ith enemy is still alive (that is, vi>0).
Deal one damage to the ith enemy and all enemies adjacent to it that are still alive. Specifically, for each j∈[max(i−1,1),min(i+1,N)], if vj>0, subtract one from vj.
Help Bessie determine the minimum number of attacks she needs to defeat all enemies (that is, reduce all vi to 0).
Additionally, you are given a parameter M (0≤M≤2). If M>0, please output a construction achieving the minimum number of attacks with a small number of runs, where a run consists of attacking the same enemy consecutively.
Let R be the number of runs in your construction. Your construction should be in the following format: output R on its own line, followed by R lines each containing two integers i and r (1≤i≤N,0≤r≤109), meaning that Bessie attacks the i-th enemy r times consecutively.
Depending on the value of M, R must satisfy one of the following constraints:
M=1: R≤2N(it can be proven that a construction always exists).
M=2: R≤f(N), where f(N) is the maximum minimum number of runs over all lists of length N.
INPUT FORMAT (input arrives from the terminal / stdin):
Each input consists of T (1≤T≤105) independent tests. The first line contains T
and M.
Each test is specified as follows:
The first line contains N.
The second line contains v1…vN.
It is guaranteed that the sum of N over all tests does not exceed 106 .
OUTPUT FORMAT (print output to the terminal / stdout):
For each test, output the minimum number of attacks on the first line.
Then if M>0, output R+1 additional lines as specified above. Any valid construction will be accepted.
SAMPLE INPUT:
2 0
1
10
3
6 1 7
SAMPLE OUTPUT:
10
12
For the second test, you can first perform one attack on the middle enemy. Then, in any order after that, perform five attacks on the first enemy and six attacks on the last enemy.
SAMPLE INPUT:
2 1
1
10
3
6 1 7
SAMPLE OUTPUT:
10
2
1 0
1 10
12
4
2 1
1 5
3 2
3 4
This output receives credit because R=2≤2 for test 1 and R=4≤6 for test 2.
SAMPLE INPUT:
2 2
1
10
3
6 1 7
SAMPLE OUTPUT:
10
1
1 10
12
3
2 1
3 6
1 5
This output receives credit because R=1≤f(1) for test 1 and R=3≤f(3) for test 2.
SCORING:
Inputs 4-7: M=0
Inputs 8-11: M=1
Input 12-13: M=2
Problem credits: Benjamin Qi