Cho các số nguyên tố phân biệt \(p_1, p_2, \dots, p_k\) và các số dư \(r_1, r_2, \dots, r_k\). Tìm số \(x\) nhỏ nhất thỏa \(x \equiv r_i \pmod{p_i}\).

Định dạng đầu vào

• Dòng đầu: số nguyên \(k\) (\(2 \le k \le 10\)).
• Dòng hai: \(k\) số nguyên tố \(p_i\).
• Dòng ba: \(k\) số dư \(r_i\).

Định dạng đầu ra

• Một số nguyên là nghiệm nhỏ nhất.

Ví dụ

Input:

3
3 5 7
2 3 2

Output:

23

Ràng buộc

• 100% số điểm: \(p_i \le 10^9\), \(M \le 10^{18}\).