لديك عددان صحيحان $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".