Ein Koch möchte für die Kinder $m$ Gerichte zubereiten, wobei für jedes Gericht $k$ Gramm Zutaten verwendet werden. Dazu hat er $n$ Arten von Zutaten gekauft, die von $1$ bis $n$ nummeriert sind. Von der $i$-ten Zutatenart sind $d_i$ Gramm vorhanden. Die Gesamtmasse der $n$ Zutatenarten beträgt genau $m \times k$ Gramm, wobei $d_i$ und $k$ positive ganze Zahlen sind.

Eine Zutatenart darf für mehrere Gerichte verwendet werden. Damit der Geschmack der Gerichte jedoch unverfälschter bleibt, möchte der Koch für jedes Gericht höchstens $2$ Zutatenarten verwenden. Entscheide, ob ein Zubereitungsplan existiert, der die Anforderungen erfüllt. Genauer muss der Plan folgende Bedingungen erfüllen:

• Insgesamt werden $m$ Gerichte zubereitet.
• Für jedes Gericht werden höchstens $2$ Zutatenarten verwendet.
• Für jedes Gericht werden genau $k$ Gramm Zutaten verwendet.
• Die Masse jeder in einem Gericht verwendeten Zutatenart ist eine positive ganze Anzahl von Gramm.
• Alle $n$ Zutatenarten werden vollständig aufgebraucht.

Falls ein solcher Plan existiert, sollst du auch einen konkreten Zubereitungsplan angeben.

Eingabe

Die Daten werden aus der Datei dish.in gelesen.

Jede Testdatei dieser Aufgabe enthält mehrere Testfälle.

Die erste Zeile enthält eine ganze Zahl $T$, die Anzahl der Testfälle. Für jeden Testfall gilt:

• Die erste Zeile enthält drei positive ganze Zahlen $n, m, k$: die Anzahl der Zutatenarten, die Anzahl der zuzubereitenden Gerichte und die für jedes Gericht benötigte Masse der Zutaten.
• Die zweite Zeile enthält $n$ ganze Zahlen. Die $i$-te Zahl gibt die Masse $d_i$ der $i$-ten Zutatenart an.

Ausgabe

Schreibe die Ausgabe in die Datei dish.out.

Für jeden Testfall gilt:

• Falls kein Zubereitungsplan existiert, der die Anforderungen erfüllt, gib in einer Zeile die ganze Zahl $-1$ aus.
• Andernfalls musst du $m$ Zeilen ausgeben, von denen jede die Zubereitung eines Gerichts beschreibt. Je nach Anzahl der verwendeten Zutatenarten hat sie eines der beiden folgenden Formate:
  • Gib in einer Zeile die beiden ganzen Zahlen $i$ und $x$ in dieser Reihenfolge aus. Dies bedeutet, dass für das Gericht $x$ Gramm der $i$-ten Zutatenart verwendet werden. Es muss $1 \le i \le n$ und $x = k$ gelten.
  • Gib in einer Zeile die vier ganzen Zahlen $i$, $x$, $j$ und $y$ in dieser Reihenfolge aus. Dies bedeutet, dass für das Gericht $x$ Gramm der $i$-ten und $y$ Gramm der $j$-ten Zutatenart verwendet werden. Es muss $1 \le i,j \le n$, $i \ne j$, $x+y=k$ und $x,y>0$ gelten.

Diese Aufgabe verwendet einen speziellen Prüfer, um die Korrektheit deiner Antwort zu prüfen. Falls mehrere Pläne die Bedingungen erfüllen, genügt es deshalb, einen beliebigen davon auszugeben.

Achte darauf, dass das Ausgabeformat des Plans korrekt ist und benachbarte Zahlen in derselben Zeile durch genau ein Leerzeichen getrennt sind. Darüber hinaus darf deine Ausgabe keine zusätzlichen Zeichen enthalten.

Beispiele

Eingabe 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

Ausgabe 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

Hinweis

Für den zweiten Testfall ist ein gültiger Zubereitungsplan:

• Verwende $80$ Gramm der Zutatenart $1$ und $20$ Gramm der Zutatenart $2$ für das erste Gericht.
• Verwende $10$ Gramm der Zutatenart $2$ und $90$ Gramm der Zutatenart $3$ für das zweite Gericht.
• Verwende $100$ Gramm der Zutatenart $4$ für das dritte Gericht.

Beispiel 2

Siehe dish/dish2.in und dish/dish2.ans im Teilnehmerverzeichnis.

Beispiel 3

Siehe dish/dish3.in und dish/dish3.ans im Teilnehmerverzeichnis.

Beschränkungen

Für alle Testdateien gilt:

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

Die genauen Beschränkungen für die einzelnen Testdateien stehen in der folgenden Tabelle: