Dorijan ga herr Nežmah et svært intrikat instrument i gave. Instrumentet kan spille $m$ forskjellige toner nummerert fra $0$ til $m - 1$. Interessant nok kan det spille en melodi med $n$ toner $s_0, \dots, s_{n-1}$ bare når $n$ er et primtall og følgende er sant:

• følgen er strengt stigende, dvs. $s_i < s_{i+1}$ for alle $0 \le i < n - 1$,
• det finnes $a, b, c$ og $d$ slik at $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ for alle $0 \le i < n$, der $0 \le a < n$, $1 \le b < n$ og $0 \le c < m$, $1 \le d < m$.

Legg merke til at slike $a, b, c$ og $d$ entydig definerer den gitte følgen. Nežmah komponerer for tiden en ny melodi, og han har allerede fylt ut noen posisjoner med toner. Hjelp ham med å fullføre melodien! Det er nok å skrive ut hvilke som helst $a, b, c$ og $d$ som definerer en gyldig følge som stemmer overens i posisjonene Nežmah allerede har satt. Det er garantert at en løsning finnes.

Inndata

Den første linjen inneholder et enkelt heltall $t$ ($1 \le t \le 2 \cdot 10^4$), antallet testtilfeller.

Den første linjen i hvert testtilfelle inneholder $2$ heltall $n$ og $m$ ($3 \le n \le 3 \cdot 10^5$, $n$ er et primtall, $n \le m \le 10^9$).

Den andre linjen i hvert testtilfelle inneholder den resulterende tabellen ($-1 \le u_i < m$, der $u_i = -1$ hvis Nežmah ennå ikke har bestemt hvilken tone som skal spilles i denne posisjonen).

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $3 \cdot 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut $1$ linje med $4$ heltall: de nødvendige verdiene for $a$, $b$, $c$ og $d$. Hvis det finnes flere mulige svar, kan du skrive ut hvilket som helst av dem.

Eksempel

Inndata 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

Utdata 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