Du får gitt heltallene $N, K$ og en heltallsfølge $X = (X_0, X_1, \dots, X_{N-1})$ med lengde $N$.
En heltallstrippel $(M, A, B)$ kalles en god trippel hvis den oppfyller alle følgende betingelser:
- $1 \le M < 2^{30}$
- For alle $k = 0, 1, \dots, N-1$ gjelder $X_k = \lfloor \frac{Ak + B}{M} \rfloor$.
Det kan bevises at antallet gode tripler er endelig under de gitte begrensningene. La dette antallet være $C$.
Avgjør om $K \le C$ gjelder. Hvis det gjør det, finn den $K$-te minste gode trippelen i leksikografisk rekkefølge.
Du får gitt $T$ testtilfeller. Løs hvert testtilfelle uavhengig.
Inndata
Inndataene gis på følgende format:
T case1 case2 : caseT
Hvert testtilfelle $\text{case}_i$ gis på følgende format:
N K X0 X1 ... XN-1
Begrensninger
- Alle inndataverdier er heltall.
- $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}$
- Summen av $N$ over alle testtilfeller overstiger ikke $2 \times 10^5$.
Utdata
Skriv ut $T$ linjer.
For den $i$-te linjen, hvis $K \le C$ gjelder for det $i$-te testtilfellet, skriv ut den $K$-te minste gode trippelen i leksikografisk rekkefølge ved å skrive ut $M, A, B$ i denne rekkefølgen adskilt med mellomrom. Ellers, skriv ut -1.
Eksempel
Inndata 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
Utdata 1
2 1 1 -1 11 -19 107
Merk
I det første eksempelet er de gode triplene i leksikografisk rekkefølge $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.
I det andre eksempelet finnes det ingen god trippel.
I det tredje eksempelet er de gode triplene i leksikografisk rekkefølge $(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$.