長さ $n$ の 3 つの順列 $a$, $b$, $c$ が与えられます。順列 $c$ を配列 $a$ に適用すると、すべての $i$ に対して $d[c[i]] = a[i]$ を満たす配列 $d$ が得られます。
$c$ を $a$ に適用する前に、順列 $c$ に対して操作を何回でも行うことができます。1 回の操作では、2 つの添字 $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$) が与えられます。
続く 3 行には、長さ $n$ の順列 $a$, $b$, $c$ が与えられます。各順列は $1$ から $n$ までのすべての整数をちょうど 1 回ずつ含みます。
すべてのテストケースにわたる $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$ 回の操作です。