Dorijan hat Herrn Nežmah ein sehr kompliziertes Instrument geschenkt. Das Instrument kann $m$ verschiedene Noten spielen, die von $0$ bis $m - 1$ nummeriert sind. Interessanterweise kann es eine Melodie aus $n$ Noten $s_0, \dots, s_{n-1}$ nur dann spielen, wenn $n$ eine Primzahl ist und Folgendes gilt:

• die Folge ist streng monoton steigend, d. h. $s_i < s_{i+1}$ für alle $0 \le i < n - 1$,
• es existieren $a, b, c$ und $d$, sodass $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ für alle $0 \le i < n$ gilt, wobei $0 \le a < n$, $1 \le b < n$ und $0 \le c < m$, $1 \le d < m$.

Beachten Sie, dass solche $a, b, c$ und $d$ die gegebene Folge eindeutig definieren. Nežmah komponiert derzeit eine neue Melodie und hat bereits einige Positionen mit Noten gefüllt. Helfen Sie ihm, die Melodie fertigzustellen! Es genügt, beliebige $a, b, c$ und $d$ auszugeben, die eine gültige Folge definieren, welche an den von Nežmah bereits festgelegten Positionen übereinstimmt. Es wird garantiert, dass eine Lösung existiert.

Eingabe

Die erste Zeile enthält eine einzelne ganze Zahl $t$ ($1 \le t \le 2 \cdot 10^4$), die Anzahl der Testfälle.

Die erste Zeile jedes Testfalls enthält $2$ ganze Zahlen $n$ und $m$ ($3 \le n \le 3 \cdot 10^5$, $n$ ist eine Primzahl, $n \le m \le 10^9$).

Die zweite Zeile jedes Testfalls enthält das resultierende Array ($-1 \le u_i < m$, wobei $u_i = -1$ gilt, falls Nežmah noch nicht entschieden hat, welche Note an dieser Position gespielt werden soll).

Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $3 \cdot 10^5$ nicht überschreitet.

Ausgabe

Geben Sie für jeden Testfall $1$ Zeile mit $4$ ganzen Zahlen aus: die gesuchten Werte von $a$, $b$, $c$ und $d$. Wenn es mehrere mögliche Antworten gibt, geben Sie eine beliebige davon aus.

Beispiel

Eingabe 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

Ausgabe 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