พ่อครัวกำลังเตรียมทำอาหาร $m$ จานให้เด็ก ๆ โดยอาหารแต่ละจานใช้วัตถุดิบ $k$ กรัม พ่อครัวจึงซื้อวัตถุดิบมา $n$ ชนิด ซึ่งมีหมายเลขตั้งแต่ $1$ ถึง $n$ วัตถุดิบชนิดที่ $i$ มีมวล $d_i$ กรัม มวลรวมของวัตถุดิบทั้ง $n$ ชนิดเท่ากับ $m\times k$ กรัมพอดี โดย $d_i$ และ $k$ เป็นจำนวนเต็มบวก

ในการทำอาหาร วัตถุดิบชนิดเดียวกันสามารถใช้ในอาหารหลายจานได้ แต่เพื่อให้รสชาติของอาหารบริสุทธิ์ยิ่งขึ้น พ่อครัวตั้งใจจะใช้วัตถุดิบไม่เกิน 2 ชนิดในอาหารแต่ละจาน จงพิจารณาว่ามีแผนการทำอาหารที่ตรงตามเงื่อนไขหรือไม่ กล่าวอย่างเจาะจง แผนต้องตรงตามข้อกำหนดต่อไปนี้:

• ทำอาหารทั้งหมด $m$ จาน
• อาหารแต่ละจานใช้วัตถุดิบไม่เกิน 2 ชนิด
• อาหารแต่ละจานใช้วัตถุดิบรวม $k$ กรัมพอดี
• มวลของวัตถุดิบแต่ละชนิดที่ใช้ในอาหารแต่ละจานเป็นจำนวนเต็มบวกกรัม
• ใช้วัตถุดิบทั้ง $n$ ชนิดจนหมดพอดี

หากมีแผนที่ตรงตามข้อกำหนด คุณต้องแสดงแผนการทำอาหารที่เป็นรูปธรรมหนึ่งแผนด้วย

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

อ่านข้อมูลจากไฟล์ dish.in

แต่ละชุดทดสอบของข้อนี้มีข้อมูลทดสอบหลายกรณี

บรรทัดแรกมีจำนวนเต็ม $T$ ซึ่งระบุจำนวนกรณีทดสอบ สำหรับแต่ละกรณี:

• บรรทัดแรกมีจำนวนเต็มบวกสามจำนวน $n,m,k$ ซึ่งระบุจำนวนชนิดของวัตถุดิบ จำนวนจานอาหารที่ต้องทำ และมวลของวัตถุดิบที่ใช้ในอาหารแต่ละจาน ตามลำดับ
• บรรทัดที่สองมีจำนวนเต็ม $n$ จำนวน โดยจำนวนที่ $i$ ระบุมวล $d_i$ ของวัตถุดิบชนิดที่ $i$

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

เขียนผลลัพธ์ลงในไฟล์ dish.out

สำหรับแต่ละกรณีทดสอบ:

• หากไม่มีแผนการทำอาหารที่ตรงตามข้อกำหนด ให้พิมพ์จำนวนเต็ม $-1$ เพียงจำนวนเดียวในหนึ่งบรรทัด

• มิฉะนั้น ให้พิมพ์ $m$ บรรทัด แต่ละบรรทัดแสดงแผนการทำอาหารหนึ่งจาน โดยใช้รูปแบบใดรูปแบบหนึ่งต่อไปนี้ตามจำนวนชนิดของวัตถุดิบที่ใช้:

  • พิมพ์จำนวนเต็มสองจำนวน $i$ และ $x$ ตามลำดับในหนึ่งบรรทัด หมายความว่าอาหารจานนี้ใช้วัตถุดิบชนิดที่ $i$ จำนวน $x$ กรัม คุณต้องรับรองว่า $1\le i\le n$ และ $x=k$
  • พิมพ์จำนวนเต็มสี่จำนวน $i,x,j,y$ ตามลำดับในหนึ่งบรรทัด หมายความว่าอาหารจานนี้ใช้วัตถุดิบชนิดที่ $i$ จำนวน $x$ กรัม และวัตถุดิบชนิดที่ $j$ จำนวน $y$ กรัม คุณต้องรับรองว่า $1\le i,j\le n$, $i\ne j$, $x+y=k$ และ $x,y>0$

ข้อนี้ใช้โปรแกรมตรวจคำตอบแบบกำหนดเองเพื่อตรวจว่าคำตอบของคุณถูกต้องหรือไม่ ดังนั้นหากมีหลายแผนที่ตรงตามเงื่อนไข คุณสามารถพิมพ์แผนใดก็ได้หนึ่งแผน

คุณต้องรับรองว่ารูปแบบผลลัพธ์ของแผนถูกต้อง และตัวเลขที่อยู่ติดกันในบรรทัดเดียวกันคั่นด้วยช่องว่างหนึ่งตัว นอกจากนี้ผลลัพธ์ต้องไม่มีอักขระส่วนเกินอื่นใด

ตัวอย่าง

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

4
1 1 10
10
4 3 100
80 30 90 100
5 3 1000
200 400 500 900 1000
6 4 100
25 30 50 80 95 120

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

1 10
1 80 2 20
2 10 3 90
4 100
-1
1 5 5 95
1 20 4 80
2 30 6 70
3 50 6 50

หมายเหตุ

สำหรับกรณีทดสอบที่สอง แผนหนึ่งที่ตรงตามข้อกำหนดคือ:

• ใช้วัตถุดิบชนิดที่ $1$ จำนวน 80 กรัม และวัตถุดิบชนิดที่ $2$ จำนวน 20 กรัม ทำอาหารจานแรก
• ใช้วัตถุดิบชนิดที่ $2$ จำนวน 10 กรัม และวัตถุดิบชนิดที่ $3$ จำนวน 90 กรัม ทำอาหารจานที่สอง
• ใช้วัตถุดิบชนิดที่ $4$ จำนวน 100 กรัม ทำอาหารจานที่สาม

ตัวอย่าง 2

ดูไฟล์ dish/dish2.in และ dish/dish2.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ตัวอย่าง 3

ดูไฟล์ dish/dish3.in และ dish/dish3.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ข้อจำกัด

สำหรับทุกชุดทดสอบ:

$1\le T\le 10$, $1\le n\le 500$, $n-2\le m\le 5000$, $m\ge 1$,

$1\le k\le 5000$, $\sum_{i=1}^{n}d_i=m\times k$

ข้อจำกัดเฉพาะของแต่ละชุดทดสอบแสดงในตารางต่อไปนี้: