O cozinheiro pretende preparar $m$ pratos para as crianças, utilizando $k$ gramas de ingredientes em cada prato. Para isso, comprou $n$ tipos de ingredientes, numerados de $1$ a $n$. A massa do ingrediente do tipo $i$ é $d_i$ gramas. A soma das massas dos $n$ tipos de ingredientes é exatamente $m \times k$ gramas, e tanto $d_i$ como $k$ são inteiros positivos.

Um tipo de ingrediente pode ser utilizado em vários pratos. No entanto, para que os pratos tenham um sabor mais puro, o cozinheiro pretende utilizar no máximo 2 tipos de ingredientes em cada prato. Determine se existe uma forma de preparar os pratos que satisfaça os requisitos. Mais precisamente, o plano deve satisfazer as seguintes condições:

• Preparar um total de $m$ pratos.
• Utilizar no máximo 2 tipos de ingredientes em cada prato.
• Utilizar exatamente $k$ gramas de ingredientes em cada prato.
• A massa de cada tipo de ingrediente utilizado em cada prato deve ser um número inteiro positivo de gramas.
• Consumir exatamente todos os ingredientes dos $n$ tipos.

Se existir um plano que satisfaça os requisitos, deve também apresentar um plano concreto.

Entrada

Os dados são lidos do ficheiro dish.in.

Cada ficheiro de teste deste problema contém vários casos de teste.

A primeira linha contém um inteiro $T$, que indica o número de casos de teste. Para cada caso:

• A primeira linha contém três inteiros positivos $n, m, k$, que representam, respetivamente, o número de tipos de ingredientes, o número de pratos a preparar e a massa de ingredientes necessária em cada prato.
• A segunda linha contém $n$ inteiros; o $i$-ésimo inteiro representa a massa $d_i$ do ingrediente do tipo $i$.

Saída

Escreva a saída no ficheiro dish.out.

Para cada caso de teste:

• Se não existir um plano que satisfaça os requisitos, escreva uma linha com o inteiro $-1$.
• Caso contrário, escreva $m$ linhas, cada uma descrevendo a preparação de um prato. Dependendo do número de tipos de ingredientes utilizados, a linha deve ter um dos dois formatos seguintes:
  • Dois inteiros $i$ e $x$, por esta ordem, indicando que o prato utiliza $x$ gramas do ingrediente do tipo $i$. Deve garantir que $1 \le i \le n$ e $x = k$.
  • Quatro inteiros $i$, $x$, $j$ e $y$, por esta ordem, indicando que o prato utiliza $x$ gramas do ingrediente do tipo $i$ e $y$ gramas do ingrediente do tipo $j$. Deve garantir que $1 \le i, j \le n$, $i \ne j$, $x + y = k$ e $x, y > 0$.

Este problema utiliza um verificador personalizado para verificar a sua resposta. Assim, se existirem vários planos válidos, basta apresentar qualquer um deles.

Garanta que o formato do plano apresentado é correto e que dois números consecutivos na mesma linha estão separados por um único espaço. A saída não deve conter outros caracteres adicionais.

Exemplos

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

Saída 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

Explicação

Para o segundo caso de teste, um plano válido é:

• Preparar o primeiro prato com 80 gramas do ingrediente 1 e 20 gramas do ingrediente 2.
• Preparar o segundo prato com 10 gramas do ingrediente 2 e 90 gramas do ingrediente 3.
• Preparar o terceiro prato com 100 gramas do ingrediente 4.

Exemplo 2

Consulte dish/dish2.in e dish/dish2.ans no diretório do participante.

Exemplo 3

Consulte dish/dish3.in e dish/dish3.ans no diretório do participante.

Restrições

Para todos os ficheiros de teste:

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

As restrições específicas de cada ficheiro de teste constam da tabela seguinte: