Вам даны целые числа $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$.