Un cocinero va a preparar $m$ platos para unos niños, utilizando $k$ gramos de ingredientes en cada plato. Para ello ha comprado $n$ tipos de ingredientes, numerados del $1$ al $n$. La cantidad del ingrediente de tipo $i$ es de $d_i$ gramos. La suma de las cantidades de los $n$ tipos de ingredientes es exactamente $m \times k$ gramos, donde tanto $d_i$ como $k$ son enteros positivos.

Al preparar los platos, un mismo tipo de ingrediente puede utilizarse en varios platos. Sin embargo, para que el sabor de los platos sea más puro, el cocinero quiere utilizar como máximo 2 tipos de ingredientes por plato. Determina si existe un plan de preparación que cumpla estos requisitos. Más concretamente, el plan debe satisfacer lo siguiente:

• Preparar un total de $m$ platos.
• Utilizar como máximo 2 tipos de ingredientes en cada plato.
• Utilizar exactamente $k$ gramos de ingredientes en cada plato.
• La cantidad de cada tipo de ingrediente utilizado en cada plato debe ser un número entero positivo de gramos.
• Agotar exactamente los $n$ tipos de ingredientes.

Si existe un plan de preparación que cumpla los requisitos, también debes proporcionar uno concreto.

Entrada

Los datos se leen del archivo dish.in.

Cada caso de prueba de este problema contiene varios conjuntos de datos.

La primera línea contiene un entero $T$ que indica el número de conjuntos de datos. Para cada conjunto:

• La primera línea contiene tres enteros positivos $n, m, k$, que indican, respectivamente, el número de tipos de ingredientes, el número de platos que deben prepararse y la cantidad de ingredientes necesaria para cada plato.
• La segunda línea contiene $n$ enteros. El entero $i$-ésimo indica la cantidad $d_i$ del ingrediente de tipo $i$.

Salida

La salida se escribe en el archivo dish.out.

Para cada conjunto de datos:

• Si no existe un plan de preparación que cumpla los requisitos, escribe una línea con el entero $-1$.

• En caso contrario, debes escribir $m$ líneas, cada una con el plan de preparación de un plato. Según el número de tipos de ingredientes utilizados, el formato será uno de los dos siguientes:

  • Escribe en una línea dos enteros, $i$ y $x$, en ese orden, para indicar que el plato se prepara utilizando $x$ gramos del ingrediente de tipo $i$. Debes garantizar que $1 \le i \le n$ y $x = k$.

  • Escribe en una línea cuatro enteros, $i$, $x$, $j$ e $y$, en ese orden, para indicar que el plato se prepara utilizando $x$ gramos del ingrediente de tipo $i$ e $y$ gramos del ingrediente de tipo $j$. Debes garantizar que $1 \le i, j \le n$, $i \ne j$, $x + y = k$ y $x, y > 0$.

Este problema utiliza un verificador personalizado para comprobar tu respuesta. Por tanto, si hay varios planes que cumplen las condiciones, basta con que escribas cualquiera de ellos.

Debes garantizar que el formato de salida del plan sea correcto y que dos números consecutivos de una misma línea estén separados por un único espacio. Aparte de eso, tu salida no debe contener ningún carácter adicional.

Ejemplos

Entrada 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

Salida 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

Nota

Para el segundo conjunto de datos, un plan de preparación que cumple los requisitos es:

• Utilizar 80 gramos del ingrediente 1 y 20 gramos del ingrediente 2 para preparar el primer plato.
• Utilizar 10 gramos del ingrediente 2 y 90 gramos del ingrediente 3 para preparar el segundo plato.
• Utilizar 100 gramos del ingrediente 4 para preparar el tercer plato.

Ejemplo 2

Consulta dish/dish2.in y dish/dish2.ans en el directorio de los concursantes.

Ejemplo 3

Consulta dish/dish3.in y dish/dish3.ans en el directorio de los concursantes.

Restricciones

Para todos los casos de prueba:

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

Las restricciones específicas de cada caso de prueba se muestran en la siguiente tabla: