Seorang koki akan menyiapkan $m$ hidangan untuk anak-anak, dengan masing-masing hidangan menggunakan $k$ gram bahan. Untuk itu, koki membeli $n$ jenis bahan yang diberi nomor dari $1$ hingga $n$. Massa bahan jenis ke-$i$ adalah $d_i$ gram. Jumlah massa seluruh $n$ jenis bahan tepat $m \times k$ gram, dengan $d_i$ dan $k$ merupakan bilangan bulat positif.

Saat menyiapkan hidangan, satu jenis bahan dapat digunakan untuk beberapa hidangan. Namun, agar rasa hidangan lebih murni, koki berencana menggunakan paling banyak 2 jenis bahan untuk setiap hidangan. Tentukan apakah ada rencana penyiapan yang memenuhi persyaratan. Secara lebih rinci, rencana tersebut harus memenuhi persyaratan berikut:

• Menghasilkan total $m$ hidangan.
• Setiap hidangan menggunakan paling banyak 2 jenis bahan.
• Setiap hidangan menggunakan tepat $k$ gram bahan.
• Massa setiap jenis bahan yang digunakan dalam setiap hidangan harus berupa bilangan bulat positif dalam gram.
• Seluruh $n$ jenis bahan harus habis digunakan tepat tanpa sisa.

Jika ada rencana penyiapan yang memenuhi persyaratan, Anda juga harus memberikan satu rencana penyiapan yang konkret.

Masukan

Baca data dari berkas dish.in.

Satu berkas uji pada soal ini memuat beberapa kasus uji.

Baris pertama berisi sebuah bilangan bulat $T$ yang menyatakan jumlah kasus uji. Untuk setiap kasus uji:

• Baris pertama berisi tiga bilangan bulat positif $n, m, k$, yang masing-masing menyatakan jumlah jenis bahan, jumlah hidangan yang harus disiapkan, dan massa bahan yang diperlukan untuk setiap hidangan.
• Baris kedua berisi $n$ bilangan bulat. Bilangan bulat ke-$i$ menyatakan massa $d_i$ bahan jenis ke-$i$.

Keluaran

Tulis keluaran ke berkas dish.out.

Untuk setiap kasus uji:

• Jika tidak ada rencana penyiapan yang memenuhi persyaratan, keluarkan satu baris berisi bilangan bulat $-1$.
• Jika ada, keluarkan $m$ baris, dengan setiap baris menyatakan rencana penyiapan satu hidangan. Bergantung pada jumlah jenis bahan yang digunakan, formatnya adalah salah satu dari dua bentuk berikut:
  • Keluarkan dua bilangan bulat $i$ dan $x$, secara berurutan dalam satu baris, yang menyatakan bahwa hidangan tersebut dibuat menggunakan $x$ gram bahan jenis ke-$i$. Anda harus memastikan $1 \le i \le n$ dan $x = k$.
  • Keluarkan empat bilangan bulat $i$, $x$, $j$, dan $y$, secara berurutan dalam satu baris, yang menyatakan bahwa hidangan tersebut dibuat menggunakan $x$ gram bahan jenis ke-$i$ dan $y$ gram bahan jenis ke-$j$. Anda harus memastikan $1 \le i,j \le n$, $i \ne j$, $x+y=k$, dan $x,y>0$.

Soal ini menggunakan pemeriksa khusus untuk memeriksa kebenaran jawaban Anda. Oleh karena itu, jika ada beberapa rencana yang memenuhi persyaratan, Anda hanya perlu mengeluarkan salah satunya.

Anda harus memastikan format keluaran rencana benar dan dua bilangan yang bersebelahan pada baris yang sama dipisahkan oleh satu spasi. Selain itu, keluaran Anda tidak boleh memuat karakter tambahan lainnya.

Contoh

Masukan 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

Keluaran 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

Penjelasan

Untuk kasus uji kedua, salah satu rencana penyiapan yang memenuhi persyaratan adalah:

• Gunakan 80 gram bahan 1 dan 20 gram bahan 2 untuk membuat hidangan pertama.
• Gunakan 10 gram bahan 2 dan 90 gram bahan 3 untuk membuat hidangan kedua.
• Gunakan 100 gram bahan 4 untuk membuat hidangan ketiga.

Contoh 2

Lihat dish/dish2.in dan dish/dish2.ans dalam direktori peserta.

Contoh 3

Lihat dish/dish3.in dan dish/dish3.ans dalam direktori peserta.

Batasan

Untuk seluruh berkas uji:

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

Batasan khusus untuk setiap berkas uji ditunjukkan dalam tabel berikut: