Kucharz zamierza przygotować dla dzieci $m$ dań, zużywając na każde z nich $k$ gramów składników. W tym celu kupił $n$ rodzajów składników, ponumerowanych od $1$ do $n$. Masa składnika rodzaju $i$ wynosi $d_i$ gramów. Łączna masa wszystkich $n$ rodzajów składników wynosi dokładnie $m \times k$ gramów, a $d_i$ i $k$ są dodatnimi liczbami całkowitymi.

Jeden rodzaj składnika można wykorzystać w wielu daniach. Aby jednak smak dań był bardziej wyrazisty, kucharz zamierza użyć w każdym daniu co najwyżej $2$ rodzajów składników. Ustal, czy istnieje sposób przygotowania dań spełniający wymagania. Dokładniej, musi on spełniać następujące warunki:

• Należy przygotować łącznie $m$ dań.
• Każde danie zawiera co najwyżej $2$ rodzaje składników.
• Na każde danie zużywa się dokładnie $k$ gramów składników.
• Masa każdego rodzaju składnika użytego w danym daniu jest dodatnią całkowitą liczbą gramów.
• Wszystkie składniki każdego z $n$ rodzajów zostają zużyte w całości.

Jeżeli istnieje sposób spełniający wymagania, należy również podać jeden taki sposób.

Wejście

Dane należy odczytać z pliku dish.in.

Jeden plik testowy zawiera wiele zestawów danych.

Pierwszy wiersz zawiera liczbę całkowitą $T$, oznaczającą liczbę zestawów danych. Dla każdego zestawu:

• Pierwszy wiersz zawiera trzy dodatnie liczby całkowite $n,m,k$, oznaczające odpowiednio liczbę rodzajów składników, liczbę dań do przygotowania oraz masę składników potrzebnych na każde danie.
• Drugi wiersz zawiera $n$ liczb całkowitych. Liczba na pozycji $i$ oznacza masę $d_i$ składnika rodzaju $i$.

Wyjście

Wynik należy zapisać do pliku dish.out.

Dla każdego zestawu danych:

• Jeżeli nie istnieje sposób przygotowania dań spełniający wymagania, wypisz w jednym wierszu liczbę całkowitą $-1$.

• W przeciwnym przypadku wypisz $m$ wierszy, po jednym dla każdego dania. W zależności od liczby użytych rodzajów składników wiersz musi mieć jeden z dwóch poniższych formatów:

  • Dwie liczby całkowite $i$ oraz $x$, w tej kolejności, oznaczające, że danie przygotowuje się z $x$ gramów składnika rodzaju $i$. Muszą zachodzić warunki $1 \le i \le n$ oraz $x=k$.
  • Cztery liczby całkowite $i$, $x$, $j$ oraz $y$, w tej kolejności, oznaczające, że danie przygotowuje się z $x$ gramów składnika rodzaju $i$ oraz $y$ gramów składnika rodzaju $j$. Muszą zachodzić warunki $1 \le i,j \le n$, $i \ne j$, $x+y=k$ oraz $x,y>0$.

Poprawność odpowiedzi jest sprawdzana przez specjalny program weryfikujący, zatem jeżeli istnieje wiele poprawnych sposobów, wystarczy wypisać dowolny jeden z nich.

Zadbaj o poprawny format odpowiedzi: sąsiednie liczby w tym samym wierszu muszą być oddzielone pojedynczą spacją, a wyjście nie powinno zawierać żadnych innych zbędnych znaków.

Przykład

Wejście 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

Wyjście 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

Uwagi

Dla drugiego zestawu danych jeden ze sposobów spełniających wymagania jest następujący:

• Przygotuj pierwsze danie z $80$ gramów składnika rodzaju $1$ i $20$ gramów składnika rodzaju $2$.
• Przygotuj drugie danie z $10$ gramów składnika rodzaju $2$ i $90$ gramów składnika rodzaju $3$.
• Przygotuj trzecie danie ze $100$ gramów składnika rodzaju $4$.

Przykład 2

Zobacz pliki dish/dish2.in i dish/dish2.ans w katalogu zawodnika.

Przykład 3

Zobacz pliki dish/dish3.in i dish/dish3.ans w katalogu zawodnika.

Ograniczenia

Dla wszystkich testów:

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

Szczegółowe ograniczenia dla poszczególnych testów podano w poniższej tabeli: