Cho bốn số nguyên dương ~a, b, x, y~ ~(2 \le a, b \le 10^9;\ 2 \le x \le y \le 10^{12})~.

Yêu cầu

Đếm số lượng số nguyên thuộc đoạn ~[x, y]~ chia hết cho ~a~ nhưng không chia hết cho ~b~.

Dữ liệu đầu vào

Gồm một dòng chứa bốn số nguyên dương ~a, b, x, y~. Các số cách nhau bởi một khoảng trắng.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số lượng số thỏa mãn yêu cầu bài toán.

Ràng buộc dữ liệu

• 30% số test ứng với 30% số điểm có ~2 \le x, y \le 10^6~.
• 40% số test ứng với 40% số điểm có ~10^6 < x, y \le 10^9~.
• 30% số test ứng với 30% số điểm có ~10^9 < x, y \le 10^{12}~.

Ví dụ

Ví dụ 1

INPUT

4 10 24 44

OUTPUT

5

Giải thích: Trong đoạn ~[24, 44]~ có ~5~ số nguyên thỏa mãn điều kiện chia hết cho ~4~ nhưng không chia hết cho ~10~ là: ~24, 28, 32, 36, 44~.

Ví dụ 2

INPUT

8 4 14 20

OUTPUT

0

Giải thích: Trong đoạn ~[14, 20]~ không có số nguyên dương nào thỏa mãn điều kiện chia hết cho 8 nhưng không chia hết cho ~4~.

Cho dãy số gồm ~n~ số nguyên ~a_1, a_2, a_3, ..., a_n~ và một số nguyên dương ~k~. Số nguyên ~a_i, a_j~ là số nguyên lần lượt ở các vị trí thứ ~i~ và thứ ~j~.

Yêu cầu

Hãy cho biết có bao nhiêu cách chọn các cặp số ~i~ và ~j~ thỏa mãn: ~i < j~ và ~a_i + a_j~ chia hết cho ~k~.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên gồm hai số nguyên dương ~n, k~ ~(1 < n, k \le 10^6)~, mỗi số cách nhau một khoảng trắng.
• Dòng thứ hai chứa dãy số nguyên ~a_1, a_2, a_3, ..., a_n~ ~(|a_i| \le 10^9;\ 1 \le i \le n)~, mỗi số cách nhau một khoảng trắng.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số cách chọn thỏa mãn yêu cầu bài toán.

Ràng buộc dữ liệu

• 60% số test ứng với 60% số điểm có ~n \le 10^3~.
• 40% số test ứng với 40% số điểm không giới hạn gì thêm.

Ví dụ

Ví dụ 1

INPUT

4 6
2 4 8 -8

OUTPUT

4

Giải thích: Có ~4~ cặp ~(i, j)~ thỏa mãn là: ~(1, 2), (1, 4), (2, 3), (3, 4)~.

Cho xâu ~S~ chỉ có các kí tự chữ cái và kí tự chữ số có độ dài không vượt quá ~10^6~ kí tự. Các số trong xâu ~S~ là một dãy các kí tự chữ số liên tiếp được phân tách bởi các kí tự chữ cái, xâu ~S~ bắt đầu bằng một kí tự chữ cái và kết thúc cũng bằng một kí tự chữ cái. Khi thực hiện lấy ra các số trong ~S~, ta thu được một dãy số ~A~ gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(0 < a_i \le 10^6)~.

Hai số nguyên dương ~x, y~ được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng ~1~. Một đoạn con liên tiếp trong dãy ~A~ được gọi là nguyên tố cùng nhau nếu mọi cặp số trong đoạn đó là nguyên tố cùng nhau.

Yêu cầu

Tìm đoạn con liên tiếp nguyên tố cùng nhau dài nhất.

Dữ liệu đầu vào

Gồm một dòng duy nhất ghi xâu ~S~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là độ dài của đoạn con liên tiếp nguyên tố cùng nhau dài nhất của dãy ~A~.

Ràng buộc dữ liệu

• 30% số test ứng với 30% số điểm có: ~n \le 20~.
• 40% số test ứng với 40% số điểm có: các số nguyên xuất hiện trong xâu ~S~ đều là số nguyên tố.
• 30% số test ứng với 30% số điểm không có ràng buộc thêm.

Ví dụ

Ví dụ 1

INPUT

a14a5ac7a6bb

OUTPUT

3

Giải thích: Thực hiện tách các số trong xâu ~S~ ta thu được dãy ~A~ gồm các số ~14, 5, 7, 6~. Đoạn con liên tiếp nguyên tố cùng nhau dài nhất là đoạn: ~5, 7, 6~ có độ dài bằng ~3~.

Ví dụ 2

INPUT

ac5b2c3a7b

OUTPUT

4

Giải thích: Dãy thu được gồm các số ~5, 2, 3, 7~ đều là các số nguyên tố phân biệt nên là nguyên tố cùng nhau, có độ dài bằng ~4~.

Cho dãy gồm ~n~ số tự nhiên ~a_1, a_2, a_3, ..., a_n~, các số ~a_i~ ~(1 \le i \le n)~ không quá ~m~ và có giá trị đôi một khác nhau, trong đó có đúng một số có giá trị bằng ~0~.

Yêu cầu

Thay thế số ~0~ thành một giá trị bất kì không được trùng với các giá trị đã có để nhận được một dãy con (các phần tử không nhất thiết nằm liên tiếp) có các giá trị liên tiếp dài nhất có thể.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu ghi hai số nguyên ~m, n~ ~(1 \le n < m \le 10^6)~.
• Dòng thứ hai chứa ~n~ số tự nhiên đôi một khác nhau không lớn hơn ~m~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là độ dài của dãy con có giá trị liên tiếp dài nhất có thể đạt được sau khi thay đổi giá trị của số ~0~.

Ràng buộc dữ liệu

• 40% số test ứng với 40% số điểm có: ~1 \le n \le 100~.
• 30% số test ứng với 30% số điểm có: ~100 < n \le 1000~.
• 30% số test ứng với 30% số điểm có: ~1000 < n \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

8 5
8 2 0 5 7

OUTPUT

4

Giải thích: Ta có thể gán giá trị ~6~ cho phần tử có giá trị ~0~, khi đó dãy trở thành ~8, 2, 6, 5, 7~. Dễ thấy dãy con ~8, 6, 5, 7~ có các phần tử có giá trị liên tiếp nhau là ~5, 6, 7, 8~ và có độ dài ~4~ là dài nhất.