Dane są trzy permutacje $a$, $b$ oraz $c$ długości $n$. Zastosowanie permutacji $c$ do tablicy $a$ daje tablicę $d$ taką, że $d[c[i]] = a[i]$ dla każdego $i$.
Przed zastosowaniem $c$ do $a$ możesz wykonać operację na permutacji $c$ dowolną liczbę razy. W jednej operacji możesz wybrać dwa indeksy $i$ oraz $j$ i zamienić miejscami $c[i]$ oraz $c[j]$.
Dla każdego $k$ od $0$ do $n$ znajdź minimalną liczbę operacji, po których zastosowanie zmodyfikowanej permutacji $c$ do $a$ daje tablicę różniącą się od $b$ na dokładnie $k$ pozycjach, lub stwierdź, że jest to niemożliwe.
Wejście
Pierwszy wiersz zawiera liczbę całkowitą $t$ ($1 \le t \le 5 \cdot 10^4$), oznaczającą liczbę przypadków testowych.
Pierwszy wiersz każdego przypadku testowego zawiera liczbę całkowitą $n$ ($1 \le n \le 10^6$).
Kolejne trzy wiersze zawierają permutacje $a$, $b$ oraz $c$ długości $n$. Każda permutacja zawiera każdą liczbę całkowitą od $1$ do $n$ dokładnie raz.
Suma $n$ po wszystkich przypadkach testowych nie przekracza $10^6$.
Wyjście
Dla każdego przypadku testowego wypisz $n + 1$ liczb całkowitych, gdzie $k$-ta z nich to minimalna liczba operacji potrzebnych do uzyskania dokładnie $k$ różnic, lub $-1$, jeśli jest to niemożliwe.
Przykład
Wejście 1
2 3 1 2 3 3 1 2 2 3 1 2 2 1 1 2 1 2
Wyjście 1
0 -1 1 2 1 -1 0
Uwagi
W pierwszym przypadku testowym tablica to $a = [1, 2, 3]$. Po zastosowaniu permutacji $c = [2, 3, 1]$ element z $1$. pozycji przechodzi na $2$., z $2$. na $3$., a z $3$. na $1$., w wyniku czego powstaje tablica $d = [3, 1, 2]$. W tym przypadku pokrywa się ona z tablicą $b$. Zatem odpowiedź dla $k = 0$ różnic wynosi $0$ operacji.