أُعطيت ثلاث تبديلات $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$ عمليات.