$n, m > 0$ бүтін сандары, сондай-ақ $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$ бүтін сандары берілген. Келесі шартты қанағаттандыратын $n$ төбесі $V = \{v_1, v_2, \dots, v_n\}$ бар $T$ ағашын құрастырыңыз: $a_i \ne -1$ болатын әрбір $v_i$ төбесі үшін $\deg_T(v_i)$ дәрежесін $m$-ге бөлгендегі қалдық $a_i$-ге тең болуы тиіс. Егер $a_i = -1$ болса, онда $v_i$ төбесінің дәрежесіне ешқандай шектеу қойылмайды.

Кіріс деректер

Кіріс деректердің бірінші жолында тесттер санын білдіретін бүтін сан $t$ берілген ($1 \le t \le 5 \cdot 10^5$). Әрбір тест үшін:

Бірінші жолда ағаштағы төбелер саны мен модульді білдіретін екі бүтін сан $n$ және $m$ берілген ($1 \le n \le 5 \cdot 10^5$; $1 \le m \le 2 \cdot 10^9$).

Келесі жолда талап етілетін қалдықтарды білдіретін $n$ бүтін сан $a_1, a_2, \dots, a_n$ берілген ($-1 \le a_i < m$).

Барлық тесттер бойынша $n$ қосындысы $5 \cdot 10^5$-нен аспайды.

Шығыс деректер

Әрбір тест үшін, егер осындай $n$ төбесі бар ағаш табылса, «YES» (кез келген регистрде) деп шығарып, одан кейін әрбір қырдың ұштарын білдіретін екі бүтін саннан тұратын $n - 1$ жолды шығарыңыз. Әйтпесе, «NO» (кез келген регистрде) деп шығарыңыз.

Мысал

Кіріс деректер

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

Шығыс деректер

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

Ескертпе

Бірінші тестте бізден $n = 1$ төбесі бар, $m = 5$ және дәреже қалдықтарының жиымы $b = [0]$ болатын ағаш құрастыру сұралады. Тек бір төбе болғандықтан, қырлар болуы мүмкін емес, сондықтан тек бір ғана ағаш болуы мүмкін: дәрежесі $0$-ге тең жалғыз төбе. $0 \bmod 5 = 0$ болғандықтан, ол талапты қанағаттандырады; демек, жауап — «YES».

Екінші тестте бізге $n = 2$ төбесі бар, $m = 3$ және қалдықтары $b = [1, 1]$ болатын ағаш қажет, яғни екі дәреже де $3$ модулі бойынша $1$-ге конгруэнтті болуы керек. Екі төбеде тек бір ғана ағаш бар: жалғыз $1-2$ қыры. Оның дәрежелері $(1, 1)$ және шынымен де $1 \bmod 3 = 1$, сондықтан жауап — «YES», ал «1 2» деп шығару дұрыс.

Үшінші тестте бізге $n = 5$, $m = 4$, қалдықтары $b = [0, 1, 1, 1, 1]$ қажет: бірінші төбенің дәрежесі $4$-ке бөлінуі керек, ал қалған төрт төбе үшін $\text{degree} \equiv 1 \pmod 4$ орындалуы тиіс. Табиғи құрылым — центрі $1$ төбесінде орналасқан жұлдызша: $1$-ді барлық басқа төбелермен қосамыз. Сонда $\deg(1) = 4$ және $4 \bmod 4 = 0$, ал $2, 3, 4, 5$ төбелерінің әрқайсысының дәрежесі $1$ және $1 \bmod 4 = 1$. Демек, жауап — «YES», ал «1 2», «1 3», «1 4», «1 5» қырлары жарайды.

Төртінші тестте бізге $n = 6$, $m = 2$, қалдықтары $b = [1, 0, 0, 0, 0, 1]$ болатын ағаш қажет, яғни шеткі төбелердің дәрежесі тақ, ал ортадағы төрт төбенің дәрежесі жұп болуы керек. $2$ модулі бойынша бұл таза жұптылық шарты. $1-2-3-4-5-6$ қарапайым жолы өте жақсы сәйкес келеді: $1$ және $6$ төбелерінің дәрежесі $1$ (тақ), ал $2, 3, 4, 5$ төбелерінің дәрежесі $2$ (жұп). Сондықтан жауап — «YES», және жол қырлары дұрыс.

Бесінші тестте бізден $n = 3$, $m = 2$ және $b = [1, 1, 1]$ болғанда граф (соның ішінде ағаш) құрастыру сұралады, яғни әрбір төбенің дәрежесі тақ болуы тиіс. Бұл мүмкін емес: кез келген бағытталмаған графта тақ дәрежелі төбелердің саны әрқашан жұп болады, сондықтан ешбір қырлар жиыны үшін үш тақ дәреже болуы мүмкін емес. Демек, шешім — «NO».

Алтыншы тестте бізде $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$. $m > n - 1 = 3$ болғандықтан, $10$ модулі бойынша қалдық дәреженің өзіне тең, сондықтан бізге дәл $\deg = [3, 3, 1, 1]$ қажет. Бұл екі төбенің барлық басқа төбелермен көршілес болуын мәжбүрлейді ($4$ төбелі графтағы $3$ дәреже), ал $n > 2$ болғанда мұндай кез келген жұп кез келген үшінші төбемен бірге міндетті түрде цикл құрайды. Ағашта циклдер болмайды, сондықтан шешім де — «NO».