Доріян подарував панові Нежмаху дуже мудрований музичний інструмент. Інструмент може відтворювати $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