Dorijan gav herr Nežmah ett mycket invecklat instrument i present. Instrumentet kan spela $m$ olika toner numrerade från $0$ till $m - 1$. Intressant nog kan det spela en melodi med $n$ toner $s_0, \dots, s_{n-1}$ endast när $n$ är primtal och följande gäller:

• talföljden är strängt växande, dvs. $s_i < s_{i+1}$ för alla $0 \le i < n - 1$,
• det finns $a, b, c$ och $d$ sådana att $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ för alla $0 \le i < n$, där $0 \le a < n$, $1 \le b < n$ och $0 \le c < m$, $1 \le d < m$.

Observera att sådana $a, b, c$ och $d$ entydigt definierar den givna talföljden. Nežmah komponerar för närvarande en ny melodi, och han har redan fyllt i några positioner med toner. Hjälp honom att avsluta melodin! Det räcker att skriva ut vilka $a, b, c$ och $d$ som helst som definierar en giltig talföljd som stämmer överens på de positioner som Nežmah redan har bestämt. Det garanteras att en lösning existerar.

Indata

Den första raden innehåller ett enda heltal $t$ ($1 \le t \le 2 \cdot 10^4$), antalet testfall.

Den första raden i varje testfall innehåller $2$ heltal $n$ och $m$ ($3 \le n \le 3 \cdot 10^5$, $n$ är ett primtal, $n \le m \le 10^9$).

Den andra raden i varje testfall innehåller den resulterande arrayen ($-1 \le u_i < m$, där $u_i = -1$ om Nežmah ännu inte har bestämt vilken ton som ska spelas på denna position).

Det garanteras att summan av $n$ över alla testfall inte överstiger $3 \cdot 10^5$.

Utdata

För varje testfall, skriv ut $1$ rad med $4$ heltal: de efterfrågade värdena på $a$, $b$, $c$ och $d$. Om det finns flera möjliga svar, skriv ut vilket som helst av dem.

Exempel

Indata 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