Dorijan ha regalato al signor Nežmah uno strumento molto intricato. Lo strumento può suonare $m$ note diverse numerate da $0$ a $m - 1$. Curiosamente, può suonare una melodia di $n$ note $s_0, \dots, s_{n-1}$ solo quando $n$ è primo e vale quanto segue:

• la sequenza è strettamente crescente, cioè $s_i < s_{i+1}$ per ogni $0 \le i < n - 1$,
• esistono $a, b, c$ e $d$ tali che $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ per ogni $0 \le i < n$, dove $0 \le a < n$, $1 \le b < n$ e $0 \le c < m$, $1 \le d < m$.

Si noti che tali $a, b, c$ e $d$ definiscono univocamente la sequenza data. Nežmah sta attualmente componendo una nuova melodia e ha già riempito alcune posizioni con delle note. Aiutalo a completare la melodia! È sufficiente stampare una qualsiasi quaterna $a, b, c$ e $d$ che definisca una sequenza valida che corrisponda nelle posizioni che Nežmah ha già impostato. È garantito che esista una soluzione.

Input

La prima riga contiene un singolo intero $t$ ($1 \le t \le 2 \cdot 10^4$), il numero di casi di test.

La prima riga di ogni caso di test contiene $2$ interi $n$ e $m$ ($3 \le n \le 3 \cdot 10^5$, $n$ è primo, $n \le m \le 10^9$).

La seconda riga di ogni caso di test contiene l'array risultante ($-1 \le u_i < m$, dove $u_i = -1$ se Nežmah non ha ancora deciso quale nota debba essere suonata in questa posizione).

È garantito che la somma di $n$ su tutti i casi di test non superi $3 \cdot 10^5$.

Output

Per ogni caso di test, stampa $1$ riga con $4$ interi: i valori richiesti di $a$, $b$, $c$ e $d$. Se ci sono più risposte possibili, stampane una qualsiasi.

Esempio

Input 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

Output 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