נתונים מספרים שלמים $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".