يستعد الطاهي لإعداد $m$ أطباق للأطفال، ويستخدم كل طبق $k$ غرامًا من المكونات. لهذا الغرض، اشترى الطاهي $n$ أنواع من المكونات، مرقمة من $1$ إلى $n$، وتبلغ كتلة المكون من النوع $i$ مقدار $d_i$ غرامًا. مجموع كتل الأنواع $n$ يساوي بالضبط $m \times k$ غرامًا، وكل من $d_i$ و$k$ عدد صحيح موجب.

عند إعداد الأطباق، يمكن استخدام نوع واحد من المكونات في عدة أطباق. ولكن لكي يكون مذاق الأطباق أنقى، ينوي الطاهي استخدام نوعين من المكونات على الأكثر في كل طبق. عليك الآن تحديد ما إذا كانت هناك خطة إعداد تستوفي المتطلبات. وبصورة أدق، يجب أن تحقق الخطة الشروط التالية:

• إعداد $m$ أطباق في المجموع.
• استخدام نوعين من المكونات على الأكثر في كل طبق.
• استخدام $k$ غرامًا من المكونات بالضبط في كل طبق.
• أن تكون كتلة كل نوع من المكونات المستخدمة في كل طبق عددًا صحيحًا موجبًا من الغرامات.
• استهلاك جميع المكونات من الأنواع $n$ بالكامل، دون زيادة أو نقصان.

إذا كانت هناك خطة إعداد تستوفي المتطلبات، فعليك أيضًا تقديم خطة محددة.

الإدخال

تُقرأ البيانات من الملف dish.in.

تحتوي نقطة الاختبار الواحدة في هذه المسألة على عدة حالات اختبار.

يحتوي السطر الأول على عدد صحيح $T$ يمثل عدد حالات الاختبار. ولكل حالة:

• يحتوي السطر الأول على ثلاثة أعداد صحيحة موجبة $n, m, k$ تمثل، على الترتيب، عدد أنواع المكونات، وعدد الأطباق المطلوب إعدادها، وكتلة المكونات التي يحتاج إليها كل طبق.
• يحتوي السطر الثاني على $n$ أعداد صحيحة؛ يمثل العدد الصحيح رقم $i$ كتلة المكون من النوع $i$، أي $d_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$.

القيود المحددة لكل نقطة اختبار موضحة في الجدول التالي: