กำหนดจำนวนเต็ม $N, K$ และลำดับของจำนวนเต็ม $X = (X_0, X_1, \dots, X_{N-1})$ ที่มีความยาว $N$
สามสิ่งอันดับของจำนวนเต็ม $(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$ หาก $K \le C$ เป็นจริงสำหรับชุดข้อมูลทดสอบที่ $i$ ให้แสดงผลสามสิ่งอันดับที่ดีที่มีค่าน้อยที่สุดเป็นอันดับที่ $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$