Hai đèn chùm

Hai chiếc đèn chùm thay đổi màu theo chu kỳ. Đèn thứ nhất có $n$ màu khác nhau $a_1,a_2,\dots ,a_n$, đèn thứ hai có $m$ màu khác nhau $b_1,b_2,\dots ,b_m$. Tại ngày $i$ (đếm từ $i=1$):

• Đèn thứ nhất hiện màu $a_x$ với $x=((i-1)modn)+1$.
• Đèn thứ hai hiện màu $b_y$ với $y=((i-1)modm)+1$.

Có những ngày màu của hai đèn giống nhau, có những ngày khác nhau. Hãy tìm ngày thứ $i$ — chính là lần thứ $k$ mà hai đèn hiển thị màu khác nhau.

Đảm bảo rằng dãy $a$ và dãy $b$ khác nhau (xét cả về tập màu và thứ tự), nên luôn tồn tại ngày khác màu.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• Dòng thứ hai chứa $n$ số nguyên đôi một khác nhau $a_1,\dots ,a_n$.
• Dòng thứ ba chứa $m$ số nguyên đôi một khác nhau $b_1,\dots ,b_m$.

Dữ liệu ra

In ra một số nguyên — chỉ số ngày tại lần thứ $k$ hai đèn khác màu.

Ràng buộc

• $1\le n,m\le 5·{10}^5$.
• $1\le k\le {10}^{12}$.
• $1\le a_i,b_j\le 2max(n,m)$.
• Đảm bảo dãy $a$ khác dãy $b$.

Ví dụ

Ghi chú

Gợi ý: dùng định lý số dư Trung Hoa (CRT) để xác định trong một chu kỳ độ dài $lcm(n,m)$ có bao nhiêu ngày hai đèn cùng màu.