Sinulle annetaan kolme pituutta $n$ olevaa permutaatiota $a$, $b$ ja $c$. Permutaation $c$ soveltaminen taulukkoon $a$ tuottaa taulukon $d$, jolle pätee $d[c[i]] = a[i]$ kaikilla $i$.
Ennen kuin sovellat permutaatiota $c$ taulukkoon $a$, voit suorittaa permutaatiolle $c$ operaation mielivaltaisen monta kertaa. Yhdessä operaatiossa voit valita kaksi indeksiä $i$ ja $j$ ja vaihtaa alkiot $c[i]$ ja $c[j]$ keskenään.
Etsi jokaiselle $k$ väliltä $0$:sta $n$:ään pienin määrä operaatioita, joiden jälkeen muokatun permutaation $c$ soveltaminen taulukkoon $a$ tuottaa taulukon, joka eroaa taulukosta $b$ täsmälleen $k$ kohdassa, tai päätä, että se on mahdotonta.
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $t$ ($1 \le t \le 5 \cdot 10^4$), testitapausten lukumäärän.
Kunkin testitapauksen ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 10^6$).
Seuraavat kolme riviä sisältävät pituutta $n$ olevat permutaatiot $a$, $b$ ja $c$. Jokainen permutaatio sisältää jokaisen kokonaisluvun väliltä $1$:stä $n$:ään täsmälleen kerran.
Lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^6$.
Tuloste
Tulosta jokaiselle testitapaukselle $n + 1$ kokonaislukua, joista $k$:s on pienin tarvittava operaatioiden määrä täsmälleen $k$ eron saamiseksi, tai $-1$, jos se on mahdotonta.
Esimerkit
Syöte 1
2 3 1 2 3 3 1 2 2 3 1 2 2 1 1 2 1 2
Tuloste 1
0 -1 1 2 1 -1 0
Huomautus
Ensimmäisessä testitapauksessa taulukko on $a = [1, 2, 3]$. Permutaation $c = [2, 3, 1]$ soveltamisen jälkeen alkio $1$. sijainnista siirtyy $2$. sijaintiin, $2$. sijainnista $3$. sijaintiin ja $3$. sijainnista $1$. sijaintiin, ja tuloksena saatava taulukko on $d = [3, 1, 2]$. Tässä tapauksessa se on sama kuin taulukko $b$. Siispä vastaus $k = 0$ erolle on $0$ operaatiota.