Cho số nguyên dương ~N~ và hai số nguyên tố ~A, B~.

Yêu cầu

Hỏi có bao nhiêu số không lớn hơn ~N~ chỉ chia hết cho ~A~ hoặc ~B~?

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất ghi số nguyên dương ~N~ ~(1 \le N \le 10^9)~;
• Dòng thứ hai ghi hai số nguyên tố ~A,\ B~ ~(A, B < N)~.

Dữ liệu đầu ra

Ghi một số nguyên là kết quả của bài toán.

Ràng buộc dữ liệu

• Có 90% test tương ứng 90% điểm với ~N \le 10^6;\ A, B < N~;
• Có 10% test tương ứng với 10% điểm với ~10^6 < N \le 10^9; A, B < N~.

Ví dụ

Ví dụ 1

INPUT

10
2 3

OUTPUT

6

Giải thích:

• Các số chia hết cho ~2~ là ~2, 4, 6, 8, 10~;
• Các số chia hết cho ~3~ là ~3, 6, 9~;
• Các số chỉ chia hết cho ~2~ hoặc ~3~ là ~2, 3, 4, 8, 9, 10~ (~6~ số). Số ~6~ chia hết cho cả ~2~ và ~3~.

Một số nguyên dương có đúng ~3~ ước số nguyên dương khác nhau được gọi là số TNUM.

Yêu cầu

Cho trước một dãy ~N~ số nguyên dương, xác định các số đã cho có phải là số TNUM hay không?

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên ghi số duyên dương ~N~ ~(N \le 10^6)~;
• Dòng tiếp theo ghi ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ ~(a_i \le 10^{12};\ i = 1..N)~.

Dữ liệu đầu ra

Gồm ~N~ dòng, dòng thứ ~i~ ghi YES nếu số thứ ~i~ là số TNUM, ngược lại thì ghi NO.

Ràng buộc dữ liệu

• Có 70% test tương ứng 70% điểm với ~a_i \le 10^4~ ~(i = 1..N)~, ~N \le 10^4~;
• Có 15% test tương ứng 15% điểm với ~10^4 < a_i \le 10^{10}~ ~(i = 1..N)~, ~10^4 < N \le 10^5~;
• Có 15% test tương ứng 15% điểm với ~10^{10} < a_i \le 10^{12}~ ~(i = 1..N)~, ~10^5 < N \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

3
4 5 6

OUTPUT

YES
NO
NO

Cho hai dãy số nguyên dương ~a_1, a_2, ..., a_N~ và ~b_1, b_2, ..., b_M~.

Yêu cầu

Hỏi có bao nhiêu cặp số ~(i, j)~ ~(1 \le i \le N,\ 1 \le j \le M)~ sao cho ~a_i = b_j~?

Dữ liệu đầu vào

Gồm ba dòng:

• Dòng 1 ghi hai số nguyên dương ~N,\ M~ ~(1 \le N, M \le 10^7)~;
• Dòng 2 ghi ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ ~(a_i \le 10^6,\ i = 1..N)~;
• Dòng 3 ghi ~M~ số nguyên dương ~b_1, b_2, ..., b_M~ ~(b_j \le 10^6,\ j = 1..M)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc dữ liệu

• Có 62,5% test tương ứng 62,5% điểm với ~N, M \le 10^3~;
• Có 25% test tương ứng 25% điểm với ~10^3 < N, M \le 10^5~;
• Có 12,5% test tương ứng 12,5% điểm với ~10^5 < N, M \le 10^7~.

Ví dụ

Ví dụ 1

INPUT

3 4
1 5 0
0 1 7 5

OUTPUT

3

Bố của hai anh em Bắc và Giang vừa có một chuyến đi công tác về. Ông đã chuẩn bị ~N~ gói quà, các gói quà được đánh số từ ~1~ đến ~N~, gói quà thứ ~i~ có giá trị là ~a_i~. Ông sẽ chia hết số quà cho hai anh em Bắc và Giang vì hai anh em đã động viên ông trong suốt quãng thời gian ông đi công tác. Ông chia quả thành hai phần với tổng giá trị của từng phần là ~S_1~ và ~S_2~, độ chệnh lệch giữa hai phần quà là ~|S_1 - S_2|~ và mỗi anh em sẽ nhận một trong hai phần quà đó.

Trước khi chia quà cho các con, ông đã ghi lần lượt các số ~1~ và ~2~ trên các gói quà, lúc chia nếu gói quà ghi số ~1~ thì ông chia cho Bắc, gói quà ghi số ~2~ ông chia cho Giang. Như vậy, độ chênh lệch của hai phần quả đã được xác định. Ông đã suy nghĩ và muốn chia quà cho các con để sao cho độ chênh lệch giữa hai phần quả là nhỏ nhất.

Yêu cầu

Hãy giúp bố của Bắc và Giang chia quà cho hai anh em sao cho độ chênh lệch giữa hai phần quả là nhỏ nhất.

Dữ liệu đầu vào

Gồm ba dòng:

• Dòng 1 ghi số nguyên dương ~N~ ~(1 \le N \le 100)~;
• Dòng 2 ghi ~N~ số ~a_1, a_2, ..., a_N~ ~(1 \le a_i \le 10000,\ i = 1..N)~;
• Dòng 3 ghi dãy gồm ~N~ số (số ~1~ hoặc số ~2~) tương ứng với cách chia quà ban đầu của bố Bắc và Giang (số thứ ~i~ bằng ~1~ thì ông chia gói quà thứ ~i~ cho Bắc, số thứ ~i~ bằng ~2~ thì ông chia gói quà thứ ~i~ cho Giang).

Dữ liệu đầu ra

Gồm hai dòng:

• Dòng 1 ghi độ chênh lệch của cách chia ban đầu;
• Dòng 2 ghi độ chênh lệch nhỏ nhất tìm được.

Ràng buộc dữ liệu

• Có 75% test tương ứng 75% điểm với ~1 < N \le 20~;
• Có 25% test tương ứng 25% điểm với ~20 < N \le 100~.

Ví dụ

Ví dụ 1

INPUT

5
10 15 14 8 10
1 2 1 2 1

OUTPUT

11
1