Gegeben sind ganze Zahlen $N, K$ und eine ganzzahlige Folge $X = (X_0, X_1, \dots, X_{N-1})$ der Länge $N$.
Ein ganzzahliges Tripel $(M, A, B)$ wird gutes Tripel genannt, wenn es alle folgenden Bedingungen erfüllt:
- $1 \le M < 2^{30}$
- Für alle $k = 0, 1, \dots, N-1$ gilt $X_k = \lfloor \frac{Ak + B}{M} \rfloor$.
Es lässt sich beweisen, dass unter den gegebenen Bedingungen die Anzahl der guten Tripel endlich ist. Sei diese Anzahl $C$.
Bestimme, ob $K \le C$ gilt. Falls ja, finde das lexikographisch $K$-kleinste gute Tripel.
Dir werden $T$ Testfälle gegeben. Löse jeden Testfall unabhängig.
Eingabe
Die Eingabe erfolgt im folgenden Format:
T case1 case2 : caseT
Jeder Testfall $\text{case}_i$ wird im folgenden Format angegeben:
N K X0 X1 ... XN-1
Bedingungen
- Alle Eingabewerte sind ganze Zahlen.
- $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}$
- Die Summe von $N$ über alle Testfälle hinweg überschreitet nicht $2 \times 10^5$.
Ausgabe
Gib $T$ Zeilen aus.
Falls für den $i$-ten Testfall $K \le C$ gilt, gib in der $i$-ten Zeile das lexikographisch $K$-kleinste gute Tripel aus, indem du $M, A, B$ in dieser Reihenfolge durch Leerzeichen getrennt ausgibst. Andernfalls gib -1 aus.
Beispiel
Eingabe 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
Ausgabe 1
2 1 1 -1 11 -19 107
Hinweis
Im ersten Beispiel lauten die guten Tripel in lexikographischer Reihenfolge $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.
Im zweiten Beispiel existiert kein gutes Tripel.
Im dritten Beispiel lauten die guten Tripel in lexikographischer Reihenfolge $(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$.