נתונים לך מספרים שלמים $N, K$ וסדרת מספרים שלמים $X = (X_0, X_1, \dots, X_{N-1})$ באורך $N$.
שלשה של מספרים שלמים $(M, A, B)$ נקראת שלשה טובה אם היא מקיימת את כל התנאים הבאים:
- $1 \le M < 2^{30}$
- לכל $k = 0, 1, \dots, N-1$, מתקיים $X_k = \lfloor \frac{Ak + B}{M} \rfloor$.
ניתן להוכיח כי תחת האילוצים הנתונים, מספר השלשות הטובות הוא סופי. נסמן מספר זה ב-$C$.
קבע האם מתקיים $K \le C$. אם כן, מצא את השלשה הטובה ה-$K$ בגודלה (מהקטן לגדול) לפי סדר לקסיקוגרפי.
נתונים לך $T$ מקרי בדיקה. פתור כל מקרה בדיקה בנפרד.
קלט
הקלט ניתן בפורמט הבא:
T case1 case2 : caseT
כל מקרה בדיקה $\text{case}_i$ ניתן בפורמט הבא:
N K X0 X1 ... XN-1
אילוצים
- כל ערכי הקלט הם מספרים שלמים.
- $1 \le T \le 1000$
- $2 \le N \le 2 \times 10^5$
- $1 \le K \le 10^9$
- $0 \le X_i < 2^{30}$
- סכום ערכי $N$ על פני כל מקרי הבדיקה אינו עולה על $2 \times 10^5$.
פלט
הדפס $T$ שורות.
עבור השורה ה-$i$, אם מתקיים $K \le C$ עבור מקרה הבדיקה ה-$i$, הדפס את השלשה הטובה ה-$K$ בקוטנה לפי סדר לקסיקוגרפי על ידי הדפסת $M, A, B$ בסדר זה מופרדים ברווחים. אחרת, הדפס -1.
דוגמה
קלט 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
פלט 1
2 1 1 -1 11 -19 107
הערה
בדוגמה הראשונה, השלשות הטובות לפי סדר לקסיקוגרפי הן $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.
בדוגמה השנייה, לא קיימת שלשה טובה.
בדוגמה השלישית, השלשות הטובות לפי סדר לקסיקוגרפי הן $(M, A, B) = (4, -7, 39), (7, -12, 68), (8, -14, 78), (8, -14, 79), (9, -16, 89), (10, -17, 97), (11, -19, 107), \dots$.