Þér eru gefnar þrjár umraðanir $a$, $b$ og $c$ af lengd $n$. Ef umröðuninni $c$ er beitt á fylkið $a$ fæst fylki $d$ þannig að $d[c[i]] = a[i]$ fyrir öll $i$.
Áður en $c$ er beitt á $a$ máttu framkvæma aðgerð á umröðunina $c$ hversu oft sem er. Í einni aðgerð geturðu valið tvo vísa $i$ og $j$ og víxlað $c[i]$ og $c[j]$.
Fyrir hvert $k$ frá $0$ til $n$, finndu lágmarksfjölda aðgerða þannig að eftir að breyttu umröðuninni $c$ er beitt á $a$ fáist fylki sem er ólíkt $b$ í nákvæmlega $k$ sætum, eða ákvarðaðu að það sé ómögulegt.
Inntak
Fyrsta línan inniheldur heiltölu $t$ ($1 \le t \le 5 \cdot 10^4$), fjölda prófunartilfella.
Fyrsta línan í hverju prófunartilfelli inniheldur heiltölu $n$ ($1 \le n \le 10^6$).
Næstu þrjár línur innihalda umraðanirnar $a$, $b$ og $c$ af lengd $n$. Hver umröðun inniheldur hverja heiltölu frá $1$ til $n$ nákvæmlega einu sinni.
Summa $n$ yfir öll prófunartilfelli fer ekki yfir $10^6$.
Úttak
Fyrir hvert prófunartilfelli skal prenta $n + 1$ heiltölur, þar sem $k$-ta talan er lágmarksfjöldi aðgerða sem þarf til að fá nákvæmlega $k$ mismunandi sæti, eða $-1$ ef það er ómögulegt.
Dæmi
Inntak 1
2 3 1 2 3 3 1 2 2 3 1 2 2 1 1 2 1 2
Úttak 1
0 -1 1 2 1 -1 0
Athugasemd
Í fyrsta prófunartilfellinu er fylkið $a = [1, 2, 3]$. Eftir að umröðuninni $c = [2, 3, 1]$ er beitt færist stakið úr $1$. sæti í $2$. sæti, úr $2$. sæti í $3$. sæti og úr $3$. sæti í $1$. sæti, og fylkið sem fæst er $d = [3, 1, 2]$. Í þessu tilfelli fellur það saman við fylkið $b$. Því er svarið fyrir $k = 0$ mismunandi sæti $0$ aðgerðir.