נתונות לך שלוש תמורות $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$ פעולות.