Dane są liczby całkowite $n, m > 0$, a także liczby całkowite $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$. Skonstruuj drzewo $T$ o $n$ wierzchołkach $V = \{v_1, v_2, \dots, v_n\}$ spełniające następujący warunek: dla każdego wierzchołka $v_i$, dla którego $a_i \ne -1$, reszta z dzielenia stopnia $\deg_T(v_i)$ przez $m$ musi być równa $a_i$. Jeśli $a_i = -1$, to na stopień wierzchołka $v_i$ nie ma żadnych ograniczeń.

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą $t$, liczbę przypadków testowych ($1 \le t \le 5 \cdot 10^5$). Dla każdego przypadku testowego:

Pierwszy wiersz zawiera dwie liczby całkowite, $n$ oraz $m$, oznaczające liczbę wierzchołków w drzewie oraz moduł ($1 \le n \le 5 \cdot 10^5$; $1 \le m \le 2 \cdot 10^9$).

Następny wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ oznaczających wymagane reszty ($-1 \le a_i < m$).

Suma $n$ po wszystkich przypadkach testowych nie przekracza $5 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego, jeśli takie drzewo o $n$ wierzchołkach istnieje, wypisz „YES” (wielkość liter dowolna), a następnie $n - 1$ wierszy zawierających po dwie liczby całkowite oznaczające końce każdej krawędzi. W przeciwnym razie wypisz „NO” (wielkość liter dowolna).

Przykład

Wejście

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

Wyjście

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

Uwaga

W pierwszym przypadku testowym mamy zbudować drzewo o $n = 1$ wierzchołku, $m = 5$ i tablicy reszt stopni $b = [0]$. Przy tylko jednym wierzchołku nie może być żadnych krawędzi, więc istnieje dokładnie jedno możliwe drzewo: pojedynczy wierzchołek stopnia $0$. Ponieważ $0 \bmod 5 = 0$, spełnia ono wymaganie; stąd odpowiedź brzmi „YES”.

W drugim przypadku testowym potrzebujemy drzewa na $n = 2$ wierzchołkach z $m = 3$ i resztami $b = [1, 1]$, co oznacza, że oba stopnie muszą przystawać do $1$ modulo $3$. Na dwóch wierzchołkach istnieje tylko jedno drzewo: pojedyncza krawędź $1-2$. Jego stopnie to $(1, 1)$ i rzeczywiście $1 \bmod 3 = 1$, więc odpowiedzią jest „YES”, a wypisanie „1 2” jest poprawne.

W trzecim przypadku testowym potrzebujemy $n = 5$, $m = 4$ z resztami $b = [0, 1, 1, 1, 1]$: pierwszy wierzchołek musi mieć stopień podzielny przez $4$, natomiast pozostałe cztery wierzchołki muszą spełniać $\text{degree} \equiv 1 \pmod 4$. Naturalną konstrukcją jest gwiazda o środku w wierzchołku $1$: łączymy $1$ z każdym innym wierzchołkiem. Wówczas $\deg(1) = 4$ oraz $4 \bmod 4 = 0$, podczas gdy każdy z wierzchołków $2, 3, 4, 5$ ma stopień $1$ oraz $1 \bmod 4 = 1$. Zatem odpowiedzią jest „YES”, a krawędzie „1 2”, „1 3”, „1 4”, „1 5” są poprawne.

W czwartym przypadku testowym potrzebujemy drzewa o $n = 6$, $m = 2$, z resztami $b = [1, 0, 0, 0, 0, 1]$, tj. końce muszą mieć stopień nieparzysty, a cztery środkowe wierzchołki stopień parzysty. Modulo $2$ jest to wyłącznie warunek parzystości. Ścieżka prosta $1-2-3-4-5-6$ pasuje idealnie: wierzchołki $1$ i $6$ mają stopień $1$ (nieparzysty), a wierzchołki $2, 3, 4, 5$ mają stopień $2$ (parzysty). Stąd odpowiedzią jest „YES”, a krawędzie ścieżki są poprawne.

W piątym przypadku testowym mamy zbudować graf (a więc w szczególności drzewo) na $n = 3$ z $m = 2$ i $b = [1, 1, 1]$, czyli każdy wierzchołek musi mieć nieparzysty stopień. Jest to niemożliwe: w każdym grafie nieskierowanym liczba wierzchołków o nieparzystym stopniu jest zawsze parzysta, więc trzy nieparzyste stopnie nie mogą wystąpić dla żadnego zbioru krawędzi. Zatem werdykt to „NO”.

W szóstym przypadku testowym mamy $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$. Ponieważ $m > n - 1 = 3$, reszta modulo $10$ jest równa samemu stopniowi, więc wymagamy dokładnie $\deg = [3, 3, 1, 1]$. Wymusza to, aby dwa wierzchołki były połączone ze wszystkimi pozostałymi (stopień $3$ w grafie $4$-wierzchołkowym), a gdy $n > 2$, każda taka para nieuchronnie tworzy cykl wraz z dowolnym trzecim wierzchołkiem. Drzewo nie może zawierać cykli, więc werdykt to również „NO”.