Cho một hình chữ nhật có chu vi và độ dài một cạnh.

Yêu cầu: Hãy tính diện tích hình chữ nhật.

Input

• Gồm hai số nguyên dương ~cv~ và ~a~ (~0 < a < cv \le 10^9~). Với ~cv~ là số chẵn.

Output

• Ghi ra một số nguyên là diện tích hình chữ nhật tìm được.

Sample Input 1

12 3

Sample Output 1

9

Sample Input 2

10 3

Sample Output 2

6

Trong giờ Toán hôm nay, cả lớp được cô giáo dạy về số nguyên tố. Số nguyên tố là số có 2 ước phân biệt là 1 và chính nó.

Để kiểm tra kiến thức đã học, cô giáo đưa ra thử thách cho cả lớp như sau: Ước số song tố của ~N~ là ~d~ nếu:

• ~d~ là ước của ~N~ và ~d~ là số nguyên tố.
• ~\frac{N}{d}~ cũng là số nguyên tố.

Yêu cầu: Nhiệm vụ của em là xác định số lượng ước số song tố của ~N~.

Input

• Gồm số nguyên dương ~N~ (~1 \le N \le 10^{12}~).

Output

• Ghi ra số nguyên duy nhất là số lượng ước số song tố của ~N~.

Sample Input 1

15

Sample Output 1

2

Sample Input 2

49

Sample Output 2

1

Sample Input 3

10

Sample Output 3

2

Giải thích:

• Với ~N = 15~: các ước số song tố là 3 và 5.
• Với ~N = 49~: chỉ có 7 là nguyên tố và ~\frac{49}{7} = 7~ cũng nguyên tố.
• Với ~N = 10~: các ước số song tố là 2 và 5.

Subtasks

Sau khi đạt kết quả cao tại kỳ thi học sinh giỏi THCS cấp tỉnh, bố An có ~N~ phần thưởng dành cho An, phần thưởng thứ ~i~ có giá trị ~A_i~, bố đặt các phần thưởng theo thứ tự giá trị không giảm để An tự chọn các phần thưởng tùy ý, nhưng với điều kiện giá trị chênh lệch giữa 2 phần thưởng lớn nhất và nhỏ nhất không vượt quá ~K~.

Yêu cầu: In ra một số nguyên duy nhất là số lượng phần thưởng tối đa mà An có thể nhận.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~N~ và ~K~ (~N \le 10^7~; ~K \le 10^9~).
• Dòng thứ 2 gồm số ~N~ số nguyên ~A_i~ là giá trị các phần thưởng (~A_i \le 10^9~).

Output

• In ra một số nguyên duy nhất là số lượng phần thưởng tối đa mà An có thể nhận.

Sample Input 1

6 6
1 2 5 7 9 10

Sample Output 1

4

Giải thích:

• An có thể nhận 4 phần thưởng có giá trị là 1 2 5 7 là nhiều nhất có thể.

Subtasks

Trong giờ học Tiếng Anh, Linh nhận thấy có những từ vựng mà nếu lấy 1 phần thì đó là một xâu đối xứng rất đẹp (xâu đối xứng là xâu mà khi viết từ phải sang trái và trái sang phải là như nhau), ví dụ như từ bub ble, h ere, kook y. Linh nghĩ ra một bài tập học muốn thử thách các bạn như sau: Cho một dòng chỉ gồm các ký tự Tiếng Anh in thường ('a'.. 'z') và yêu cầu kiểm tra các đoạn bắt đầu từ vị trí ~L~ và kết thúc tại vị trí ~R~ có phải xâu đối xứng hay không?

Yêu cầu: In ra ~Q~ dòng, là kết quả tương ứng từng truy vấn, nếu xâu đối xứng in ra YES, nếu không in ra NO.

Input

• Dòng đầu tiên gồm xâu ~S~ có độ dài ~|S| \le 10000~.
• Dòng thứ 2 là số nguyên dương ~Q~ (~1 \le Q \le 10^6~).
• ~Q~ dòng tiếp theo mỗi dòng gồm 2 số ~L, R~ (~L, R \le |S|~) là các truy vấn.

Output

• In ra ~Q~ dòng, là kết quả tương ứng từng truy vấn, nếu xâu đối xứng in ra YES, nếu không in ra NO.

Sample Input 1

abcbd
2
1 3
2 4

Sample Output 1

NO
YES

Giải thích:

• Với truy vấn 1 3, xâu abc không đối xứng.
• Với truy vấn 2 4, xâu bcb đối xứng.

Subtasks

Quá trình phát triển công nghiệp hóa - hiện đại hóa khiến tốc độ đô thị hóa ngày càng nhanh, nhưng ở nhiều miền quê Việt Nam vẫn tồn tại và lưu giữ những nét yên bình, mộc mạc. Nơi ấy, cuộc sống con người chầm chậm trôi như thể bỏ qua sự hối hả nơi phồn hoa đô thị ngoài kia. Buổi trưa, giữa nắng hè oi ả, đám trẻ lại hò nhau trốn bố mẹ vui đùa dưới những bụi tre già: đá bóng, bắn bi, ô ăn quan, ..., những trò chơi dân gian quen thuộc được các bạn nhỏ tổ chức, tham gia.

Hôm nay An và Linh tổ chức trò chơi mới. Để các bạn khác hiểu và tham gia trò chơi, An và Linh làm mẫu để các bạn khác xem và sau đó tham gia.

Trò chơi gồm ~N~ thẻ đánh số từ 1 tới ~N~, thẻ thứ ~i~ có giá trị ~a_i~. Trò chơi này quy ước rằng trong hai người mỗi người được chọn đúng ~K~ thẻ có chỉ số liên tiếp trong dãy (~K \le \frac{N}{3}~) và không được cùng chọn bất cứ thẻ nào.

Hôm nay làm mẫu cho các bạn nên An sẽ chọn trước Linh chọn sau. Vì tính hiếu thắng, An muốn Linh nhận được các thẻ có tổng giá trị nhỏ nhất có thể.

Yêu cầu: Tính tổng giá trị lớn nhất Linh có thể đạt được sau khi An chọn.

Input

• Dòng 1: Chứa 2 số nguyên ~N, K~ (~3 \le N \le 10^6; 1 \le K \le \frac{N}{3}~).
• Dòng 2 chứa ~N~ số nguyên ~a_1, a_2, ..., a_N~ (~ \forall i: 1 \le a_i \le 10^6~).

Lưu ý: Bộ test đảm bảo luôn tồn tại đáp án.

Output

• Ghi ra một số nguyên duy nhất là kết quả tìm được.

Sample Input 1

9 3
3 4 3 5 6 2 4 3 2

Sample Output 1

9

Sample Input 2

10 2
1 2 3 4 5 6 7 8 9 10

Sample Output 2

13

Giải thích:

• Ví dụ 1: An chọn các thẻ thứ 3, 4, 5, khi đó Linh chỉ có thể chọn các thẻ với tổng giá trị tối đa bằng 9 (chọn các thẻ thứ 6, 7, 8 hoặc 7, 8, 9).
• Ví dụ 2: An chọn các thẻ thứ 8 và thứ 9, khi đó Linh chỉ có thể chọn các thẻ với tổng giá trị tối đa bằng 13 (chọn các thẻ thứ 6 và thứ 7).

Subtasks