השף מתכנן להכין לילדים $m$ מנות, שבכל אחת מהן $k$ גרמים של חומרי גלם. לשם כך הוא קנה $n$ סוגים של חומרי גלם, הממוספרים מ-$1$ עד $n$. המסה של חומר הגלם מסוג $i$ היא $d_i$ גרמים. סכום המסות של כל $n$ סוגי חומרי הגלם הוא בדיוק $m\times k$ גרמים, כאשר $d_i$ ו-$k$ הם מספרים שלמים חיוביים.

אפשר להשתמש באותו סוג של חומר גלם בכמה מנות, אך כדי לשמור על טעם טהור יותר, השף מתכנן להשתמש לכל היותר בשני סוגים של חומרי גלם בכל מנה. עליכם לקבוע אם קיימת תוכנית הכנה העומדת בדרישות. בפרט, התוכנית צריכה לקיים את התנאים הבאים:

• מכינים בסך הכול $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$.

המגבלות המסוימות לכל בדיקה מופיעות בטבלה הבאה: