Hợp tác xã tại Thái Nguyên vừa thu hoạch được N gram chè xanh hảo hạng. Họ có 2 loại hộp đóng gói: Hộp nhỏ chứa đúng A gram, và Hộp lớn chứa đúng B gram. Câu hỏi đặt ra là: Có thể chia N gram chè này vào các hộp sao cho tất cả các hộp đều vừa khít (không hộp nào vơi, không thừa gram chè nào ngoài hộp) hay không?

Input: Dòng duy nhất chứa 3 số nguyên N, A, B (1 <= N, A, B <= 10^6).

Output: In ra YES nếu có cách đóng gói, ngược lại in NO.

Ví dụ:

Input:

17 3 5

Output:

YES

(Giải thích: Dùng 4 hộp 3 gram và 1 hộp 5 gram. 4 x 3 + 1 x 5 = 17).

Một đoạn mã hợp lệ được định nghĩa là một xâu ký tự có độ dài bằng đúng K, và tất cả K ký tự trong đó đều phải đôi một khác nhau. Cho một xâu S dài, hãy đếm xem có bao nhiêu đoạn mã hợp lệ nằm liên tiếp bên trong S. (Hai đoạn mã có nội dung giống nhau nhưng xuất phát từ 2 vị trí khác nhau trong S vẫn được tính là 2 đoạn khác nhau).

Input:

Dòng 1: Xâu S (Chỉ gồm chữ cái in thường, độ dài <= 10^5).

Dòng 2: Số nguyên K (1 <= K <= 26).

Output: Số lượng đoạn mã hợp lệ.

Ví dụ:

Input:

abacbad
3

Output:

4

(Giải thích: Các đoạn con dài 3 là: aba (loại), bac (nhận), acb (nhận), cba (nhận), bad (nhận). Chờ đã, "bac", "acb", "cba", "bad" đều có 3 ký tự khác nhau. Tổng cộng là 4 đoạn. Lỗi ví dụ, output phải là 4).

Kế hoạch tài chính là một mảng gồm N số nguyên dương. Kế toán cần chia mảng này thành đúng K đoạn liên tiếp nhau. Chi phí của một đoạn là tổng các phần tử trong đoạn đó. Rủi ro của cách chia là chi phí của đoạn có chi phí lớn nhất. Hãy dùng thuật toán chia mảng sao cho rủi ro đạt mức thấp nhất có thể.

Input:

Dòng 1: N, K (1 <= K <= N <= 10^5).

Dòng 2: N số nguyên dương Ai (1 <= Ai <= 10^4).

Output: Mức rủi ro thấp nhất.

Ví dụ:

Input:

5 2
7 2 5 10 8

Output:

18

(Giải thích: Chia thành [7,2,5] tổng 14 và [10,8] tổng 18. Rủi ro là 18).

Hệ thống bảo mật yêu cầu mã hóa Q tín hiệu. Tín hiệu thứ i mang một giá trị là số nguyên Ni. Khóa mã hóa của tín hiệu này chính là "ước số nguyên tố nhỏ nhất" của Ni. Hãy viết chương trình tìm nhanh khóa mã hóa cho tất cả Q tín hiệu. (Gợi ý: Sử dụng Sàng nguyên tố để tối ưu thời gian trả lời truy vấn).

Input:

Dòng 1: Số nguyên Q (1 <= Q <= 10^5).

Q dòng tiếp theo: Mỗi dòng chứa một số nguyên dương Ni (2 <= Ni <= 10^6).

Output: In ra Q dòng, mỗi dòng là ước nguyên tố nhỏ nhất của N_i tương ứng.

Ví dụ:

Input:

3
15
2
35

Output:

3
2
5

Một xâu ký tự được gọi là "đạt chuẩn" nếu nó chứa chính xác K nguyên âm (các ký tự a, e, i, o, u). Cho một xâu S chỉ gồm các chữ cái in thường. Bạn hãy đếm xem trong S có tất cả bao nhiêu xâu con liên tiếp đạt chuẩn.

Input:

Dòng 1: Số nguyên K (0 <= K <= 10^5).

Dòng 2: Xâu S (Độ dài <= 10^5).

Output: Số lượng xâu con liên tiếp chứa đúng K nguyên âm.

Ví dụ:

Input:

1
abaca

Output:

8