Diberikan bilangan bulat $n, m > 0$, serta bilangan bulat $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$. Konstruksikan sebuah pohon $T$ dengan $n$ simpul $V = \{v_1, v_2, \dots, v_n\}$ yang memenuhi kondisi berikut: untuk setiap simpul $v_i$ dengan $a_i \ne -1$, sisa pembagian derajat $\deg_T(v_i)$ oleh $m$ harus sama dengan $a_i$. Jika $a_i = -1$, maka tidak ada batasan pada derajat $v_i$.

Masukan

Baris pertama masukan berisi sebuah bilangan bulat $t$, banyaknya kasus uji ($1 \le t \le 5 \cdot 10^5$). Untuk setiap kasus uji:

Baris pertama berisi dua bilangan bulat, $n$ dan $m$, yang menyatakan banyaknya simpul pada pohon dan modulus ($1 \le n \le 5 \cdot 10^5$; $1 \le m \le 2 \cdot 10^9$).

Baris berikutnya berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ yang menyatakan sisa pembagian yang diminta ($-1 \le a_i < m$).

Jumlah dari $n$ di seluruh kasus uji tidak melebihi $5 \cdot 10^5$.

Keluaran

Untuk setiap kasus uji, jika pohon dengan $n$ simpul seperti itu ada, keluarkan "YES" (dalam huruf besar/kecil apa pun), diikuti oleh $n - 1$ baris yang masing-masing berisi dua bilangan bulat yang menyatakan titik-titik ujung dari setiap sisi. Jika tidak, keluarkan "NO" (dalam huruf besar/kecil apa pun).

Contoh

Masukan

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

Keluaran

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

Catatan

Pada kasus uji pertama, kita diminta membuat sebuah pohon dengan $n = 1$ simpul, $m = 5$, dan larik sisa derajat $b = [0]$. Dengan hanya satu simpul, tidak mungkin ada sisi, sehingga hanya ada tepat satu pohon yang mungkin: satu simpul tunggal berderajat $0$. Karena $0 \bmod 5 = 0$, pohon ini memenuhi syarat; maka jawabannya adalah "YES".

Pada kasus uji kedua, kita membutuhkan sebuah pohon pada $n = 2$ simpul dengan $m = 3$ dan sisa $b = [1, 1]$, yang berarti kedua derajat harus kongruen dengan $1$ modulo $3$. Pada dua simpul, hanya ada satu pohon: satu sisi tunggal $1-2$. Derajatnya adalah $(1, 1)$ dan memang $1 \bmod 3 = 1$, sehingga jawabannya adalah "YES", dan mencetak "1 2" adalah valid.

Pada kasus uji ketiga, kita membutuhkan $n = 5$, $m = 4$, dengan sisa $b = [0, 1, 1, 1, 1]$: simpul pertama harus memiliki derajat yang habis dibagi $4$, sedangkan empat simpul lainnya harus memiliki $\text{degree} \equiv 1 \pmod 4$. Konstruksi yang alami adalah graf bintang yang berpusat di simpul $1$: hubungkan $1$ ke setiap simpul lainnya. Maka $\deg(1) = 4$ dan $4 \bmod 4 = 0$, sementara masing-masing dari $2, 3, 4, 5$ memiliki derajat $1$ dan $1 \bmod 4 = 1$. Oleh karena itu, jawabannya adalah "YES", dan sisi-sisi "1 2", "1 3", "1 4", "1 5" memenuhi syarat.

Pada kasus uji keempat, kita membutuhkan sebuah pohon dengan $n = 6$, $m = 2$, sisa $b = [1, 0, 0, 0, 0, 1]$, yaitu simpul-simpul ujung harus berderajat ganjil dan empat simpul tengah harus berderajat genap. Dalam modulo $2$, ini murni merupakan batasan paritas. Lintasan sederhana $1-2-3-4-5-6$ sangat cocok: simpul $1$ dan $6$ berderajat $1$ (ganjil), dan simpul $2, 3, 4, 5$ berderajat $2$ (genap). Maka jawabannya adalah "YES", dan sisi-sisi lintasan tersebut benar.

Pada kasus uji kelima, kita diminta membangun sebuah graf (dan dengan demikian, khususnya, sebuah pohon) pada $n = 3$ dengan $m = 2$ dan $b = [1, 1, 1]$, sehingga setiap simpul harus berderajat ganjil. Hal ini tidak mungkin: pada setiap graf tak berarah, banyaknya simpul berderajat ganjil selalu genap, sehingga memiliki tiga derajat ganjil tidak mungkin terjadi untuk himpunan sisi mana pun. Oleh karena itu, keputusannya adalah "NO".

Pada kasus uji keenam, kita memiliki $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$. Karena $m > n - 1 = 3$, sisa modulo $10$ sama dengan derajat itu sendiri, sehingga kita memerlukan tepat $\deg = [3, 3, 1, 1]$. Hal itu memaksa dua simpul untuk bertetangga dengan semua simpul lainnya (derajat $3$ pada graf $4$ simpul), dan ketika $n > 2$, pasangan seperti itu pasti membentuk siklus bersama dengan simpul ketiga mana pun. Sebuah pohon tidak boleh mengandung siklus, sehingga keputusannya juga "NO".