Dane są liczby całkowite $N, K$ oraz ciąg liczb całkowitych $X = (X_0, X_1, \dots, X_{N-1})$ o długości $N$.
Trójkę liczb całkowitych $(M, A, B)$ nazywamy dobrą trójką, jeśli spełnia wszystkie poniższe warunki:
- $1 \le M < 2^{30}$
- Dla wszystkich $k = 0, 1, \dots, N-1$ zachodzi $X_k = \lfloor \frac{Ak + B}{M} \rfloor$.
Można udowodnić, że przy podanych ograniczeniach liczba dobrych trójek jest skończona. Niech liczba ta wynosi $C$.
Rozstrzygnij, czy zachodzi $K \le C$. Jeśli tak, znajdź $K$-tą najmniejszą dobrą trójkę w porządku leksykograficznym.
Danych jest $T$ przypadków testowych. Rozwiąż każdy przypadek testowy niezależnie.
Wejście
Wejście jest podane w następującym formacie:
T case1 case2 : caseT
Każdy przypadek testowy $\text{case}_i$ jest podany w następującym formacie:
N K X0 X1 ... XN-1
Ograniczenia
- Wszystkie wartości wejściowe są liczbami całkowitymi.
- $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}$
- Suma wartości $N$ po wszystkich przypadkach testowych nie przekracza $2 \times 10^5$.
Wyjście
Wypisz $T$ wierszy.
W $i$-tym wierszu, jeśli dla $i$-tego przypadku testowego zachodzi $K \le C$, wypisz $K$-tą najmniejszą dobrą trójkę w porządku leksykograficznym, wypisując $M, A, B$ w tej kolejności, oddzielone spacjami. W przeciwnym razie wypisz -1.
Przykład
Wejście 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
Wyjście 1
2 1 1 -1 11 -19 107
Uwaga
W pierwszym przykładzie dobrymi trójkami w porządku leksykograficznym są $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.
W drugim przykładzie nie istnieje żadna dobra trójka.
W trzecim przykładzie dobrymi trójkami w porządku leksykograficznym są $(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$.