Дано цілі числа $n, m > 0$, а також цілі числа $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$. Побудуйте дерево $T$ з $n$ вершинами $V = \{v_1, v_2, \dots, v_n\}$, що задовольняє таку умову: для кожної вершини $v_i$, де $a_i \ne -1$, остача від ділення степеня $\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]$, що означає, що обидва степені мають бути конгруентними $1$ за модулем $3$. На двох вершинах існує лише одне дерево: єдине ребро $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]$. Це змушує дві вершини бути суміжними з усіма іншими (степінь $3$ у графі з $4$ вершинами), а при $n > 2$ будь-яка така пара неминуче утворює цикл разом із будь-якою третьою вершиною. Дерево не може містити циклів, тому вердикт також «NO».