문제

가은이는 $N$명의 적을 물리쳐야 하는 비디오 게임을 하고 있다. 각 적의 초기 체력은 $v_1, \dots, v_N$으로 주어진다. ($1 \le N \le 2 \cdot 10^5; 0 \le v_i \le 10^9$) 가은이는 한 번의 공격으로 다음과 같은 과정을 수행할 수 있다.

1. 살아있는(즉, $v_i > 0$인) 적 $i$를 선택한다.
2. 적 $i$와 그에 인접하며 살아있는 모든 적에게 $1$의 피해를 준다. 구체적으로, 각 $j \in [\max(i-1, 1), \min(i+1, N)]$에 대해 $v_j > 0$이면 $v_j$를 $1$ 감소시킨다.

가은이를 도와 모든 적을 물리치기(모든 $v_i$를 $0$으로 만들기) 위해 필요한 최소 공격 횟수를 구하라.

추가로, 매개변수 $M$($0 \le M \le 2$)이 주어진다. 만약 $M > 0$이라면, 최소 공격 횟수를 달성하면서 적은 수의 **런(run)**을 사용하는 구성을 출력해야 한다. 여기서 런이란 동일한 적을 연속해서 공격하는 단위를 의미한다.

구성을 출력할 때 런의 개수를 $R$이라 하면, 먼저 $R$을 한 줄에 출력하고 이어서 $R$개의 줄에 각각 두 정수 $i$와 $r$($1 \le i \le N; 0 \le r \le 10^9$)을 출력한다. 이는 가은이가 $i$번째 적을 연속해서 $r$번 공격했음을 의미한다.

$M$의 값에 따라 $R$은 다음 조건을 만족해야 한다.

• $M=1$: $R \le 2N$ (이러한 구성이 항상 존재함이 증명되어 있다).
• $M=2$: $R \le f(N)$, 여기서 $f(N)$은 길이가 $N$인 모든 체력 목록에 대해 가능한 '최소 런 개수'의 최댓값이다.

입력

첫째 줄에 테스트 케이스의 수 $T$와 매개변수 $M$이 주어진다. ($1 \le T \le 10^5; 0 \le M \le 2$)

각 테스트 케이스는 다음과 같이 구성된다:

첫째 줄에 $N$이 주어진다.

둘째 줄에 $v_1, \dots, v_N$이 공백으로 구분되어 주어진다.

모든 테스트 케이스에 대한 $N$의 합은 $10^6$을 초과하지 않는다.

출력

각 테스트 케이스마다 첫째 줄에 모든 적을 물리치기 위한 최소 공격 횟수를 출력한다.

만약 $M > 0$이라면, 위에 명시된 형식으로 $R$과 그 뒤에 $R$개의 줄을 추가로 출력한다. 조건을 만족하는 구성이 여러 가지라면 그중 아무거나 하나를 출력한다.

예제 입력 1

2 0
1
10
3
6 1 7

예제 출력 1

10
12

예제 입력 2

2 1
1
10
3
6 1 7

예제 출력 2

10
2
1 0
1 10
12
4
2 1
1 5
3 2
3 4

예제 입력 3

2 2
1
10
3
6 1 7

예제 출력 3

10
1
1 10
12
3
2 1
3 6
1 5

데이터 범위

• 입력 4-7: $M=0$
• 입력 8-11: $M=1$
• 입력 12-13: $M=2$