Cho các số nguyên $n, m > 0$, cũng như các số nguyên $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$. Hãy xây dựng một cây $T$ gồm $n$ đỉnh $V = \{v_1, v_2, \dots, v_n\}$ thỏa mãn điều kiện sau: với mỗi đỉnh $v_i$ mà $a_i \ne -1$, số dư của bậc $\deg_T(v_i)$ khi chia cho $m$ phải bằng $a_i$. Nếu $a_i = -1$, thì không có ràng buộc nào đối với bậc của $v_i$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $t$, số lượng bộ dữ liệu ($1 \le t \le 5 \cdot 10^5$). Với mỗi bộ dữ liệu:

Dòng đầu tiên chứa hai số nguyên $n$ và $m$, biểu thị số lượng đỉnh trong cây và số modulo ($1 \le n \le 5 \cdot 10^5$; $1 \le m \le 2 \cdot 10^9$).

Dòng tiếp theo chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ biểu thị các số dư được yêu cầu ($-1 \le a_i < m$).

Tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $5 \cdot 10^5$.

Kết quả

Với mỗi bộ dữ liệu, nếu tồn tại một cây gồm $n$ đỉnh như vậy, hãy in ra "YES" (không phân biệt hoa thường), theo sau là $n - 1$ dòng, mỗi dòng gồm hai số nguyên biểu thị hai đầu mút của mỗi cạnh. Ngược lại, hãy in ra "NO" (không phân biệt hoa thường).

Ví dụ

Dữ liệu vào

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

Kết quả

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

Ghi chú

Ở bộ dữ liệu đầu tiên, chúng ta được yêu cầu xây dựng một cây có $n = 1$ đỉnh, $m = 5$, và mảng số dư bậc $b = [0]$. Chỉ với một đỉnh, không thể có cạnh nào, vì vậy chỉ có đúng một cây khả dĩ: một đỉnh duy nhất có bậc $0$. Vì $0 \bmod 5 = 0$, nó thỏa mãn yêu cầu; do đó câu trả lời là "YES".

Ở bộ dữ liệu thứ hai, chúng ta cần một cây trên $n = 2$ đỉnh với $m = 3$ và các số dư $b = [1, 1]$, nghĩa là cả hai bậc đều phải đồng dư với $1$ theo modulo $3$. Trên hai đỉnh, chỉ có một cây duy nhất: cạnh đơn $1-2$. Các bậc của nó là $(1, 1)$ và thực sự $1 \bmod 3 = 1$, vì vậy câu trả lời là "YES", và việc in ra "1 2" là hợp lệ.

Ở bộ dữ liệu thứ ba, chúng ta cần $n = 5$, $m = 4$, với các số dư $b = [0, 1, 1, 1, 1]$: đỉnh đầu tiên phải có bậc chia hết cho $4$, trong khi bốn đỉnh còn lại phải có $\text{degree} \equiv 1 \pmod 4$. Một cách xây dựng tự nhiên là hình sao có tâm tại đỉnh $1$: nối $1$ với mọi đỉnh khác. Khi đó $\deg(1) = 4$ và $4 \bmod 4 = 0$, trong khi mỗi đỉnh trong $2, 3, 4, 5$ có bậc $1$ và $1 \bmod 4 = 1$. Do đó, câu trả lời là "YES", và các cạnh "1 2", "1 3", "1 4", "1 5" thỏa mãn.

Ở bộ dữ liệu thứ tư, chúng ta cần một cây với $n = 6$, $m = 2$, các số dư $b = [1, 0, 0, 0, 0, 1]$, tức là các đỉnh đầu mút phải có bậc lẻ và bốn đỉnh ở giữa phải có bậc chẵn. Theo modulo $2$, đây thuần túy là một ràng buộc về tính chẵn lẻ. Đường đi đơn $1-2-3-4-5-6$ hoàn toàn phù hợp: đỉnh $1$ và $6$ có bậc $1$ (lẻ), và các đỉnh $2, 3, 4, 5$ có bậc $2$ (chẵn). Do đó câu trả lời là "YES", và các cạnh của đường đi là chính xác.

Ở bộ dữ liệu thứ năm, chúng ta được yêu cầu xây dựng một đồ thị (và do đó, nói riêng là một cây) trên $n = 3$ với $m = 2$ và $b = [1, 1, 1]$, vì vậy mọi đỉnh đều phải có bậc lẻ. Điều này là bất khả thi: trong mọi đồ thị vô hướng, số lượng đỉnh bậc lẻ luôn là số chẵn, nên việc có ba bậc lẻ không thể xảy ra với bất kỳ tập cạnh nào. Do đó, kết luận là "NO".

Ở bộ dữ liệu thứ sáu, chúng ta có $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$. Vì $m > n - 1 = 3$, số dư theo modulo $10$ bằng chính bậc đó, nên chúng ta cần chính xác $\deg = [3, 3, 1, 1]$. Điều đó buộc hai đỉnh phải kề với tất cả các đỉnh khác (bậc $3$ trong đồ thị $4$ đỉnh), và khi $n > 2$, bất kỳ cặp đỉnh nào như vậy nhất thiết phải tạo thành một chu trình cùng với bất kỳ đỉnh thứ ba nào. Một cây không thể chứa chu trình, vì vậy kết luận cũng là "NO".