Bessie 正在玩一款电子游戏，她需要击败一排 $N$ 个敌人，这些敌人的初始生命值（HP）由列表 $v_1\dots v_N$ 给出（$1\le N\le 2\cdot 10^5, 0\le v_i\le 10^9$）。在一次攻击中，她可以执行以下步骤：
- 选择一个 $i$，使得第 $i$ 个敌人仍然存活（即 $v_i>0$）。
- 对第 $i$ 个敌人以及所有与它相邻且仍然存活的敌人造成 1 点伤害。具体来说，对于每个 $j\in [\max(i-1, 1), \min(i+1, N)]$，如果 $v_j>0$，则将 $v_j$ 减去 1。
请帮助 Bessie 确定她击败所有敌人（即将所有 $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$），表示 Bessie 连续攻击第 $i$ 个敌人 $r$ 次。
根据 $M$ 的值，$R$ 必须满足以下约束之一：
- $M=1$：$R\le 2N$（可以证明这样的构造总是存在的）。
- $M=2$：$R\le f(N)$，其中 $f(N)$ 是所有长度为 $N$ 的列表中，最少轮次数的最大值。
输入格式
每个输入包含 $T$（$1\le T\le 10^5$）个独立的测试用例。第一行包含 $T$ 和 $M$。
每个测试用例的格式如下：
第一行包含 $N$。
第二行包含 $v_1\dots v_N$。
保证所有测试用例的 $N$ 之和不超过 $10^6$。
输出格式
对于每个测试用例，第一行输出最少攻击次数。
如果 $M>0$，则按照上述规定额外输出 $R+1$ 行。任何合法的构造方案均可被接受。
样例
样例输入 1
2 0
1
10
3
6 1 7样例输出 1
10
12说明 1
对于第二个测试用例，你可以先对中间的敌人进行一次攻击。此后，以任意顺序对第一个敌人进行五次攻击，并对最后一个敌人进行六次攻击。
样例输入 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说明 2
该输出得分，因为对于测试用例 1，$R=2\le 2$，对于测试用例 2，$R=4\le 6$。
样例输入 3
2 2
1
10
3
6 1 7样例输出 3
10
1
1 10
12
3
2 1
3 6
1 5说明 3
该输出得分，因为对于测试用例 1，$R=1\le f(1)$，对于测试用例 2，$R=3\le f(3)$。
子任务
- 测试点 4-7：$M=0$
- 测试点 8-11：$M=1$
- 测试点 12-13：$M=2$