정수 $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$입니다.