Se te dan tres permutaciones $a$, $b$ y $c$ de longitud $n$. Aplicar la permutación $c$ al arreglo $a$ produce un arreglo $d$ tal que $d[c[i]] = a[i]$ para todo $i$.
Antes de aplicar $c$ a $a$, puedes realizar una operación sobre la permutación $c$ cualquier número de veces. En una operación, puedes elegir dos índices $i$ y $j$ e intercambiar $c[i]$ y $c[j]$.
Para cada $k$ desde $0$ hasta $n$, encuentra el número mínimo de operaciones tras las cuales aplicar la permutación modificada $c$ a $a$ produce un arreglo que difiere de $b$ en exactamente $k$ posiciones, o determina que es imposible.
Entrada
La primera línea contiene un entero $t$ ($1 \le t \le 5 \cdot 10^4$), el número de casos de prueba.
La primera línea de cada caso de prueba contiene un entero $n$ ($1 \le n \le 10^6$).
Las siguientes tres líneas contienen las permutaciones $a$, $b$ y $c$ de longitud $n$. Cada permutación contiene cada entero desde $1$ hasta $n$ exactamente una vez.
La suma de $n$ en todos los casos de prueba no supera $10^6$.
Salida
Para cada caso de prueba, imprime $n + 1$ enteros, donde el $k$-ésimo de ellos es el número mínimo de operaciones necesarias para obtener exactamente $k$ diferencias, o $-1$ si es imposible.
Ejemplos
Entrada 1
2 3 1 2 3 3 1 2 2 3 1 2 2 1 1 2 1 2
Salida 1
0 -1 1 2 1 -1 0
Nota
En el primer caso de prueba, el arreglo es $a = [1, 2, 3]$. Después de aplicar la permutación $c = [2, 3, 1]$, el elemento de la $1$-ª posición se mueve a la $2$-ª, de la $2$-ª a la $3$-ª y de la $3$-ª a la $1$-ª, y el arreglo resultante es $d = [3, 1, 2]$. En este caso, coincide con el arreglo $b$. Por lo tanto, la respuesta para $k = 0$ diferencias es $0$ operaciones.