畀定三個長度為 $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$ 次操作。