Даны целые числа $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».