Gefnar eru heiltölur $n, m > 0$, ásamt heiltölum $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$. Smíðið tré $T$ með $n$ hnútum $V = \{v_1, v_2, \dots, v_n\}$ sem uppfyllir eftirfarandi skilyrði: fyrir hvern hnút $v_i$ þar sem $a_i \ne -1$ verður afgangurinn þegar gráðunni $\deg_T(v_i)$ er deilt með $m$ að vera jafn $a_i$. Ef $a_i = -1$, þá eru engar takmarkanir á gráðu $v_i$.

Inntak

Fyrsta línan í inntakinu inniheldur heiltölu $t$, fjölda prófunartilvika ($1 \le t \le 5 \cdot 10^5$). Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur tvær heiltölur, $n$ og $m$, sem tákna fjölda hnúta í trénu og deilinn ($1 \le n \le 5 \cdot 10^5$; $1 \le m \le 2 \cdot 10^9$).

Næsta lína inniheldur $n$ heiltölur $a_1, a_2, \dots, a_n$ sem tákna umbeðna afganga ($-1 \le a_i < m$).

Summa $n$ yfir öll prófunartilvik fer ekki yfir $5 \cdot 10^5$.

Úttak

Fyrir hvert prófunartilvik, ef slíkt tré með $n$ hnútum er til, prentaðu „YES“ (óháð há- og lágstöfum), fylgt eftir af $n - 1$ línum með tveimur heiltölum hver sem tákna endapunkta hvers leggs. Annars skaltu prenta „NO“ (óháð há- og lágstöfum).

Dæmi

Inntak

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

Úttak

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

Athugasemd

Í fyrsta prófunartilvikinu erum við beðin um að smíða tré með $n = 1$ hnúti, $m = 5$, og fylki gráðuafganga $b = [0]$. Með aðeins einum hnúti geta engir leggir verið til staðar, svo það er nákvæmlega eitt mögulegt tré: einn stakur hnútur af gráðu $0$. Þar sem $0 \bmod 5 = 0$, uppfyllir það skilyrðið; því er svarið „YES“.

Í öðru prófunartilvikinu þurfum við tré á $n = 2$ hnútum með $m = 3$ og afganga $b = [1, 1]$, sem þýðir að báðar gráðurnar verða að vera samleifa $1$ modulo $3$. Á tveimur hnútum er aðeins eitt tré: staki leggurinn $1-2$. Gráður hans eru $(1, 1)$ og vissulega er $1 \bmod 3 = 1$, svo svarið er „YES“, og að prenta „1 2“ er gilt.

Í þriðja prófunartilvikinu þurfum við $n = 5$, $m = 4$, með afganga $b = [0, 1, 1, 1, 1]$: fyrsti hnúturinn verður að hafa gráðu sem er deilanleg með $4$, en hinir fjórir hnútarnir verða að uppfylla $\text{degree} \equiv 1 \pmod 4$. Náttúruleg smíði er stjarna með miðju í hnúti $1$: tengjum $1$ við alla aðra hnúta. Þá er $\deg(1) = 4$ og $4 \bmod 4 = 0$, en hver af $2, 3, 4, 5$ hefur gráðu $1$ og $1 \bmod 4 = 1$. Því er svarið „YES“, og leggirnir „1 2“, „1 3“, „1 4“, „1 5“ virka.

Í fjórða prófunartilvikinu þurfum við tré með $n = 6$, $m = 2$, afganga $b = [1, 0, 0, 0, 0, 1]$, þ.e. endapunktarnir verða að hafa oddatölugráðu og miðhnútarnir fjórir verða að hafa slétta gráðu. Modulo $2$ er þetta eingöngu jafnstæðisskilyrði. Einfaldi vegurinn $1-2-3-4-5-6$ passar fullkomlega: hnútar $1$ og $6$ hafa gráðu $1$ (oddatala), og hnútar $2, 3, 4, 5$ hafa gráðu $2$ (slétt tala). Því er svarið „YES“, og leggir vegarins eru réttir.

Í fimmta prófunartilvikinu erum við beðin um að smíða net (og þar með sér í lagi tré) á $n = 3$ með $m = 2$ og $b = [1, 1, 1]$, svo hver hnútur verður að hafa oddatölugráðu. Þetta er ómögulegt: í sérhverju óstefndu neti er fjöldi hnúta með oddatölugráðu alltaf slétt tala, svo þrjár oddatölugráður geta ekki komið fyrir í neinu mengi leggja. Því er niðurstaðan „NO“.

Í sjötta prófunartilvikinu höfum við $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$. Þar sem $m > n - 1 = 3$, er afgangurinn modulo $10$ jafn gráðunni sjálfri, svo við krefjumst nákvæmlega $\deg = [3, 3, 1, 1]$. Það neyðir tvo hnúta til að vera aðlægir öllum öðrum (gráða $3$ í $4$-hnúta neti), og þegar $n > 2$, myndar sérhvert slíkt par óhjákvæmilega rás ásamt hvaða þriðja hnúti sem er. Tré getur ekki innihaldið rásir, svo niðurstaðan er einnig „NO“.