Du får tre permutationer $a$, $b$ och $c$ av längd $n$. Att tillämpa permutationen $c$ på fältet $a$ ger ett fält $d$ sådant att $d[c[i]] = a[i]$ för alla $i$.
Innan du tillämpar $c$ på $a$ får du utföra en operation på permutationen $c$ valfritt antal gånger. I en operation kan du välja två index $i$ och $j$ och byta plats på $c[i]$ och $c[j]$.
För varje $k$ från $0$ till $n$, hitta det minsta antalet operationer efter vilka tillämpningen av den modifierade permutationen $c$ på $a$ ger ett fält som skiljer sig från $b$ på exakt $k$ positioner, eller avgör att det är omöjligt.
Indata
Den första raden innehåller ett heltal $t$ ($1 \le t \le 5 \cdot 10^4$), antalet testfall.
Den första raden i varje testfall innehåller ett heltal $n$ ($1 \le n \le 10^6$).
De följande tre raderna innehåller permutationerna $a$, $b$ och $c$ av längd $n$. Varje permutation innehåller varje heltal från $1$ till $n$ exakt en gång.
Summan av $n$ över alla testfall överstiger inte $10^6$.
Utdata
För varje testfall, skriv ut $n + 1$ heltal, där det $k$-te av dem är det minsta antalet operationer som krävs för att få exakt $k$ skillnader, eller $-1$ om det är omöjligt.
Exempel
Indata 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
Förklaring
I det första testfallet är fältet $a = [1, 2, 3]$. Efter att ha tillämpat permutationen $c = [2, 3, 1]$ flyttas elementet från den $1$-sta positionen till den $2$-ndra, från den $2$-ndra till den $3$-dje och från den $3$-dje till den $1$-sta, och det resulterande fältet är $d = [3, 1, 2]$. I detta fall sammanfaller det med fältet $b$. Så svaret för $k = 0$ skillnader är $0$ operationer.