أهدى دوريان السيد نيجماه آلة موسيقية معقدة للغاية. يمكن للآلة عزف $m$ من النغمات المختلفة المرقمة من $0$ إلى $m - 1$. ومن المثير للاهتمام أنها لا تستطيع عزف لحن مكون من $n$ نغمة $s_0, \dots, s_{n-1}$ إلا عندما يكون $n$ عددًا أوليًا ويتحقق ما يلي:

• المتتالية متزايدة، أي $s_i < s_{i+1}$ لكل $0 \le i < n - 1$،
• توجد القيم $a, b, c$ و $d$ بحيث يكون $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ لكل $0 \le i < n$، حيث $0 \le a < n$ و $1 \le b < n$ وكذلك $0 \le c < m$ و $1 \le d < m$.

لاحظ أن قيم $a, b, c$ و $d$ هذه تحدد المتتالية المعطاة بشكل فريد. يقوم نيجماه حاليًا بتأليف لحن جديد، وقد ملأ بالفعل بعض المواضع بالنغمات. ساعده في إنهاء اللحن! يكفي طباعة أي قيم $a, b, c$ و $d$ تحدد متتالية صالحة تتطابق في المواضع التي حددها نيجماه بالفعل. من المضمون وجود حل.

الإدخال

يحتوي السطر الأول على عدد صحيح واحد $t$ ($1 \le t \le 2 \cdot 10^4$)، وهو عدد حالات الاختبار.

يحتوي السطر الأول من كل حالة اختبار على عددين صحيحين $2$ هما $n$ و $m$ ($3 \le n \le 3 \cdot 10^5$، $n$ عدد أولي، $n \le m \le 10^9$).

يحتوي السطر الثاني من كل حالة اختبار على المصفوفة الناتجة ($-1 \le u_i < m$، حيث $u_i = -1$ إذا لم يقرر نيجماه بعد أي نغمة يجب عزفها في هذا الموضع).

من المضمون أن مجموع $n$ عبر جميع حالات الاختبار لا يتجاوز $3 \cdot 10^5$.

الإخراج

لكل حالة اختبار، اطبع سطرًا واحدًا ($1$) يحتوي على $4$ أعداد صحيحة: القيم المطلوبة لـ $a$ و $b$ و $c$ و $d$. إذا كانت هناك عدة إجابات ممكنة، فاطبع أيًا منها.

مثال

الإدخال 1

8
7 12
0 2 4 5 7 9 11
5 19
-1 4 -1 12 -1
3 7
1 4 -1
7 35
2 -1 12 -1 -1 27 -1
5 14
0 -1 11 -1 -1
3 6
-1 -1 2
3 16
-1 -1 -1
5 14
-1 1 -1 9 -1

الإخراج 1

3 4 5 7
2 2 7 8
2 1 5 3
0 1 2 5
1 4 1 13
0 1 0 1
0 1 0 1
1 3 1 9