On vous donne des entiers $N, K$ et une suite d'entiers $X = (X_0, X_1, \dots, X_{N-1})$ de longueur $N$.
Un triplet d'entiers $(M, A, B)$ est appelé un bon triplet s'il satisfait toutes les conditions suivantes :
- $1 \le M < 2^{30}$
- Pour tout $k = 0, 1, \dots, N-1$, $X_k = \lfloor \frac{Ak + B}{M} \rfloor$ est vérifié.
On peut prouver que, sous les contraintes données, le nombre de bons triplets est fini. Soit $C$ ce nombre.
Déterminez si $K \le C$ est vérifié. Si c'est le cas, trouvez le $K$-ième plus petit bon triplet dans l'ordre lexicographique.
On vous donne $T$ cas de test. Résolvez chaque cas de test indépendamment.
Entrée
L'entrée est donnée dans le format suivant :
T case1 case2 : caseT
Chaque cas de test $\text{case}_i$ est donné dans le format suivant :
N K X0 X1 ... XN-1
Contraintes
- Toutes les valeurs d'entrée sont des entiers.
- $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 somme de $N$ sur tous les cas de test ne dépasse pas $2 \times 10^5$.
Sortie
Affichez $T$ lignes.
Pour la $i$-ième ligne, si $K \le C$ est vérifié pour le $i$-ième cas de test, affichez le $K$-ième plus petit bon triplet dans l'ordre lexicographique en affichant $M, A, B$ dans cet ordre séparés par des espaces. Sinon, affichez -1.
Exemple
Entrée 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
Sortie 1
2 1 1 -1 11 -19 107
Note
Dans le premier exemple, les bons triplets dans l'ordre lexicographique sont $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.
Dans le deuxième exemple, il n'existe aucun bon triplet.
Dans le troisième exemple, les bons triplets dans l'ordre lexicographique sont $(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$.