Dorijan ได้มอบเครื่องดนตรีที่ซับซ้อนมากชิ้นหนึ่งให้แก่คุณ Nežmah เครื่องดนตรีนี้สามารถบรรเลงโน้ตที่แตกต่างกันได้ $m$ ตัว ซึ่งมีหมายเลขตั้งแต่ $0$ ถึง $m - 1$ ที่น่าสนใจคือ มันสามารถบรรเลงทำนองที่มีโน้ต $n$ ตัว $s_0, \dots, s_{n-1}$ ได้เฉพาะเมื่อ $n$ เป็น จำนวนเฉพาะ และเป็นไปตามเงื่อนไขต่อไปนี้:

• ลำดับมีค่าเพิ่มขึ้น กล่าวคือ $s_i < s_{i+1}$ สำหรับทุกๆ $0 \le i < n - 1$,
• มี $a, b, c$ และ $d$ ที่ทำให้ $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ สำหรับทุกๆ $0 \le i < n$ โดยที่ $0 \le a < n$, $1 \le b < n$ และ $0 \le c < m$, $1 \le d < m$

สังเกตว่าค่า $a, b, c$ และ $d$ ดังกล่าวจะกำหนดลำดับที่ให้มาได้อย่างเดียวเท่านั้น ขณะนี้ Nežmah กำลังแต่งทำนองเพลงใหม่ และเขาได้เติมโน้ตลงในบางตำแหน่งไปแล้ว จงช่วยเขาแต่งทำนองเพลงนี้ให้เสร็จ! เพียงแค่แสดงผลค่า $a, b, c$ และ $d$ ชุดใดก็ได้ที่กำหนดลำดับที่ถูกต้องซึ่งตรงกับตำแหน่งที่ Nežmah ได้กำหนดไว้แล้ว รับประกันว่ามีคำตอบเสมอ

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็มเพียงตัวเดียวคือ $t$ ($1 \le t \le 2 \cdot 10^4$) แทนจำนวนชุดทดสอบ

บรรทัดแรกของแต่ละชุดทดสอบประกอบด้วยจำนวนเต็ม $2$ ตัวคือ $n$ และ $m$ ($3 \le n \le 3 \cdot 10^5$, $n$ เป็นจำนวนเฉพาะ, $n \le m \le 10^9$)

บรรทัดที่สองของแต่ละชุดทดสอบประกอบด้วยอาร์เรย์ผลลัพธ์ ($-1 \le u_i < m$ โดยที่ $u_i = -1$ หาก Nežmah ยังไม่ได้ตัดสินใจว่าจะบรรเลงโน้ตตัวใดในตำแหน่งนี้)

รับประกันว่าผลรวมของ $n$ ในทุกชุดทดสอบจะไม่เกิน $3 \cdot 10^5$

ข้อมูลส่งออก

สำหรับแต่ละชุดทดสอบ ให้แสดงผล $1$ บรรทัดที่มีจำนวนเต็ม $4$ ตัว ได้แก่ ค่าที่ต้องการของ $a$, $b$, $c$ และ $d$ หากมีคำตอบที่เป็นไปได้หลายชุด ให้แสดงผลชุดใดก็ได้

ตัวอย่าง

ข้อมูลนำเข้า 1

8
7 12
0 2 4 5 7 9 11
5 19
-1 4 -1 12 -1
3 7
1 4 -1
7 35
2 -1 12 -1 -1 27 -1
5 14
0 -1 11 -1 -1
3 6
-1 -1 2
3 16
-1 -1 -1
5 14
-1 1 -1 9 -1

ข้อมูลส่งออก 1

3 4 5 7
2 2 7 8
2 1 5 3
0 1 2 5
1 4 1 13
0 1 0 1
0 1 0 1
1 3 1 9