Gefnar eru heiltölurnar $N, K$ og heiltalnarruna $X = (X_0, X_1, \dots, X_{N-1})$ af lengd $N$.
Heiltalnaþrennd $(M, A, B)$ kallast góð þrennd ef hún uppfyllir öll eftirfarandi skilyrði:
- $1 \le M < 2^{30}$
- Fyrir öll $k = 0, 1, \dots, N-1$ gildir $X_k = \lfloor \frac{Ak + B}{M} \rfloor$.
Sanna má að miðað við gefnar skorður er fjöldi góðra þrennda endanlegur. Látum þennan fjölda vera $C$.
Ákvarðið hvort $K \le C$ gildi. Ef svo er, finnið $K$-tu minnstu góðu þrenndina í stafrófsröð (lexíkógrafískri röð).
Gefin eru $T$ prófunartilvik. Leysið hvert prófunartilvik sjálfstætt.
Inntak
Inntakið er gefið á eftirfarandi sniði:
T case1 case2 : caseT
Hvert prófunartilvik $\text{case}_i$ er gefið á eftirfarandi sniði:
N K X0 X1 ... XN-1
Skorður
- Öll inntaksgildi eru heiltölur.
- $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}$
- Summa $N$ yfir öll prófunartilvik fer ekki yfir $2 \times 10^5$.
Úttak
Prentið $T$ línur.
Fyrir $i$-tu línuna, ef $K \le C$ gildir fyrir $i$-ta prófunartilvikið, prentið $K$-tu minnstu góðu þrenndina í lexíkógrafískri röð með því að prenta $M, A, B$ í þessari röð aðskilin með bilum. Annars skal prenta -1.
Dæmi
Inntak 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
Úttak 1
2 1 1 -1 11 -19 107
Athugasemd
Í fyrsta dæminu eru góðu þrenndirnar í lexíkógrafískri röð $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.
Í öðru dæminu er engin góð þrennd til.
Í þriðja dæminu eru góðu þrenndirnar í lexíkógrafískri röð $(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$.