Sinulle annetaan kokonaisluvut $N, K$ ja pituutta $N$ oleva kokonaislukujono $X = (X_0, X_1, \dots, X_{N-1})$.
Kokonaislukukolmikkoa $(M, A, B)$ kutsutaan hyväksi kolmikoksi, jos se täyttää kaikki seuraavat ehdot:
- $1 \le M < 2^{30}$
- Kaikilla $k = 0, 1, \dots, N-1$ pätee $X_k = \lfloor \frac{Ak + B}{M} \rfloor$.
Voidaan todistaa, että annettujen rajoitusten puitteissa hyvien kolmikoiden lukumäärä on äärellinen. Olkoon tämä lukumäärä $C$.
Määritä, päteekö $K \le C$. Jos pätee, etsi aakkosjärjestyksessä (leksikografisessa järjestyksessä) $K$:nneksi pienin hyvä kolmikko.
Sinulle annetaan $T$ testitapausta. Ratkaise jokainen testitapaus toisistaan riippumatta.
Syöte
Syöte annetaan seuraavassa muodossa:
T case1 case2 : caseT
Jokainen testitapaus $\text{case}_i$ annetaan seuraavassa muodossa:
N K X0 X1 ... XN-1
Rajoitukset
- Kaikki syötteen arvot ovat kokonaislukuja.
- $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}$
- Lukujen $N$ summa yli kaikkien testitapausten ei ylitä $2 \times 10^5$.
Tuloste
Tulosta $T$ riviä.
Jos $i$:nnessä testitapauksessa pätee $K \le C$, tulosta $i$:nnelle riville leksikografisessa järjestyksessä $K$:nneksi pienin hyvä kolmikko tulostamalla $M, A, B$ tässä järjestyksessä välilyönnein eroteltuina. Muussa tapauksessa tulosta -1.
Esimerkki
Syöte 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
Tuloste 1
2 1 1 -1 11 -19 107
Huomautus
Ensimmäisessä esimerkissä hyvät kolmikot leksikografisessa järjestyksessä ovat $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.
Toisessa esimerkissä ei ole yhtään hyvää kolmikkoa.
Kolmannessa esimerkissä hyvät kolmikot leksikografisessa järjestyksessä ovat $(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$.