Du får heltalen $N, K$ och en heltalsföljd $X = (X_0, X_1, \dots, X_{N-1})$ av längd $N$.
En heltalstrippel $(M, A, B)$ kallas en bra trippel om den uppfyller alla följande villkor:
- $1 \le M < 2^{30}$
- För alla $k = 0, 1, \dots, N-1$ gäller $X_k = \lfloor \frac{Ak + B}{M} \rfloor$.
Det kan bevisas att antalet bra tripplar är ändligt under de givna begränsningarna. Låt detta antal vara $C$.
Avgör om $K \le C$ gäller. Om så är fallet, hitta den $K$-te minsta bra trippeln i lexikografisk ordning.
Du får $T$ testfall. Lös varje testfall oberoende.
Indata
Indata ges i följande format:
T case1 case2 : caseT
Varje testfall $\text{case}_i$ ges i följande format:
N K X0 X1 ... XN-1
Begränsningar
- Alla indatavärden är heltal.
- $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}$
- Summan av $N$ över alla testfall överstiger inte $2 \times 10^5$.
Utdata
Skriv ut $T$ rader.
För den $i$-te raden, om $K \le C$ gäller för det $i$-te testfallet, skriv ut den $K$-te minsta bra trippeln i lexikografisk ordning genom att skriva ut $M, A, B$ i denna ordning separerade med mellanslag. Annars, skriv ut -1.
Exempel
Indata 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
Anmärkning
I det första exemplet är de bra tripplarna i lexikografisk ordning $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.
I det andra exemplet finns ingen bra trippel.
I det tredje exemplet är de bra tripplarna i lexikografisk ordning $(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$.