Se te dan enteros $N, K$ y una secuencia de enteros $X = (X_0, X_1, \dots, X_{N-1})$ de longitud $N$.
Una terna de enteros $(M, A, B)$ se llama una buena terna si satisface todas las condiciones siguientes:
- $1 \le M < 2^{30}$
- Para todo $k = 0, 1, \dots, N-1$, se cumple $X_k = \lfloor \frac{Ak + B}{M} \rfloor$.
Se puede demostrar que, bajo las restricciones dadas, el número de buenas ternas es finito. Sea $C$ este número.
Determina si se cumple $K \le C$. Si se cumple, encuentra la $K$-ésima buena terna más pequeña en orden lexicográfico.
Se te dan $T$ casos de prueba. Resuelve cada caso de prueba de forma independiente.
Entrada
La entrada se proporciona en el siguiente formato:
T case1 case2 : caseT
Cada caso de prueba $\text{case}_i$ se proporciona en el siguiente formato:
N K X0 X1 ... XN-1
Restricciones
- Todos los valores de entrada son enteros.
- $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}$
- La suma de $N$ en todos los casos de prueba no supera $2 \times 10^5$.
Salida
Imprime $T$ líneas.
En la $i$-ésima línea, si se cumple $K \le C$ para el $i$-ésimo caso de prueba, imprime la $K$-ésima buena terna más pequeña en orden lexicográfico imprimiendo $M, A, B$ en este orden separados por espacios. De lo contrario, imprime -1.
Ejemplo
Entrada 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
Salida 1
2 1 1 -1 11 -19 107
Nota
En el primer ejemplo, las buenas ternas en orden lexicográfico son $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.
En el segundo ejemplo, no existe ninguna buena terna.
En el tercer ejemplo, las buenas ternas en orden lexicográfico son $(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$.