คุณได้รับสามการเรียงสับเปลี่ยน $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$ การดำเนินการ