Givet är heltal $n, m > 0$, samt heltal $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$. Konstruera ett träd $T$ med $n$ hörn $V = \{v_1, v_2, \dots, v_n\}$ med följande villkor: för varje hörn $v_i$ där $a_i \ne -1$ måste resten då graden $\deg_T(v_i)$ divideras med $m$ vara lika med $a_i$. Om $a_i = -1$ finns det inga begränsningar på graden för $v_i$.

Indata

Den första raden i indatan innehåller ett heltal $t$, antalet testfall ($1 \le t \le 5 \cdot 10^5$). För varje testfall:

Den första raden innehåller två heltal, $n$ och $m$, som anger antalet hörn i trädet och modulen ($1 \le n \le 5 \cdot 10^5$; $1 \le m \le 2 \cdot 10^9$).

Nästa rad innehåller $n$ heltal $a_1, a_2, \dots, a_n$ som anger de begärda resterna ($-1 \le a_i < m$).

Summan av $n$ över alla testfall överstiger inte $5 \cdot 10^5$.

Utdata

För varje testfall, om ett sådant träd med $n$ hörn existerar, skriv ut "YES" (skiftlägesokänsligt), följt av $n - 1$ rader med två heltal vardera som anger ändpunkterna för varje kant. Annars, skriv ut "NO" (skiftlägesokänsligt).

Exempel

Indata

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

Utdata

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

Anmärkning

I det första testfallet ombeds vi bygga ett träd med $n = 1$ hörn, $m = 5$, och gradrestfältet $b = [0]$. Med bara ett hörn kan det inte finnas några kanter, så det finns exakt ett möjligt träd: ett enda hörn av grad $0$. Eftersom $0 \bmod 5 = 0$ uppfyller det kravet; alltså är svaret "YES".

I det andra testfallet behöver vi ett träd på $n = 2$ hörn med $m = 3$ och resterna $b = [1, 1]$, vilket innebär att båda graderna måste vara kongruenta med $1$ modulo $3$. På två hörn finns det bara ett träd: den enda kanten $1-2$. Dess grader är $(1, 1)$ och mycket riktigt är $1 \bmod 3 = 1$, så svaret är "YES", och att skriva ut "1 2" är giltigt.

I det tredje testfallet behöver vi $n = 5$, $m = 4$, med resterna $b = [0, 1, 1, 1, 1]$: det första hörnet måste ha en grad som är delbar med $4$, medan de andra fyra hörnen måste ha $\text{degree} \equiv 1 \pmod 4$. En naturlig konstruktion är en stjärna centrerad i hörn $1$: förbind $1$ med varje annat hörn. Då är $\deg(1) = 4$ och $4 \bmod 4 = 0$, medan vart och ett av $2, 3, 4, 5$ har grad $1$ och $1 \bmod 4 = 1$. Därför är svaret "YES", och kanterna "1 2", "1 3", "1 4", "1 5" fungerar.

I det fjärde testfallet behöver vi ett träd med $n = 6$, $m = 2$, resterna $b = [1, 0, 0, 0, 0, 1]$, dvs. ändpunkterna måste ha udda grad och de fyra mittersta hörnen måste ha jämn grad. Modulo $2$ är detta rent ett paritetsvillkor. Den enkla vägen $1-2-3-4-5-6$ passar perfekt: hörnen $1$ och $6$ har grad $1$ (udda), och hörnen $2, 3, 4, 5$ har grad $2$ (jämn). Alltså är svaret "YES", och vägens kanter är korrekta.

I det femte testfallet ombeds vi bygga en graf (och därmed i synnerhet ett träd) på $n = 3$ med $m = 2$ och $b = [1, 1, 1]$, så varje hörn måste ha udda grad. Detta är omöjligt: i varje oriktad graf är antalet hörn med udda grad alltid jämnt, så tre udda grader kan inte förekomma för någon mängd kanter. Därför är svaret "NO".

I det sjätte testfallet har vi $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$. Eftersom $m > n - 1 = 3$ är resten modulo $10$ lika med själva graden, så vi kräver exakt $\deg = [3, 3, 1, 1]$. Det tvingar två hörn att vara grannar med alla andra (grad $3$ i en graf med $4$ hörn), och när $n > 2$ bildar varje sådant par nödvändigtvis en cykel tillsammans med vilket tredje hörn som helst. Ett träd kan inte innehålla cykler, så svaret är också "NO".