Повар собирается приготовить для детей $m$ блюд, на каждое из которых требуется $k$ граммов ингредиентов. Для этого он приобрёл $n$ видов ингредиентов, пронумерованных от $1$ до $n$. Масса ингредиента вида $i$ равна $d_i$ граммам. Общая масса всех $n$ видов ингредиентов в точности равна $m \times k$ граммам, причём $d_i$ и $k$ — положительные целые числа.

При приготовлении один вид ингредиентов можно использовать в нескольких блюдах. Однако, чтобы вкус блюд был более чистым, повар собирается использовать в каждом блюде не более $2$ видов ингредиентов. Определите, существует ли подходящий способ приготовления. Более точно, он должен удовлетворять следующим требованиям:

• Всего приготовлено $m$ блюд.
• В каждом блюде использовано не более $2$ видов ингредиентов.
• В каждом блюде использовано ровно $k$ граммов ингредиентов.
• Масса каждого используемого в блюде вида ингредиентов составляет положительное целое число граммов.
• Все $n$ видов ингредиентов израсходованы полностью, без остатка.

Если подходящий способ существует, вы также должны указать один конкретный способ приготовления.

Входные данные

Данные читаются из файла dish.in.

Каждый тест содержит несколько наборов данных.

Первая строка содержит целое число $T$ — количество наборов данных. Для каждого набора:

• Первая строка содержит три положительных целых числа $n, m, k$ — количество видов ингредиентов, количество блюд, которые нужно приготовить, и массу ингредиентов для каждого блюда соответственно.
• Вторая строка содержит $n$ целых чисел. Число на позиции $i$ задаёт массу $d_i$ ингредиента вида $i$.

Выходные данные

Выведите ответ в файл dish.out.

Для каждого набора данных:

• Если подходящего способа приготовления не существует, выведите в одной строке одно целое число $-1$.
• Иначе выведите $m$ строк, каждая из которых описывает приготовление одного блюда. В зависимости от количества используемых видов ингредиентов строка должна иметь один из двух форматов:
  • Выведите по порядку два целых числа $i$ и $x$: для блюда используется $x$ граммов ингредиента вида $i$. Должно выполняться $1 \le i \le n$, $x = k$.
  • Выведите по порядку четыре целых числа $i$, $x$, $j$ и $y$: для блюда используются $x$ граммов ингредиента вида $i$ и $y$ граммов ингредиента вида $j$. Должно выполняться $1 \le i,j \le n$, $i \ne j$, $x+y=k$, $x,y>0$.

В этой задаче правильность ответа проверяет специальная проверяющая программа, поэтому, если подходящих способов несколько, достаточно вывести любой один.

Соблюдайте формат вывода: соседние числа в одной строке должны быть разделены ровно одним пробелом, и вывод не должен содержать никаких других лишних символов.

Примеры

Входные данные 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

Выходные данные 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

Примечание

Для второго набора данных подходит следующий способ приготовления:

• Первое блюдо готовится из $80$ граммов ингредиента $1$ и $20$ граммов ингредиента $2$.
• Второе блюдо готовится из $10$ граммов ингредиента $2$ и $90$ граммов ингредиента $3$.
• Третье блюдо готовится из $100$ граммов ингредиента $4$.

Примеры 2

См. файлы dish/dish2.in и dish/dish2.ans в каталоге участника.

Примеры 3

См. файлы dish/dish3.in и dish/dish3.ans в каталоге участника.

Ограничения

Для всех тестов:

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

Ограничения для отдельных тестов приведены в таблице: