أُعطيت عددين صحيحين $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$.