Anda diberikan tiga permutasi $a$, $b$, dan $c$ dengan panjang $n$. Menerapkan permutasi $c$ pada larik $a$ menghasilkan sebuah larik $d$ sedemikian sehingga $d[c[i]] = a[i]$ untuk semua $i$.
Sebelum menerapkan $c$ pada $a$, Anda dapat melakukan operasi pada permutasi $c$ berapa kali pun. Dalam satu operasi, Anda dapat memilih dua indeks $i$ dan $j$ lalu menukar $c[i]$ dan $c[j]$.
Untuk setiap $k$ dari $0$ hingga $n$, carilah jumlah operasi minimum sehingga setelah menerapkan permutasi $c$ yang telah dimodifikasi pada $a$, dihasilkan larik yang berbeda dari $b$ di tepat $k$ posisi, atau tentukan bahwa hal tersebut tidak mungkin.
Masukan
Baris pertama berisi sebuah bilangan bulat $t$ ($1 \le t \le 5 \cdot 10^4$), yaitu banyaknya kasus uji.
Baris pertama dari setiap kasus uji berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^6$).
Tiga baris berikutnya berisi permutasi $a$, $b$, dan $c$ dengan panjang $n$. Setiap permutasi memuat setiap bilangan bulat dari $1$ hingga $n$ tepat satu kali.
Jumlah nilai $n$ di seluruh kasus uji tidak melebihi $10^6$.
Keluaran
Untuk setiap kasus uji, keluarkan $n + 1$ bilangan bulat, dengan bilangan ke-$k$ adalah jumlah operasi minimum yang diperlukan untuk memperoleh tepat $k$ perbedaan, atau $-1$ jika hal tersebut tidak mungkin.
Contoh
Masukan 1
2 3 1 2 3 3 1 2 2 3 1 2 2 1 1 2 1 2
Keluaran 1
0 -1 1 2 1 -1 0
Catatan
Pada kasus uji pertama, lariknya adalah $a = [1, 2, 3]$. Setelah menerapkan permutasi $c = [2, 3, 1]$, elemen dari posisi ke-$1$ berpindah ke posisi ke-$2$, dari posisi ke-$2$ ke posisi ke-$3$, dan dari posisi ke-$3$ ke posisi ke-$1$, sehingga larik yang dihasilkan adalah $d = [3, 1, 2]$. Dalam kasus ini, larik tersebut berimpit dengan larik $b$. Jadi, jawaban untuk $k = 0$ perbedaan adalah $0$ operasi.