Given are integers $n, m > 0$, as well as integers $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$. Construct a tree $T$ with $n$ vertices $V = \{v_1, v_2, \dots, v_n\}$ with the following condition: for each vertex $v_i$ where $a_i \ne -1$, the remainder of the degree $\deg_T(v_i)$ when divided by $m$ must equal $a_i$. If $a_i = -1$, then there are no restrictions on the degree of $v_i$.

Input

The first line of input contains an integer $t$, the number of test cases ($1 \le t \le 5 \cdot 10^5$). For each test case:

The first line contains two integers, $n$ and $m$, denoting the number of vertices in the tree and the modulus ($1 \le n \le 5 \cdot 10^5$; $1 \le m \le 2 \cdot 10^9$).

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ denoting the required remainders ($-1 \le a_i < m$).

The sum of $n$ across all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, if such a tree with $n$ vertices exists, output "YES" (in any case), followed by $n - 1$ lines with two integers each denoting the endpoints of each edge. Otherwise, output "NO" (in any case).

Example

Input

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

Output

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

Note

In the first test case, we are asked to build a tree with $n = 1$ vertex, $m = 5$, and degree residue array $b = [0]$. With only one vertex, there can be no edges, so there is exactly one possible tree: a single vertex of degree $0$. Since $0 \bmod 5 = 0$, it satisfies the requirement; hence the answer is "YES".

In the second test case, we need a tree on $n = 2$ vertices with $m = 3$ and residues $b = [1, 1]$, meaning both degrees must be congruent to $1$ modulo $3$. On two vertices, there is only one tree: the single edge $1-2$. Its degrees are $(1, 1)$ and indeed $1 \bmod 3 = 1$, so the answer is "YES", and printing "1 2" is valid.

In the third test case, we need $n = 5$, $m = 4$, with residues $b = [0, 1, 1, 1, 1]$: the first vertex must have degree divisible by $4$, while the other four vertices must have $\text{degree} \equiv 1 \pmod 4$. A natural construction is a star centered at vertex $1$: connect $1$ to every other vertex. Then $\deg(1) = 4$ and $4 \bmod 4 = 0$, while each of $2, 3, 4, 5$ has degree $1$ and $1 \bmod 4 = 1$. Therefore, the answer is "YES", and edges "1 2", "1 3", "1 4", "1 5" work.

In the fourth test case, we need a tree with $n = 6$, $m = 2$, residues $b = [1, 0, 0, 0, 0, 1]$, i.e. the endpoints must have odd degree and the four middle vertices must have even degree. Modulo $2$, this is purely a parity constraint. The simple path $1-2-3-4-5-6$ fits perfectly: vertices $1$ and $6$ have degree $1$ (odd), and vertices $2, 3, 4, 5$ have degree $2$ (even). Hence the answer is "YES", and the path edges are correct.

In the fifth test case, we are asked to build a graph (and thus, in particular, a tree) on $n = 3$ with $m = 2$ and $b = [1, 1, 1]$, so every vertex must have odd degree. This is impossible: in every undirected graph, the number of odd-degree vertices is always even, so having three odd degrees cannot happen for any set of edges. Therefore, the verdict is "NO".

In the sixth test case, we have $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$. Since $m > n - 1 = 3$, the residue modulo $10$ equals the degree itself, so we require exactly $\deg = [3, 3, 1, 1]$. That forces two vertices to be adjacent to all others (degree $3$ in a $4$-vertex graph), and when $n > 2$, any such pair necessarily forms a cycle together with any third vertex. A tree cannot contain cycles, so the verdict is also "NO".