Một đầu bếp chuẩn bị làm $m$ món ăn cho các em nhỏ, mỗi món dùng $k$ gam nguyên liệu. Để làm việc này, đầu bếp đã mua $n$ loại nguyên liệu, được đánh số từ $1$ đến $n$; khối lượng của nguyên liệu loại $i$ là $d_i$ gam. Tổng khối lượng của $n$ loại nguyên liệu đúng bằng $m \times k$ gam, trong đó $d_i$ và $k$ đều là số nguyên dương.

Khi chế biến, một loại nguyên liệu có thể được dùng cho nhiều món, nhưng để hương vị của các món ăn thuần khiết hơn, đầu bếp dự định dùng nhiều nhất 2 loại nguyên liệu cho mỗi món. Hãy xác định xem có phương án chế biến nào thỏa mãn yêu cầu hay không. Cụ thể, phương án phải thỏa mãn các yêu cầu sau:

• Làm tổng cộng $m$ món ăn.
• Mỗi món dùng nhiều nhất 2 loại nguyên liệu.
• Mỗi món dùng đúng $k$ gam nguyên liệu.
• Khối lượng của mỗi loại nguyên liệu được dùng trong mỗi món là một số nguyên dương gam.
• Dùng hết vừa đủ cả $n$ loại nguyên liệu.

Nếu tồn tại phương án thỏa mãn yêu cầu, bạn còn phải đưa ra một phương án chế biến cụ thể.

Dữ liệu vào

Đọc dữ liệu từ tệp dish.in.

Mỗi bộ kiểm thử của bài này chứa nhiều bộ dữ liệu.

Dòng đầu tiên chứa một số nguyên $T$ biểu thị số bộ dữ liệu. Với mỗi bộ dữ liệu:

• Dòng đầu tiên chứa ba số nguyên dương $n, m, k$, lần lượt là số loại nguyên liệu, số món ăn cần làm và khối lượng nguyên liệu cần dùng cho mỗi món.
• Dòng thứ hai chứa $n$ số nguyên; số nguyên thứ $i$ là khối lượng $d_i$ của nguyên liệu loại $i$.

Dữ liệu ra

Ghi kết quả vào tệp dish.out.

Với mỗi bộ dữ liệu:

• Nếu không tồn tại phương án chế biến thỏa mãn yêu cầu, in ra một dòng chứa số nguyên $-1$.
• Nếu không, bạn cần in ra $m$ dòng, mỗi dòng mô tả phương án chế biến một món. Tùy theo số loại nguyên liệu được dùng, định dạng là một trong hai dạng sau:
  • In lần lượt hai số nguyên $i$ và $x$ trên một dòng, biểu thị món ăn dùng $x$ gam nguyên liệu loại $i$. Bạn phải bảo đảm $1 \le i \le n$, $x = k$.
  • In lần lượt bốn số nguyên $i$, $x$, $j$ và $y$ trên một dòng, biểu thị món ăn dùng $x$ gam nguyên liệu loại $i$ và $y$ gam nguyên liệu loại $j$. Bạn phải bảo đảm $1 \le i,j \le n$, $i \ne j$, $x+y=k$, $x,y>0$.

Bài này sử dụng trình kiểm tra tùy chỉnh để kiểm tra tính đúng đắn của đáp án, vì vậy nếu có nhiều phương án thỏa mãn điều kiện, bạn chỉ cần in ra một phương án bất kỳ.

Bạn phải bảo đảm định dạng đầu ra của phương án là đúng và hai số liền nhau trên cùng một dòng được phân cách bằng một dấu cách. Ngoài ra, đầu ra không được chứa ký tự thừa nào khác.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 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

Ghi chú

Với bộ dữ liệu thứ hai, một phương án chế biến thỏa mãn yêu cầu là:

• Dùng 80 gam nguyên liệu loại 1 và 20 gam nguyên liệu loại 2 để làm món thứ nhất.
• Dùng 10 gam nguyên liệu loại 2 và 90 gam nguyên liệu loại 3 để làm món thứ hai.
• Dùng 100 gam nguyên liệu loại 4 để làm món thứ ba.

Ví dụ 2

Xem dish/dish2.in và dish/dish2.ans trong thư mục của thí sinh.

Ví dụ 3

Xem dish/dish3.in và dish/dish3.ans trong thư mục của thí sinh.

Giới hạn

Với tất cả các bộ kiểm thử:

$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$.

Giới hạn cụ thể của từng bộ kiểm thử được cho trong bảng sau: