Вам задано три перестановки $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$ операцій.