Cho một số nguyên dương ~N~ (~1 \le N \le 10^{12}~). Bạn hãy kiểm tra xem tổng tất cả các ước số của ~N~ (bao gồm cả ~1~ và chính nó) có phải là một số nguyên tố hay không.

Dữ liệu vào: Vào từ tệp văn bản TONGNT.INP:

• Gồm một dòng duy nhất chứa số nguyên dương ~N~.

Kết quả: Ghi ra tệp văn bản TONGNT.OUT:

• In ra YES nếu tổng các ước số của ~N~ là số nguyên tố, ngược lại in ra NO.

Ví dụ:

Giải thích ví dụ 1: Số 4 có các ước là 1, 2, 4. Tổng các ước là 1 + 2 + 4 = 7. Vì 7 là số nguyên tố nên kết quả là YES. Giải thích ví dụ 2: Số 6 có các ước là 1, 2, 3, 6. Tổng các ước là 1 + 2 + 3 + 6 = 12. Vì 12 không phải là số nguyên tố nên kết quả là NO.

Ràng buộc dữ liệu:

• Subtask 1 (40% số điểm): ~1 \le N \le 10^6~.
• Subtask 2 (60% số điểm): ~1 \le N \le 10^{12}~.

Một xâu nhị phân được định nghĩa là hoàn hảo khi thỏa mãn đồng thời hai điều kiện sau:

• Số lượng ký tự ~1~ bằng số lượng ký tự ~0~.
• Xâu ban đầu là một dãy không giảm (tức là tất cả các ký tự ~0~ đều đứng trước tất cả các ký tự ~1~, xâu có dạng ~00...011...1~).

Cho một xâu nhị phân ~S~ gồm ~N~ ký tự. Bạn hãy kiểm tra xem xâu ~S~ có phải là xâu nhị phân hoàn hảo hay không.

Dữ liệu vào: Vào từ tệp văn bản PERFECT.INP:

• Gồm một dòng duy nhất chứa xâu nhị phân ~S~.

Kết quả: Ghi ra tệp văn bản PERFECT.OUT:

• In ra YES nếu xâu ~S~ là xâu nhị phân hoàn hảo, ngược lại in ra NO.

Ví dụ:

Giải thích ví dụ 1: Xâu 0011 có 2 số 0 và 2 số 1 (bằng nhau), đồng thời xếp tăng dần không giảm nên là xâu hoàn hảo. Giải thích ví dụ 2: Xâu 0101 tuy có số lượng 0 và 1 bằng nhau nhưng không phải là dãy không giảm.

Ràng buộc dữ liệu:

• Subtask 1 (40% số điểm): Độ dài xâu ~1 \le N \le 100~.
• Subtask 2 (60% số điểm): Độ dài xâu ~1 \le N \le 10^6~.

Nhân dịp Tết Nguyên Đán, Mai Thế Dũng xúng xính quần áo mới bước vào hành trình đi chúc Tết bà con lối xóm để "hái lộc" đầu xuân. Khu phố của Dũng có một dãy nhà dài, Dũng quyết định bắt đầu từ nhà số ~0~ và đi lần lượt đến nhà số ~N~.

Quy tắc nhận lì xì ở khu phố này cực kỳ thú vị:

• Tại ngôi nhà đầu tiên (nhà số ~0~), Dũng ngoan ngoãn chúc Tết và nhận được phong bao lì xì trị giá ~A~ đồng.
• Tại mỗi ngôi nhà tiếp theo, nhờ tài ăn nói ngày càng ngọt ngào, số tiền Dũng được mừng tuổi luôn tăng thêm đúng ~X~ đồng so với ngôi nhà ngay trước đó.
• Quy luật này cứ thế tiếp diễn cho đến khi Dũng bước ra khỏi ngôi nhà cuối cùng (nhà số ~N~).

