给定三个长度为 $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$ 次操作。