Кухар збирається приготувати для дітей $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$.

Конкретні обмеження для кожного тесту наведено в таблиці: