再次深入研究量子色动力学的复杂理论后，Little Cyan Fish 对色荷的概念产生了浓厚的兴趣。为了测试你对该理论的理解，他向你提出了以下任务。

给定一个整数 $n$ 和 $k$ 个非负整数 $c_1, c_2, \dots, c_k$，请构造一个具有 $n$ 个顶点的无向图，满足以下条件：

• 每条边都有一个颜色 $w_i$，且 $w_i$ 是 $[1, k]$ 范围内的整数。
• 对于所有 $1 \le i, j \le n$ 和所有 $1 \le t \le k$，存在一条连接顶点 $i$ 和 $j$ 的路径，使得该路径上颜色为 $t$ 的边的数量不超过 $c_t$。（注意：不同 $t$ 对应的路径不必相同。）
• 所构造图中的边数最少。

题目保证至少存在一个可行解。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 5 \times 10^4$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n, k$ ($2 \le n, k \le 10^5$)。

下一行包含 $k$ 个整数 $c_i$ ($0 \le c_i \le n$)。

题目保证至少存在一个可行解，且所有测试用例中 $n$ 的总和与 $k$ 的总和均不超过 $10^5$。

输出格式

对于每个测试用例，首先输出一行一个整数 $m$，表示你所构造图中的边数。

接下来 $m$ 行描述你的图。第 $i$ 行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n, 1 \le w_i \le k$)，表示一条连接顶点 $u_i$ 和 $v_i$ 且颜色为 $w_i$ 的边。

样例

输入 1

3
4 2
1 1
2 2
0 0
5 2
3 1

输出 1

4
1 2 1
2 3 2
3 4 2
4 1 2
2
1 2 1
1 2 2
4
1 2 1
2 3 2
3 4 1
3 5 1