給定三個長度為 $n$ 的排列 $a$、$b$ 與 $c$。將排列 $c$ 作用於陣列 $a$ 會產生一個滿足對所有 $i$ 都有 $d[c[i]] = a[i]$ 的陣列 $d$。
在將 $c$ 作用於 $a$ 之前,你可以對排列 $c$ 進行任意次數的操作。在一次操作中,你可以選擇兩個索引 $i$ 與 $j$,並交換 $c[i]$ 與 $c[j]$。
對於從 $0$ 到 $n$ 的每個 $k$,求出最少需要進行多少次操作,使得將修改後的排列 $c$ 作用於 $a$ 所產生的陣列與 $b$ 恰好在 $k$ 個位置上不同,或者判定這是不可能的。
輸入格式
第一行包含一個整數 $t$($1 \le t \le 5 \cdot 10^4$),代表測試資料的組數。
每組測試資料的第一行包含一個整數 $n$($1 \le n \le 10^6$)。
接下來的三行分別包含長度為 $n$ 的排列 $a$、$b$ 與 $c$。每個排列都恰好包含從 $1$ 到 $n$ 的每個整數各一次。
所有測試資料中 $n$ 的總和皆不超過 $10^6$。
輸出格式
對於每組測試資料,輸出 $n + 1$ 個整數,其中第 $k$ 個整數代表為了恰好得到 $k$ 處不同所需的最少操作次數;若不可能,則輸出 $-1$。
範例
輸入格式 1
2 3 1 2 3 3 1 2 2 3 1 2 2 1 1 2 1 2
輸出格式 1
0 -1 1 2 1 -1 0
說明
在第一組測試資料中,陣列為 $a = [1, 2, 3]$。在套用排列 $c = [2, 3, 1]$ 之後,來自第 $1$ 個位置的元素移動到第 $2$ 個位置,第 $2$ 個位置的元素移動到第 $3$ 個位置,第 $3$ 個位置的元素移動到第 $1$ 個位置,最終得到的陣列為 $d = [3, 1, 2]$。在這種情況下,它與陣列 $b$ 完全一致。因此,$k = 0$ 處不同對應的答案為 $0$ 次操作。