Dorijan le regaló al Sr. Nežmah un instrumento muy intrincado. El instrumento puede tocar $m$ notas diferentes numeradas de $0$ a $m - 1$. Curiosamente, solo puede tocar una melodía de $n$ notas $s_0, \dots, s_{n-1}$ cuando $n$ es primo y se cumple lo siguiente:

• la secuencia es creciente, es decir, $s_i < s_{i+1}$ para todo $0 \le i < n - 1$,
• existen $a, b, c$ y $d$ tales que $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ para todo $0 \le i < n$, donde $0 \le a < n$, $1 \le b < n$ y $0 \le c < m$, $1 \le d < m$.

Observa que dichos $a, b, c$ y $d$ definen de manera única la secuencia dada. Nežmah está componiendo actualmente una nueva melodía y ya ha rellenado algunas posiciones con notas. ¡Ayúdalo a terminar la melodía! Basta con imprimir cualesquiera $a, b, c$ y $d$ que definan una secuencia válida que coincida en las posiciones que Nežmah ya ha fijado. Se garantiza que existe una solución.

Entrada

La primera línea contiene un solo entero $t$ ($1 \le t \le 2 \cdot 10^4$), el número de casos de prueba.

La primera línea de cada caso de prueba contiene $2$ enteros $n$ y $m$ ($3 \le n \le 3 \cdot 10^5$, $n$ es primo, $n \le m \le 10^9$).

La segunda línea de cada caso de prueba contiene el arreglo resultante ($-1 \le u_i < m$, donde $u_i = -1$ si Nežmah aún no ha decidido qué nota debe tocarse en esta posición).

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $3 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime $1$ línea con $4$ enteros: los valores requeridos de $a$, $b$, $c$ y $d$. Si hay múltiples respuestas posibles, imprime cualquiera de ellas.

Ejemplo

Entrada 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

Salida 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