On vous donne des entiers $n, m > 0$, ainsi que des entiers $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$. Construisez un arbre $T$ à $n$ sommets $V = \{v_1, v_2, \dots, v_n\}$ vérifiant la condition suivante : pour chaque sommet $v_i$ tel que $a_i \ne -1$, le reste de la division du degré $\deg_T(v_i)$ par $m$ doit être égal à $a_i$. Si $a_i = -1$, alors il n'y a aucune restriction sur le degré de $v_i$.

Entrée

La première ligne de l'entrée contient un entier $t$, le nombre de cas de test ($1 \le t \le 5 \cdot 10^5$). Pour chaque cas de test :

La première ligne contient deux entiers, $n$ et $m$, désignant le nombre de sommets dans l'arbre et le modulo ($1 \le n \le 5 \cdot 10^5$ ; $1 \le m \le 2 \cdot 10^9$).

La ligne suivante contient $n$ entiers $a_1, a_2, \dots, a_n$ désignant les restes requis ($-1 \le a_i < m$).

La somme de $n$ sur tous les cas de test ne dépasse pas $5 \cdot 10^5$.

Sortie

Pour chaque cas de test, s'il existe un tel arbre à $n$ sommets, affichez « YES » (quelle que soit la casse), suivi de $n - 1$ lignes contenant chacune deux entiers désignant les extrémités de chaque arête. Sinon, affichez « NO » (quelle que soit la casse).

Exemple

Entrée

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

Sortie

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

Note

Dans le premier cas de test, on nous demande de construire un arbre avec $n = 1$ sommet, $m = 5$ et un tableau de restes de degrés $b = [0]$. Avec un seul sommet, il ne peut y avoir aucune arête, il y a donc exactement un arbre possible : un unique sommet de degré $0$. Comme $0 \bmod 5 = 0$, il satisfait à l'exigence ; la réponse est donc « YES ».

Dans le deuxième cas de test, nous avons besoin d'un arbre sur $n = 2$ sommets avec $m = 3$ et des restes $b = [1, 1]$, ce qui signifie que les deux degrés doivent être congrus à $1$ modulo $3$. Sur deux sommets, il n'existe qu'un seul arbre : l'unique arête $1-2$. Ses degrés sont $(1, 1)$ et on a bien $1 \bmod 3 = 1$, donc la réponse est « YES », et afficher « 1 2 » est valide.

Dans le troisième cas de test, nous avons besoin de $n = 5$, $m = 4$, avec les restes $b = [0, 1, 1, 1, 1]$ : le premier sommet doit avoir un degré divisible par $4$, tandis que les quatre autres sommets doivent avoir $\text{degree} \equiv 1 \pmod 4$. Une construction naturelle est une étoile centrée au sommet $1$ : relier $1$ à tous les autres sommets. Alors $\deg(1) = 4$ et $4 \bmod 4 = 0$, tandis que chacun des sommets $2, 3, 4, 5$ a pour degré $1$ et $1 \bmod 4 = 1$. Par conséquent, la réponse est « YES », et les arêtes « 1 2 », « 1 3 », « 1 4 », « 1 5 » conviennent.

Dans le quatrième cas de test, nous avons besoin d'un arbre avec $n = 6$, $m = 2$, et les restes $b = [1, 0, 0, 0, 0, 1]$, c'est-à-dire que les extrémités doivent avoir un degré impair et les quatre sommets intermédiaires doivent avoir un degré pair. Modulo $2$, il s'agit purement d'une contrainte de parité. Le chemin simple $1-2-3-4-5-6$ convient parfaitement : les sommets $1$ et $6$ ont pour degré $1$ (impair), et les sommets $2, 3, 4, 5$ ont pour degré $2$ (pair). D'où la réponse « YES », et les arêtes du chemin sont correctes.

Dans le cinquième cas de test, on nous demande de construire un graphe (et donc, en particulier, un arbre) sur $n = 3$ avec $m = 2$ et $b = [1, 1, 1]$, de sorte que chaque sommet doit avoir un degré impair. C'est impossible : dans tout graphe non orienté, le nombre de sommets de degré impair est toujours pair, il est donc impossible d'avoir trois degrés impairs quel que soit l'ensemble d'arêtes. Par conséquent, le verdict est « NO ».

Dans le sixième cas de test, nous avons $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$. Comme $m > n - 1 = 3$, le reste modulo $10$ est égal au degré lui-même, nous exigeons donc exactement $\deg = [3, 3, 1, 1]$. Cela oblige deux sommets à être adjacents à tous les autres (degré $3$ dans un graphe à $4$ sommets), et lorsque $n > 2$, une telle paire forme nécessairement un cycle avec n'importe quel troisième sommet. Un arbre ne pouvant contenir de cycles, le verdict est également « NO ».