On vous donne trois permutations $a$, $b$ et $c$ de longueur $n$. Appliquer la permutation $c$ au tableau $a$ produit un tableau $d$ tel que $d[c[i]] = a[i]$ pour tout $i$.
Avant d'appliquer $c$ à $a$, vous pouvez effectuer une opération sur la permutation $c$ autant de fois que vous le souhaitez. En une opération, vous pouvez choisir deux indices $i$ et $j$ et échanger $c[i]$ et $c[j]$.
Pour chaque $k$ de $0$ à $n$, trouvez le nombre minimum d'opérations après lesquelles l'application de la permutation modifiée $c$ à $a$ produit un tableau qui diffère de $b$ en exactement $k$ positions, ou déterminez que c'est impossible.
Entrée
La première ligne contient un entier $t$ ($1 \le t \le 5 \cdot 10^4$), le nombre de cas de test.
La première ligne de chaque cas de test contient un entier $n$ ($1 \le n \le 10^6$).
Les trois lignes suivantes contiennent les permutations $a$, $b$ et $c$ de longueur $n$. Chaque permutation contient chaque entier de $1$ à $n$ exactement une fois.
La somme de $n$ sur l'ensemble des cas de test ne dépasse pas $10^6$.
Sortie
Pour chaque cas de test, affichez $n + 1$ entiers, où le $k$-ième d'entre eux est le nombre minimum d'opérations nécessaires pour obtenir exactement $k$ différences, ou $-1$ si c'est impossible.
Exemples
Entrée 1
2 3 1 2 3 3 1 2 2 3 1 2 2 1 1 2 1 2
Sortie 1
0 -1 1 2 1 -1 0
Remarque
Dans le premier cas de test, le tableau est $a = [1, 2, 3]$. Après l'application de la permutation $c = [2, 3, 1]$, l'élément de la $1$-re position se déplace vers la $2$-e, celui de la $2$-e vers la $3$-e, et celui de la $3$-e vers la $1$-re, et le tableau résultant est $d = [3, 1, 2]$. Dans ce cas, il coïncide avec le tableau $b$. Ainsi, la réponse pour $k = 0$ différence est $0$ opération.