Du får gitt tre permutasjoner $a$, $b$ og $c$ med lengde $n$. Å bruke permutasjonen $c$ på tabellen $a$ gir en tabell $d$ slik at $d[c[i]] = a[i]$ for alle $i$.
Før du bruker $c$ på $a$, kan du utføre en operasjon på permutasjonen $c$ så mange ganger du vil. I én operasjon kan du velge to indekser $i$ og $j$ og bytte om $c[i]$ og $c[j]$.
For hver $k$ fra $0$ til $n$, finn det minste antallet operasjoner som gjør at det å bruke den endrede permutasjonen $c$ på $a$ gir en tabell som er ulik $b$ på nøyaktig $k$ posisjoner, eller avgjør at det er umulig.
Inndata
Den første linjen inneholder et heltall $t$ ($1 \le t \le 5 \cdot 10^4$), antallet testtilfeller.
Den første linjen i hvert testtilfelle inneholder et heltall $n$ ($1 \le n \le 10^6$).
De neste tre linjene inneholder permutasjonene $a$, $b$ og $c$ med lengde $n$. Hver permutasjon inneholder hvert heltall fra $1$ til $n$ nøyaktig én gang.
Summen av $n$ over alle testtilfeller overstiger ikke $10^6$.
Utdata
For hvert testtilfelle skal du skrive ut $n + 1$ heltall, der det $k$-te av dem er det minste antallet operasjoner som trengs for å oppnå nøyaktig $k$ forskjeller, eller $-1$ hvis det er umulig.
Eksempler
Inndata 1
2 3 1 2 3 3 1 2 2 3 1 2 2 1 1 2 1 2
Utdata 1
0 -1 1 2 1 -1 0
Forklaring
I det første testtilfellet er tabellen $a = [1, 2, 3]$. Etter å ha brukt permutasjonen $c = [2, 3, 1]$, flyttes elementet fra $1$. posisjon til $2$., fra $2$. til $3$., og fra $3$. til $1$., og den resulterende tabellen er $d = [3, 1, 2]$. I dette tilfellet sammenfaller den med tabellen $b$. Dermed er svaret for $k = 0$ forskjeller $0$ operasjoner.