Un cuisinier prévoit de préparer $m$ plats pour des enfants, chacun utilisant $k$ grammes d'ingrédients. Il a donc acheté $n$ types d'ingrédients, numérotés de $1$ à $n$ ; la masse du type $i$ est de $d_i$ grammes. La masse totale des $n$ types d'ingrédients est exactement de $m \times k$ grammes, où $d_i$ et $k$ sont des entiers strictement positifs.

Un même type d'ingrédient peut être utilisé dans plusieurs plats. Toutefois, pour préserver la pureté du goût, le cuisinier souhaite utiliser au plus 2 types d'ingrédients par plat. Déterminez s'il existe une méthode de préparation satisfaisant ces exigences. Plus précisément, elle doit respecter les conditions suivantes :

• Préparer exactement $m$ plats.
• Utiliser au plus 2 types d'ingrédients par plat.
• Utiliser exactement $k$ grammes d'ingrédients par plat.
• Pour chaque plat, la masse de chaque type d'ingrédient utilisé doit être un nombre entier strictement positif de grammes.
• Utiliser intégralement chacun des $n$ types d'ingrédients.

Si une telle méthode existe, vous devez également en fournir une.

Entrée

Les données sont lues dans le fichier dish.in.

Chaque fichier de test contient plusieurs jeux de données.

La première ligne contient un entier $T$, le nombre de jeux de données. Pour chaque jeu de données :

• La première ligne contient trois entiers strictement positifs $n, m, k$, représentant respectivement le nombre de types d'ingrédients, le nombre de plats à préparer et la masse d'ingrédients nécessaire à chaque plat.
• La deuxième ligne contient $n$ entiers ; le $i$-ème indique la masse $d_i$ du type d'ingrédient $i$.

Sortie

Écrivez la sortie dans le fichier dish.out.

Pour chaque jeu de données :

• S'il n'existe aucune méthode de préparation satisfaisant les exigences, affichez une ligne contenant l'entier $-1$.
• Sinon, affichez $m$ lignes, chacune décrivant la préparation d'un plat, dans l'un des deux formats suivants selon le nombre de types d'ingrédients utilisés :
  • Affichez, dans cet ordre, deux entiers $i$ et $x$ sur une ligne : le plat utilise $x$ grammes du type d'ingrédient $i$. Vous devez respecter $1 \le i \le n$ et $x = k$.
  • Affichez, dans cet ordre, quatre entiers $i$, $x$, $j$ et $y$ sur une ligne : le plat utilise $x$ grammes du type d'ingrédient $i$ et $y$ grammes du type $j$. Vous devez respecter $1 \le i, j \le n$, $i \ne j$, $x + y = k$ et $x, y > 0$.

Un vérificateur personnalisé contrôle votre réponse ; si plusieurs méthodes conviennent, vous pouvez afficher n'importe laquelle.

Vous devez respecter le format de sortie et séparer deux nombres consécutifs d'une même ligne par une seule espace. Votre sortie ne doit contenir aucun autre caractère superflu.

Exemples

Entrée 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

Sortie 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

Remarque

Pour le deuxième jeu de données, une méthode satisfaisant les exigences est la suivante :

• Préparer le premier plat avec $80$ grammes de l'ingrédient $1$ et $20$ grammes de l'ingrédient $2$.
• Préparer le deuxième plat avec $10$ grammes de l'ingrédient $2$ et $90$ grammes de l'ingrédient $3$.
• Préparer le troisième plat avec $100$ grammes de l'ingrédient $4$.

Exemple 2

Voir dish/dish2.in et dish/dish2.ans dans le répertoire du candidat.

Exemple 3

Voir dish/dish3.in et dish/dish3.ans dans le répertoire du candidat.

Contraintes

Pour tous les tests :

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

Les restrictions propres à chaque test sont données dans le tableau suivant :