דוריאן העניק למר נז'מאה כלי נגינה מורכב מאוד. הכלי יכול לנגן $m$ תווים שונים הממוספרים מ-$0$ עד $m - 1$. למרבה העניין, הוא יכול לנגן מנגינה בת $n$ תווים $s_0, \dots, s_{n-1}$ רק כאשר $n$ הוא ראשוני ומתקיים התנאי הבא:

• הסדרה עולה ממש, כלומר $s_i < s_{i+1}$ עבור כל $0 \le i < n - 1$,
• קיימים $a, b, c$ ו-$d$ כך שמתקיים $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ עבור כל $0 \le i < n$, כאשר $0 \le a < n$, $1 \le b < n$ וכן $0 \le c < m$, $1 \le d < m$.

שימו לב שערכי $a, b, c$ ו-$d$ כאלה מגדירים באופן יחיד את הסדרה הנתונה. נז'מאה מלחין כעת מנגינה חדשה, והוא כבר מילא חלק מהמיקומים בתווים. עזרו לו לסיים את המנגינה! מספיק להדפיס ערכי $a, b, c$ ו-$d$ כלשהם המגדירים סדרה תקפה שמתאימה במיקומים שנז'מאה כבר קבע. מובטח שקיים פתרון.

קלט

השורה הראשונה מכילה מספר שלם יחיד $t$ ($1 \le t \le 2 \cdot 10^4$), מספר מקרי הבדיקה.

השורה הראשונה של כל מקרה בדיקה מכילה $2$ מספרים שלמים $n$ ו-$m$ ($3 \le n \le 3 \cdot 10^5$, $n$ ראשוני, $n \le m \le 10^9$).

השורה השנייה של כל מקרה בדיקה מכילה את המערך המתקבל ($-1 \le u_i < m$, כאשר $u_i = -1$ אם נז'מאה טרם החליט איזה תו יש לנגן במיקום זה).

מובטח כי סכום ערכי ה-$n$ על פני כל מקרי הבדיקה אינו עולה על $3 \cdot 10^5$.

פלט

עבור כל מקרה בדיקה, הדפיסו שורה $1$ עם $4$ מספרים שלמים: הערכים הנדרשים של $a$, $b$, $c$ ו-$d$. אם קיימות מספר תשובות אפשריות, הדפיסו כל אחת מהן.

דוגמה

קלט 1

8
7 12
0 2 4 5 7 9 11
5 19
-1 4 -1 12 -1
3 7
1 4 -1
7 35
2 -1 12 -1 -1 27 -1
5 14
0 -1 11 -1 -1
3 6
-1 -1 2
3 16
-1 -1 -1
5 14
-1 1 -1 9 -1

פלט 1

3 4 5 7
2 2 7 8
2 1 5 3
0 1 2 5
1 4 1 13
0 1 0 1
0 1 0 1
1 3 1 9