Sau khi đi hết một vòng, Dũng cần nạp toàn bộ số tiền này vào tài khoản ngân hàng để bảo mật. Tuy nhiên, hệ thống ngân hàng yêu cầu Dũng phải nhập một "mật mã khóa két", chính là tổng số tiền thu được chia lấy phần dư cho ~998244353~. Bạn hãy giúp Mai Thế Dũng tính xem mật mã này là số mấy nhé!

Dữ liệu vào: Vào từ tệp văn bản LIXI.INP:

• Gồm một dòng duy nhất chứa ~3~ số nguyên ~N, A, X~ cách nhau bởi dấu cách.

Kết quả: Ghi ra tệp văn bản LIXI.OUT:

• In ra một số nguyên duy nhất là mật mã khóa két (Tổng số tiền thu được modulo ~998244353~).

Ví dụ:

Giải thích: Số tiền nhận được ở các trạm ~0, 1, 2, 3~ lần lượt là ~2, 3, 4, 5~. Tổng tiền nhận được là ~2 + 3 + 4 + 5 = 14~. Mật mã là ~14 \bmod 998244353 = 14~.

Ràng buộc dữ liệu:

• Subtask 1 (40% số điểm): ~1 \le N \le 10^3~; ~0 \le A, X \le 10^9~
• Subtask 2 (60% số điểm): ~1 \le N \le 10^6~; ~0 \le A, X \le 10^9~

Xưởng gạch chỉ sản xuất gạch lát nền hình vuông với cạnh thuộc một danh mục cố định gồm ~k~ kích thước:

~s_1 < s_2 < \ldots < s_k~

Trong đó luôn có kích thước cơ bản ~s_1 = 1~.

Khách hàng cần lát kín ~m~ nền nhà. Nền nhà thứ ~j~ là hình chữ nhật có kích thước ~p_j \times q_j~. Mỗi nền chỉ được lát bằng một loại gạch vuông duy nhất có cạnh thuộc danh mục. Các viên gạch phải vừa khít theo cả hai chiều, không bị cắt và không để hở nền.

Với mỗi nền nhà, loại gạch hợp lệ có cạnh lớn nhất luôn được chọn để số viên gạch cần dùng là ít nhất.

Trong toàn bộ ~m~ nền nhà, gọi ~s_{\max}~ là kích thước cạnh lớn nhất trong số các loại gạch thực tế đã được sử dụng.

Yêu cầu

Hãy tính tổng số viên gạch có kích thước cạnh ~s_{\max}~ đã được dùng để lát các nền nhà.

Input

Từ tệp văn bản TILE.INP:

• Dòng đầu tiên chứa hai số nguyên ~k, m~ ~(2 \le k,m \le 10^6)~;
• Dòng thứ hai chứa ~k~ số nguyên dương tăng dần ~s_1, s_2, \ldots, s_k~ ~(1 \le s_i \le 10^6)~, với ~s_1 = 1~;
• ~m~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên ~p_j, q_j~ ~(1 \le p_j,q_j \le 10^6)~, là kích thước nền nhà thứ ~j~.

Output

Ghi vào tệp văn bản TILE.OUT:

• Một số nguyên duy nhất là tổng số viên gạch có kích thước cạnh lớn nhất đã được sử dụng.

Ràng buộc

• Subtask 1 (40% số điểm): ~k,m \le 10^3~;
• Subtask 2 (40% số điểm): ~k \le 10^5~, ~m \le 10^4~;
• Subtask 3 (20% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

4 2
1 2 4 6
12 18
16 24

Output

6

Giải thích

• Nền thứ nhất chọn gạch cạnh ~6~ và dùng ~\dfrac{12}{6}\times\dfrac{18}{6}=6~ viên;
• Nền thứ hai chọn gạch cạnh ~4~ và dùng ~\dfrac{16}{4}\times\dfrac{24}{4}=24~ viên.

Kích thước lớn nhất đã được sử dụng là ~6~, nên chỉ tính ~6~ viên gạch cạnh ~6~ của nền thứ nhất.