给定正整数 $n, m > 0$，以及整数 $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$。请构造一棵包含 $n$ 个顶点 $V = \{v_1, v_2, \dots, v_n\}$ 的树 $T$，满足以下条件：对于每个满足 $a_i \neq -1$ 的顶点 $v_i$，其度数 $\deg_T(v_i)$ 除以 $m$ 的余数必须等于 $a_i$。如果 $a_i = -1$，则对 $v_i$ 的度数没有限制。

输入格式

输入的第一行包含一个整数 $t$，表示测试用例的数量（$1 \le t \le 5 \cdot 10^5$）。对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$，分别表示树中的顶点数和模数（$1 \le n \le 5 \cdot 10^5$；$1 \le m \le 2 \cdot 10^9$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示要求的余数（$-1 \le a_i < m$）。

所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，如果存在这样一棵包含 $n$ 个顶点的树，输出 "YES"（大小写不限），随后输出 $n - 1$ 行，每行包含两个整数，表示树中每条边的两个端点。否则，输出 "NO"（大小写不限）。

样例

输入样例 1

6
1 5
0
2 3
1 1
5 4
0 1 1 1 1
6 2
1 0 0 0 0 1
3 2
1 1 1
4 10
3 3 1 1

输出样例 1

YES
YES
1 2
YES
1 2
1 3
1 4
1 5
YES
1 2
2 3
3 4
4 5
5 6
NO
NO

说明

在第一个测试用例中，我们需要构建一棵 $n = 1$ 个顶点、$m = 5$ 且度数余数数组为 $b = [0]$ 的树。由于只有一个顶点，因此不能有边，所以只有一种可能的树：一个度数为 0 的孤立顶点。因为 $0 \bmod 5 = 0$，满足要求，因此答案为 "YES"。

在第二个测试用例中，我们需要一棵 $n = 2$ 个顶点、$m = 3$ 且余数数组为 $b = [1, 1]$ 的树，这意味着两个顶点的度数模 3 都必须同余于 1。在两个顶点上，只有一棵树：单条边 1-2。其度数为 $(1, 1)$，确实满足 $1 \bmod 3 = 1$，因此答案为 "YES"，输出 "1 2" 是有效的。

在第三个测试用例中，我们需要 $n = 5$，$m = 4$，余数数组为 $b = [0, 1, 1, 1, 1]$：第一个顶点的度数必须能被 4 整除，而其他四个顶点的度数必须满足 $\equiv 1 \pmod 4$。一个自然的构造是以顶点 1 为中心的星形图：将 1 连接到所有其他顶点。此时 $\deg(1) = 4$ 且 $4 \bmod 4 = 0$，而 2, 3, 4, 5 的度数均为 1 且 $1 \bmod 4 = 1$。因此，答案为 "YES"，边 "1 2"、"1 3"、"1 4"、"1 5" 是可行的。

在第四个测试用例中，我们需要一棵 $n = 6$，$m = 2$，余数数组为 $b = [1, 0, 0, 0, 0, 1]$ 的树，即两端顶点的度数必须为奇数，而中间四个顶点的度数必须为偶数。模 2 意义下，这纯粹是奇偶性限制。简单路径 1-2-3-4-5-6 完美契合：顶点 1 和 6 的度数为 1（奇数），而顶点 2, 3, 4, 5 的度数为 2（偶数）。因此答案为 "YES"，路径上的边是正确的。

在第五个测试用例中，我们被要求在 $n = 3$ 且 $m = 2$、$b = [1, 1, 1]$ 的情况下构建一个图（因此特别地，一棵树），所以每个顶点的度数都必须为奇数。这是不可能的：在任何无向图中，奇数度顶点的个数总是偶数，因此对于任何边集，都不可能出现三个奇数度数。因此，判定为 "NO"。

在第六个测试用例中，我们有 $n = 4$，$m = 10$，$b = [3, 3, 1, 1]$。由于 $m > n - 1 = 3$，模 10 的余数等于度数本身，因此我们要求度数恰好为 $\deg = [3, 3, 1, 1]$。这迫使两个顶点与所有其他顶点相邻（在 4 顶点图中度数为 3），而当 $n > 2$ 时，任何这样的一对顶点必然与任意第三个顶点一起构成一个环。树不能包含环，因此判定也为 "NO"。