料理人は子供たちのために $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$ 番目の整数は、$i$ 番目の材料の質量 $d_i$ を表します。

出力

ファイル dish.out に出力してください。

各テストケースについて、次のように出力してください。

• 条件を満たす作り方が存在しない場合は、整数 $-1$ を一行に出力してください。

• それ以外の場合は、$m$ 行を出力してください。各行は一品の料理の作り方を表し、使う材料の種類数に応じて次のいずれかの形式とします。

  • 二つの整数 $i$ と $x$ をこの順に一行に出力します。これは、$i$ 番目の材料を $x$ グラム使ってその料理を作ることを表します。$1 \le i \le n$、$x=k$ を満たす必要があります。
  • 四つの整数 $i,x,j,y$ をこの順に一行に出力します。これは、$i$ 番目の材料を $x$ グラム、$j$ 番目の材料を $y$ グラム使ってその料理を作ることを表します。$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

注記

二つ目のテストケースでは、条件を満たす作り方の一例は次のとおりです。

• 材料 $1$ を $80$ グラム、材料 $2$ を $20$ グラム使って一品目を作ります。
• 材料 $2$ を $10$ グラム、材料 $3$ を $90$ グラム使って二品目を作ります。
• 材料 $4$ を $100$ グラム使って三品目を作ります。

入出力例 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$。

各テストの具体的な制約は次の表のとおりです。