Вам дано цілі числа $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$-му рядку, якщо для $i$-го набору тестових даних виконується $K \le C$, виведіть $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$.