Dorijan podarował panu Nežmahowi bardzo skomplikowany instrument. Instrument ten potrafi zagrać $m$ różnych nut ponumerowanych od $0$ do $m - 1$. Co ciekawe, może on zagrać melodię złożoną z $n$ nut $s_0, \dots, s_{n-1}$ tylko wtedy, gdy $n$ jest liczbą pierwszą oraz spełnione są następujące warunki:

• ciąg jest rosnący, tj. $s_i < s_{i+1}$ dla wszystkich $0 \le i < n - 1$,
• istnieją $a, b, c$ oraz $d$ takie, że $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ dla wszystkich $0 \le i < n$, gdzie $0 \le a < n$, $1 \le b < n$ oraz $0 \le c < m$, $1 \le d < m$.

Zauważ, że takie $a, b, c$ oraz $d$ jednoznacznie definiują dany ciąg. Nežmah komponuje obecnie nową melodię i wypełnił już niektóre pozycje nutami. Pomóż mu dokończyć melodię! Wystarczy wypisać dowolne $a, b, c$ oraz $d$, które definiują poprawny ciąg zgadzający się na pozycjach ustalonych już przez Nežmaha. Gwarantuje się, że rozwiązanie istnieje.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 2 \cdot 10^4$), oznaczającą liczbę przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera $2$ liczby całkowite $n$ oraz $m$ ($3 \le n \le 3 \cdot 10^5$, $n$ jest liczbą pierwszą, $n \le m \le 10^9$).

Drugi wiersz każdego przypadku testowego zawiera wynikową tablicę ($-1 \le u_i < m$, gdzie $u_i = -1$, jeśli Nežmah nie zdecydował jeszcze, która nuta powinna zostać zagrana na tej pozycji).

Gwarantuje się, że suma $n$ we wszystkich przypadkach testowych nie przekracza $3 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz $1$ wiersz zawierający $4$ liczby całkowite: wymagane wartości $a$, $b$, $c$ oraz $d$. Jeśli istnieje wiele możliwych odpowiedzi, wypisz dowolną z nich.

Przykład

Wejście 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

Wyjście 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