整数 $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$ の次数に制限はありません。

入力

入力の 1 行目には、テストケースの個数を表す整数 $t$ が与えられます（$1 \le t \le 5 \cdot 10^5$）。各テストケースについて：

1 行目には、木の頂点数と法を表す 2 つの整数 $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$ 行に各辺の両端点を表す 2 つの整数を出力してください。存在しない場合は「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

注記

1 番目のテストケースでは、$n = 1$ 頂点、$m = 5$、次数の余りの配列 $b = [0]$ である木を作る必要があります。頂点が 1 つしかないため辺は存在せず、可能な木は次数 $0$ の単一頂点のみです。$0 \bmod 5 = 0$ なので条件を満たしており、答えは「YES」です。

2 番目のテストケースでは、$n = 2$ 頂点、$m = 3$、余り $b = [1, 1]$ の木が必要です。つまり、両方の次数が $3$ を法として $1$ と合同でなければなりません。2 頂点上の木は単一の辺 $1-2$ のみです。その次数は $(1, 1)$ であり、実際に $1 \bmod 3 = 1$ なので答えは「YES」であり、「1 2」を出力すれば正解となります。

3 番目のテストケースでは、$n = 5$、$m = 4$、余り $b = [0, 1, 1, 1, 1]$ が必要です。最初の頂点の次数は $4$ で割り切れなければならず、残りの 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」が条件を満たします。

4 番目のテストケースでは、$n = 6$、$m = 2$、余り $b = [1, 0, 0, 0, 0, 1]$ の木が必要です。すなわち、両端の頂点の次数は奇数であり、中間の 4 つの頂点の次数は偶数でなければなりません。$2$ を法とすると、これは純粋な偶奇の制約です。単純パス $1-2-3-4-5-6$ がこれにぴったり合致します。頂点 $1$ と $6$ の次数は $1$（奇数）であり、頂点 $2, 3, 4, 5$ の次数は $2$（偶数）です。よって答えは「YES」であり、このパスの辺を出力すれば正解です。

5 番目のテストケースでは、$n = 3$、$m = 2$、$b = [1, 1, 1]$ でグラフ（特に木）を作る必要があります。つまり、すべての頂点の次数が奇数でなければなりません。これは不可能です。任意の無向グラフにおいて次数が奇数の頂点の個数は常に偶数であるため、どのような辺集合に対しても 3 つの頂点の次数が奇数になることはありません。したがって判定は「NO」となります。

6 番目のテストケースでは、$n = 4$、$m = 10$、$b = [3, 3, 1, 1]$ です。$m > n - 1 = 3$ であるため、$10$ を法とする余りは次数そのものに等しく、厳密に $\deg = [3, 3, 1, 1]$ が要求されます。これは 2 つの頂点が他のすべての頂点と隣接すること（$4$ 頂点グラフにおいて次数 $3$）を強制し、$n > 2$ のとき、そのような頂点の組は任意の 3 つ目の頂点とともに必ず閉路を形成します。木は閉路を含むことができないため、判定は同様に「NO」となります。