Ti vengono date tre permutazioni $a$, $b$ e $c$ di lunghezza $n$. Applicare la permutazione $c$ all'array $a$ produce un array $d$ tale che $d[c[i]] = a[i]$ per ogni $i$.
Prima di applicare $c$ ad $a$, puoi eseguire un'operazione sulla permutazione $c$ un numero qualsiasi di volte. In un'operazione, puoi scegliere due indici $i$ e $j$ e scambiare $c[i]$ e $c[j]$.
Per ogni $k$ da $0$ a $n$, trova il numero minimo di operazioni dopo le quali applicare la permutazione modificata $c$ ad $a$ produce un array che differisce da $b$ in esattamente $k$ posizioni, oppure determina che è impossibile.
Input
La prima riga contiene un intero $t$ ($1 \le t \le 5 \cdot 10^4$), il numero di casi di test.
La prima riga di ogni caso di test contiene un intero $n$ ($1 \le n \le 10^6$).
Le tre righe successive contengono le permutazioni $a$, $b$ e $c$ di lunghezza $n$. Ogni permutazione contiene ogni intero da $1$ a $n$ esattamente una volta.
La somma di $n$ su tutti i casi di test non supera $10^6$.
Output
Per ogni caso di test, stampa $n + 1$ interi, dove il $k$-esimo di essi è il numero minimo di operazioni necessarie per ottenere esattamente $k$ differenze, oppure $-1$ se è impossibile.
Esempi
Input 1
2 3 1 2 3 3 1 2 2 3 1 2 2 1 1 2 1 2
Output 1
0 -1 1 2 1 -1 0
Note
Nel primo caso di test, l'array è $a = [1, 2, 3]$. Dopo aver applicato la permutazione $c = [2, 3, 1]$, l'elemento dalla $1$-ª posizione si sposta nella $2$-ª, dalla $2$-ª nella $3$-ª e dalla $3$-ª nella $1$-ª, e l'array risultante è $d = [3, 1, 2]$. In questo caso, coincide con l'array $b$. Pertanto, la risposta per $k = 0$ differenze è $0$ operazioni.