Dorijan gaf herra Nežmah mjög flókið hljóðfæri. Hljóðfærið getur spilað $m$ ólíka tóna sem eru númeraðir frá $0$ til $m - 1$. Áhugavert er að það getur aðeins spilað lag úr $n$ tónum $s_0, \dots, s_{n-1}$ þegar $n$ er frumtala og eftirfarandi gildir:

• runan er strangt vaxandi, þ.e. $s_i < s_{i+1}$ fyrir öll $0 \le i < n - 1$,
• til eru $a, b, c$ og $d$ þannig að $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ fyrir öll $0 \le i < n$, þar sem $0 \le a < n$, $1 \le b < n$ og $0 \le c < m$, $1 \le d < m$.

Takið eftir að slík $a, b, c$ og $d$ skilgreina gefnu rununa á ótvíræðan hátt. Nežmah er núna að semja nýtt lag og hann hefur þegar fyllt út í nokkrar stöður með tónum. Hjálpaðu honum að klára lagið! Það nægir að prenta hvaða $a, b, c$ og $d$ sem er sem skilgreina gilda runu sem passar í þeim stöðum sem Nežmah hefur þegar ákveðið. Tryggt er að lausn sé til.

Inntak

Fyrsta línan inniheldur eina heiltölu $t$ ($1 \le t \le 2 \cdot 10^4$), fjölda prófunartilvika.

Fyrsta línan í hverju prófunartilviki inniheldur $2$ heiltölur $n$ og $m$ ($3 \le n \le 3 \cdot 10^5$, $n$ er frumtala, $n \le m \le 10^9$).

Önnur línan í hverju prófunartilviki inniheldur fylkið sem myndast ($-1 \le u_i < m$, þar sem $u_i = -1$ ef Nežmah hefur ekki enn ákveðið hvaða tón eigi að spila í þessari stöðu).

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $3 \cdot 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta $1$ línu með $4$ heiltölum: umbeðnum gildum $a$, $b$, $c$ og $d$. Ef það eru margir möguleikar á svari má prenta hvern sem er þeirra.

Dæmi

Inntak 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

Úttak 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