Вам даны три перестановки $a$, $b$ и $c$ длины $n$. Применение перестановки $c$ к массиву $a$ даёт массив $d$, такой что $d[c[i]] = a[i]$ для всех $i$.
Перед применением $c$ к $a$ вы можете выполнить операцию над перестановкой $c$ любое количество раз. За одну операцию вы можете выбрать два индекса $i$ и $j$ и поменять местами $c[i]$ и $c[j]$.
Для каждого $k$ от $0$ до $n$ найдите минимальное количество операций, после которых применение изменённой перестановки $c$ к $a$ даёт массив, отличающийся от $b$ ровно в $k$ позициях, или определите, что это невозможно.
Входные данные
Первая строка содержит целое число $t$ ($1 \le t \le 5 \cdot 10^4$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $n$ ($1 \le n \le 10^6$).
Следующие три строки содержат перестановки $a$, $b$ и $c$ длины $n$. Каждая перестановка содержит каждое целое число от $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$ операциям.