Little Cyan Fish ลืมจำนวนเฉพาะ $P$ ไปแล้ว เขาจำได้เพียงว่า $9 \times 10^{17} \le P \le 10^{18}$

ก่อนที่จะลืม $P$ เขาได้จดจำนวนเต็ม $n$ จำนวน ได้แก่ $a_1, a_2, \dots, a_n$ เอาไว้ นอกจากนี้เขายังได้จดตัวผกผันการคูณของจำนวนเต็มแต่ละตัวภายใต้โมดูโล $P$ แล้วนำตัวผกผันเหล่านี้มาสลับลำดับแบบสุ่มจนได้เป็น $b_1, b_2, \dots, b_n$ ตัวผกผันการคูณของจำนวนเต็ม $x$ ภายใต้โมดูโล $P$ คือจำนวนเต็ม $y$ เพียงตัวเดียวที่ทำให้ $1 \le y < P$ และ $xy \equiv 1 \pmod P$

จงช่วย Little Cyan Fish กู้คืนจำนวนเฉพาะที่สอดคล้องกับรายการทั้งสองของเขา กล่าวอย่างเป็นทางการคือ จงหาจำนวนเฉพาะ $Q$ ที่ทำให้ $9 \times 10^{17} \le Q \le 10^{18}$ โดยที่จำนวนเต็มทุกตัวในรายการทั้งสองมีค่าน้อยกว่า $Q$ และมีเรียงสับเปลี่ยน $\pi$ ของ $1, 2, \dots, n$ ที่สอดคล้องกับ $a_i b_{\pi_i} \equiv 1 \pmod Q$ สำหรับทุกๆ $1 \le i \le n$

ข้อมูลนำเข้าถูกสร้างขึ้นดังต่อไปนี้ จำนวนเฉพาะ $P$ ถูกเลือกโดยสุ่มแบบสม่ำเสมอจากจำนวนเฉพาะทั้งหมดในช่วง $[9 \times 10^{17}, 10^{18}]$ จากนั้นกำหนดให้ $n = 10^5$ และแต่ละ $a_i$ ถูกเลือกอย่างเป็นอิสระและสุ่มแบบสม่ำเสมอจาก $[1, P - 1]$ สุดท้าย ตัวผกผันทั้งหมดจะถูกสลับลำดับโดยสุ่มแบบสม่ำเสมอ ไฟล์ทดสอบที่ต่างกันจะถูกสร้างขึ้นอย่างเป็นอิสระต่อกัน

มีไฟล์ทดสอบอย่างมากที่สุด $20$ ไฟล์

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $n$ เพียงตัวเดียว ($n = 10^5$)

บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน ได้แก่ $a_1, a_2, \dots, a_n$ ($1 \le a_i < 10^{18}$) บรรทัดที่สามประกอบด้วยจำนวนเต็ม $n$ จำนวน ได้แก่ $b_1, b_2, \dots, b_n$ ($1 \le b_i < 10^{18}$)

รับประกันว่ารายการทั้งสองสอดคล้องกับเงื่อนไขที่อธิบายไว้ข้างต้นสำหรับจำนวนเฉพาะ $P$ อย่างน้อยหนึ่งตัว

ข้อมูลส่งออก

แสดงผลบรรทัดเดียวที่ประกอบด้วยจำนวนเต็ม $Q$ เพียงตัวเดียว ซึ่งแทนจำนวนเฉพาะที่สอดคล้องกับรายการทั้งสอง หากมีคำตอบที่ถูกต้องหลายค่า ให้แสดงผลค่าใดก็ได้

ตัวอย่าง

ข้อมูลนำเข้า 1

1
2
499999999999999995

ข้อมูลส่งออก 1

999999999999999989

หมายเหตุ

ตัวอย่างนี้ไม่สอดคล้องกับข้อจำกัดของข้อมูลนำเข้า ตัวอย่างนี้มีไว้เพื่อแสดงรูปแบบของข้อมูลนำเข้าและข้อมูลส่งออกเท่านั้น โปรแกรมของคุณไม่จำเป็นต้องผ่านตัวอย่างนี้

ในตัวอย่าง $P = 999999999999999989$ ตัวอย่างเช่น $2 \times 499999999999999995 = P + 1$