Gegeben sind drei Permutationen $a$, $b$ und $c$ der Länge $n$. Das Anwenden der Permutation $c$ auf das Array $a$ erzeugt ein Array $d$, sodass $d[c[i]] = a[i]$ für alle $i$ gilt.
Bevor du $c$ auf $a$ anwendest, darfst du beliebig oft eine Operation auf der Permutation $c$ ausführen. In einer Operation kannst du zwei Indizes $i$ und $j$ wählen und $c[i]$ sowie $c[j]$ vertauschen.
Finde für jedes $k$ von $0$ bis $n$ die minimale Anzahl an Operationen, nach denen das Anwenden der modifizierten Permutation $c$ auf $a$ ein Array erzeugt, das sich von $b$ an genau $k$ Positionen unterscheidet, oder stelle fest, dass dies unmöglich ist.
Eingabe
Die erste Zeile enthält eine ganze Zahl $t$ ($1 \le t \le 5 \cdot 10^4$), die Anzahl der Testfälle.
Die erste Zeile jedes Testfalls enthält eine ganze Zahl $n$ ($1 \le n \le 10^6$).
Die nächsten drei Zeilen enthalten die Permutationen $a$, $b$ und $c$ der Länge $n$. Jede Permutation enthält jede ganze Zahl von $1$ bis $n$ genau einmal.
Die Summe von $n$ über alle Testfälle hinweg überschreitet nicht $10^6$.
Ausgabe
Gib für jeden Testfall $n + 1$ ganze Zahlen aus, wobei die $k$-te davon die minimale Anzahl an Operationen ist, die benötigt wird, um genau $k$ Unterschiede zu erhalten, oder $-1$, falls dies unmöglich ist.
Beispiele
Eingabe 1
2 3 1 2 3 3 1 2 2 3 1 2 2 1 1 2 1 2
Ausgabe 1
0 -1 1 2 1 -1 0
Hinweis
Im ersten Testfall lautet das Array $a = [1, 2, 3]$. Nach dem Anwenden der Permutation $c = [2, 3, 1]$ wandert das Element von der $1$. Position an die $2$., von der $2$. an die $3$. und von der $3$. an die $1$., und das resultierende Array ist $d = [3, 1, 2]$. In diesem Fall stimmt es mit dem Array $b$ überein. Daher ist die Antwort für $k = 0$ Unterschiede $0$ Operationen.