Ti vengono dati gli interi $N, K$ e una sequenza di interi $X = (X_0, X_1, \dots, X_{N-1})$ di lunghezza $N$.
Una terna di interi $(M, A, B)$ è chiamata buona terna se soddisfa tutte le seguenti condizioni:
- $1 \le M < 2^{30}$
- Per tutti i $k = 0, 1, \dots, N-1$, vale $X_k = \lfloor \frac{Ak + B}{M} \rfloor$.
Si può dimostrare che, sotto i vincoli dati, il numero di buone terne è finito. Sia $C$ questo numero.
Determina se vale $K \le C$. In caso affermativo, trova la $K$-esima buona terna più piccola in ordine lessicografico.
Ti vengono dati $T$ casi di test. Risolvi ciascun caso di test indipendentemente.
Input
L'input è fornito nel seguente formato:
T case1 case2 : caseT
Ogni caso di test $\text{case}_i$ è fornito nel seguente formato:
N K X0 X1 ... XN-1
Vincoli
- Tutti i valori in input sono interi.
- $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}$
- La somma di $N$ su tutti i casi di test non supera $2 \times 10^5$.
Output
Stampa $T$ righe.
Per la $i$-esima riga, se vale $K \le C$ per il $i$-esimo caso di test, stampa la $K$-esima buona terna più piccola in ordine lessicografico stampando $M, A, B$ in questo ordine separati da spazi. Altrimenti, stampa -1.
Esempio
Input 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
Output 1
2 1 1 -1 11 -19 107
Note
Nel primo esempio, le buone terne in ordine lessicografico sono $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.
Nel secondo esempio, non esiste alcuna buona terna.
Nel terzo esempio, le buone terne in ordine lessicografico sono $(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$.