Dorijan a offert à M. Nežmah un instrument très complexe. L'instrument peut jouer $m$ notes différentes numérotées de $0$ à $m - 1$. Fait intéressant, il ne peut jouer une mélodie de $n$ notes $s_0, \dots, s_{n-1}$ que lorsque $n$ est premier et que les conditions suivantes sont vérifiées :

• la suite est strictement croissante, c'est-à-dire $s_i < s_{i+1}$ pour tout $0 \le i < n - 1$,
• il existe $a, b, c$ et $d$ tels que $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ pour tout $0 \le i < n$, où $0 \le a < n$, $1 \le b < n$ et $0 \le c < m$, $1 \le d < m$.

Remarquez que de tels $a, b, c$ et $d$ définissent de manière unique la suite donnée. Nežmah compose actuellement une nouvelle mélodie, et il a déjà rempli certaines positions avec des notes. Aidez-le à terminer la mélodie ! Il suffit d'afficher n'importe quels $a, b, c$ et $d$ qui définissent une suite valide correspondant aux positions que Nežmah a déjà fixées. Il est garanti qu'une solution existe.

Entrée

La première ligne contient un seul entier $t$ ($1 \le t \le 2 \cdot 10^4$), le nombre de cas de test.

La première ligne de chaque cas de test contient $2$ entiers $n$ et $m$ ($3 \le n \le 3 \cdot 10^5$, $n$ est premier, $n \le m \le 10^9$).

La deuxième ligne de chaque cas de test contient le tableau résultant ($-1 \le u_i < m$, où $u_i = -1$ si Nežmah n'a pas encore décidé quelle note doit être jouée à cette position).

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $3 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez $1$ ligne contenant $4$ entiers : les valeurs requises de $a$, $b$, $c$ et $d$. S'il existe plusieurs réponses possibles, affichez l'une quelconque d'entre elles.

Exemple

Entrée 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

Sortie 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