Bạn được cho ba hoán vị $a$, $b$ và $c$ có độ dài $n$. Việc áp dụng hoán vị $c$ lên mảng $a$ sẽ tạo ra một mảng $d$ sao cho $d[c[i]] = a[i]$ với mọi $i$.
Trước khi áp dụng $c$ lên $a$, bạn có thể thực hiện một thao tác trên hoán vị $c$ với số lần tùy ý. Trong một thao tác, bạn có thể chọn hai chỉ số $i$ và $j$ rồi hoán đổi $c[i]$ và $c[j]$.
Với mỗi $k$ từ $0$ đến $n$, hãy tìm số thao tác tối thiểu để sau đó việc áp dụng hoán vị $c$ đã sửa đổi lên $a$ tạo ra một mảng khác với $b$ ở đúng $k$ vị trí, hoặc xác định rằng điều đó là không thể.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 5 \cdot 10^4$), là số lượng bộ dữ liệu.
Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên $n$ ($1 \le n \le 10^6$).
Ba dòng tiếp theo chứa các hoán vị $a$, $b$ và $c$ có độ dài $n$. Mỗi hoán vị chứa mọi số nguyên từ $1$ đến $n$ đúng một lần.
Tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^6$.
Dữ liệu ra
Với mỗi bộ dữ liệu, hãy in ra $n + 1$ số nguyên, trong đó số thứ $k$ là số thao tác tối thiểu cần thiết để thu được đúng $k$ vị trí khác nhau, hoặc $-1$ nếu điều đó là không thể.
Ví dụ
Dữ liệu vào 1
2 3 1 2 3 3 1 2 2 3 1 2 2 1 1 2 1 2
Dữ liệu ra 1
0 -1 1 2 1 -1 0
Ghi chú
Ở bộ dữ liệu đầu tiên, mảng là $a = [1, 2, 3]$. Sau khi áp dụng hoán vị $c = [2, 3, 1]$, phần tử từ vị trí thứ $1$ chuyển sang vị trí thứ $2$, từ vị trí thứ $2$ sang vị trí thứ $3$, và từ vị trí thứ $3$ sang vị trí thứ $1$, nên mảng thu được là $d = [3, 1, 2]$. Trong trường hợp này, nó trùng khớp với mảng $b$. Vì vậy, đáp án cho $k = 0$ vị trí khác nhau là $0$ thao tác.