Сізге $N, K$ бүтін сандары және ұзындығы $N$ болатын $X = (X_0, X_1, \dots, X_{N-1})$ бүтін сандар тізбегі берілген.
Бүтін сандар үштігі $(M, A, B)$ келесі шарттардың барлығын қанағаттандырса, жақсы үштік деп аталады:
- $1 \le M < 2^{30}$
- Барлық $k = 0, 1, \dots, N-1$ үшін $X_k = \lfloor \frac{Ak + B}{M} \rfloor$ орындалады.
Берілген шектеулерде жақсы үштіктердің саны шекті екенін дәлелдеуге болады. Бұл санды $C$ деп белгілейік.
$K \le C$ теңсіздігі орындалатынын анықтаңыз. Егер орындалса, лексикографиялық ретпен $K$-шы ең кіші жақсы үштікті табыңыз.
Сізге $T$ тест жиыны берілген. Әр тест жиынын тәуелсіз түрде шешіңіз.
Кіріс деректер
Кіріс деректер келесі форматта беріледі:
T case1 case2 : caseT
Әрбір $\text{case}_i$ тест жиыны келесі форматта беріледі:
N K X0 X1 ... XN-1
Шектеулер
- Барлық кіріс мәндері бүтін сандар.
- $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}$
- Барлық тест жиындары бойынша $N$ қосындысы $2 \times 10^5$ аспайды.
Шығыс деректер
$T$ жол шығарыңыз.
$i$-ші жол үшін, егер $i$-ші тест жиынында $K \le C$ орындалса, лексикографиялық ретпен $K$-шы ең кіші жақсы үштікті $M, A, B$ ретімен бос орын арқылы бөліп шығарыңыз. Әйтпесе, -1 шығарыңыз.
Мысал
Кіріс 1
3 4 1 0 1 1 2 3 1 2 0 1 6 7 9 8 6 4 2 1
Шығыс 1
2 1 1 -1 11 -19 107
Ескертпе
Бірінші мысалда лексикографиялық ретпен орналасқан жақсы үштіктер: $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.
Екінші мысалда ешқандай жақсы үштік жоқ.
Үшінші мысалда лексикографиялық ретпен орналасқан жақсы үштіктер: $(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$.