Cho hai số nguyên dương l và r. Hãy tính tổng tất cả các số nguyên chẵn trong đoạn [l, r].

Yêu cầu: Bạn hãy giúp Nam tính tổng tất cả các số nguyên chẵn trong đoạn [l, r].

Dữ liệu vào: Đọc dữ liệu từ bàn phím một dòng duy nhất chứa hai số nguyên dương l và r (1 ≤ l ≤ r ≤ ~2.10^9~), mỗi số cách nhau 1 khoảng trắng.

Dữ liệu ra: Xuất ra màn hình một số nguyên là tổng tính được.

Ví dụ 1

Dữ liệu vào

2 9

Dữ liệu ra

20

Ví dụ 2

Dữ liệu vào

3 3

Dữ liệu ra

0

Giải thích

Ví dụ 1, đoạn [2, 9] gồm các số nguyên: 2; 3; 4; 5; 6; 7; 8; 9, trong đó các số chẵn là: 2; 4; 6; 8, tổng là 2 + 4 + 6 + 8 = 20.

Ví dụ 2, đoạn [3, 3] không có số nguyên chẵn nên tổng bằng 0.

Giới hạn

• 90% số điểm tương ứng với số test có 1 ≤ r ≤ 10^4;
• 10% số điểm tương ứng với số test còn lại không ràng buộc gì thêm.

Công ty ABC đã trồng một số cây xanh trên con đường MK để trang trí, mỗi loại cây được kí hiệu bằng một kí tự chữ cái tiếng Anh in thường. Dãy cây xanh liên tiếp đã trồng được mô tả thành một xâu kí tự S.

Ví dụ, S = "fabacb", có 2 cây loại a, 2 cây loại b, 1 cây loại c và 1 cây loại f.

Yêu cầu: Đếm số lượng từng loại cây xanh đã trồng.

Dữ liệu vào: Đọc dữ liệu từ bàn phím một dòng duy nhất chứa xâu S, kí hiệu |S| là độ dài xâu (1 ≤ |S| ≤ ~10^3~).

Dữ liệu ra: Xuất ra màn hình một số dòng, mỗi dòng gồm ba phần: phần thứ nhất một kí tự chữ cái kí hiệu cho mỗi loại cây, phần thứ hai dấu hai chấm, phần thứ ba số lượng cây tương ứng từng loại và giữa các phần không có khoảng trắng. Các loại cây được xuất ra theo thứ tự từ điển bảng chữ cái.

Ví dụ

Dữ liệu vào

fabacb

Dữ liệu ra

a:2
b:2
c:1
f:1

Trong buổi học chuyên đề về Số học, thầy giáo đưa ra khái niệm số đặc biệt: một số nguyên dương x gọi là số đặc biệt nếu tổng các ước nguyên dương của x chia hết cho 3.

Ví dụ: 15 là một số đặc biệt vì tổng các ước của 15 là 1 + 3 + 5 + 15 = 24 chia hết cho 3; 12 không phải số đặc biệt vì tổng các ước của 12 là 1 + 2 + 3 + 4 + 6 + 12 = 28 không chia hết cho 3.

Cho trước một dãy số có n số nguyên dương ~a_1, a_2, ..., a_n~, thầy đưa ra q câu hỏi có dạng l, r, k với ý nghĩa số lượng số đặc biệt trong dãy con ~a_l, a_{l+1}, ..., a_r~ (1 ≤ l ≤ r ≤ n) có lớn hơn hoặc bằng k hay không, nếu có thì trả lời "YES", ngược lại trả lời "NO". Thầy yêu cầu cả lớp lập trình trả lời q câu hỏi trên.

Yêu cầu: Hãy viết chương trình trả lời q câu hỏi của thầy giáo.

Dữ liệu vào: Đọc dữ liệu từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất chứa 2 số nguyên dương n, q (2 ≤ n, q ≤ ~10^5~);
• Dòng thứ hai gồm n số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i ≤ 10^5~, 1 ≤ i ≤ n);
• q dòng tiếp theo mỗi dòng gồm 3 số nguyên dương l, r, k (1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ ~10^5~); Các số trên một dòng cách nhau 1 khoảng trắng.

Dữ liệu ra: Xuất ra màn hình gồm q dòng trả lời tương ứng cho q câu hỏi của thầy giáo.

Ví dụ

Dữ liệu vào

5 3
19 8 3 17 18
2 5 3
4 4 1
3 3 1

Dữ liệu ra

YES
YES
NO

Giải thích

Với trường hợp l = 2, r = 5, dãy con {8; 3; 17; 18}, tổng các ước của 8 là 1 + 2 + 4 + 8 = 15, tổng các ước của 3 là 1 + 3 = 4, tổng các ước của 17 là 1 + 17 = 18, tổng các ước của 18 là 1 + 2 + 3 + 6 + 9 + 18 = 39, có 3 số đặc biệt là 8; 17; 18 vì mỗi số đều có tổng các ước chia hết cho 3, k = 3 nên kết quả là "YES".

Giới hạn

• 50% số điểm tương ứng với số test có: n, q ≤ 10^3;
• 50% số điểm tương ứng với số test còn lại không ràng buộc gì thêm.

Bác Nam sở hữu một khu vườn có trồng n cây, cây thứ i có độ tươi tốt hiện tại ~a_i~ và khả năng tăng trưởng ~b_i~. Hôm nay, bác Nam dự định sử dụng tổng cộng l lít nước để tưới cho các cây trong vườn. Với mỗi lít nước tưới vào cây thứ i, độ tươi tốt của cây sẽ tăng thêm ~b_i~. Ngoài ra, số lít nước tưới vào mỗi cây phải là số nguyên dương. Bác Nam đánh giá vẻ đẹp của khu vườn là độ tươi tốt nhỏ nhất trong số cây trong vườn sau khi đã tưới nước.

Yêu cầu: Hãy giúp bác Nam tìm cách tưới nước sao cho vẻ đẹp của khu vườn là lớn nhất có thể.

Dữ liệu vào: Đọc dữ liệu từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất chứa hai số nguyên n, l (1 ≤ n ≤ ~10^5~, 1 ≤ l ≤ ~10^9~) lần lượt là số lượng cây trong vườn và số lít nước dùng để tưới cây;
• n dòng tiếp theo, dòng thứ i gồm hai số nguyên ~a_i~ và ~b_i~ (~1 ≤ a_i, b_i ≤ 10^4~, 1 ≤ i ≤ n); Các số trên một dòng cách nhau 1 khoảng trắng.

Dữ liệu ra: Xuất ra màn hình vẻ đẹp lớn nhất có thể của khu vườn với cách tưới cây tối ưu.

Ví dụ 1

Dữ liệu vào

2 5
3 2
100 5

Dữ liệu ra

13

Ví dụ 2

Dữ liệu vào

3 5
1 5
6 2
3 3

Dữ liệu ra

8

Giải thích

• Ví dụ 1, tưới 5 lít nước vào cây thứ nhất, cây thứ hai không tưới. Khi đó, độ tươi tốt của các cây lần lượt là {13; 100} và vẻ đẹp của khu vườn là 13.
• Ví dụ 2, tưới 2 lít nước vào cây thứ nhất, 1 lít nước vào cây thứ hai và 2 lít nước vào cây thứ ba. Khi đó, độ tươi tốt của các cây lần lượt là {11; 8; 9} và vẻ đẹp của khu vườn là 8.

Giới hạn

• 30% số điểm tương ứng với số test có: n, l ≤ ~10^3~;
• 30% số điểm tương ứng với số test có: l ≤ ~10^5~;
• 40% số điểm tương ứng với số test còn lại không ràng buộc gì thêm.

Cho trước số nguyên dương n và dãy số nguyên ~a_1, a_2, ..., a_n~. Một dãy con liên tiếp ~a_l, a_{l+1}, ..., a_r~ (1 ≤ l ≤ r ≤ n) được gọi là dãy số đẹp nếu mỗi phần tử trong dãy đều có số lần xuất hiện không vượt quá 2.

Ví dụ: {1; 5; 2; 4; 3}, {6; 10; 10; 6} và {9} là các dãy số đẹp; còn các dãy {3; 3; 4; 4; 4}, {7; 7; 8; 7} và {100; 100; 100} không phải là dãy số đẹp vì mỗi dãy đều có ít nhất một phần tử có số lần xuất hiện lớn hơn 2.

Yêu cầu: Hãy đếm số lượng cặp chỉ số (l, r) (1 ≤ l ≤ r ≤ n) sao cho dãy con ~a_l, a_{l+1}, ..., a_r~ là dãy số đẹp.

Dữ liệu vào: Đọc dữ liệu từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất chứa số nguyên n (1 ≤ n ≤ ~5.10^5~), số lượng phần tử của dãy;
• Dòng thứ hai gồm n số nguyên ~a_1, a_2, ..., a_n~ (~1 ≤ a_i ≤ 5.10^5~, 1 ≤ i ≤ n) lần lượt là các giá trị của dãy, mỗi số cách nhau 1 khoảng trắng.

Dữ liệu ra: Xuất ra màn hình một số nguyên duy nhất là số lượng cặp chỉ số (l, r) thỏa mãn yêu cầu đề bài.

Ví dụ

Dữ liệu vào

4
1 2 1 1

Dữ liệu ra

9

Giải thích

Có 9 cặp chỉ số (l, r) thỏa mãn yêu cầu đề bài:

1. l = 1, r = 1 dãy {1};
2. l = 1, r = 2 dãy {1; 2};
3. l = 1, r = 3 dãy {1; 2; 1};
4. l = 2, r = 2 dãy {2};
5. l = 2, r = 3 dãy {2; 1};
6. l = 2, r = 4 dãy {2; 1; 1};
7. l = 3, r = 3 dãy {1};
8. l = 3, r = 4 dãy {1; 1};
9. l = 4, r = 4 dãy {1}.

Giới hạn

• 20% số điểm tương ứng với số test có: n ≤ 50, ai ≤ 50, 1 ≤ i ≤ n;
• 15% số điểm tương ứng với số test có: n ≤ 500, ai ≤ 500, 1 ≤ i ≤ n;
• 15% số điểm tương ứng với số test có: n ≤ 5000, ai ≤ 5000, 1 ≤ i ≤ n;
• 50% số điểm tương ứng với số test còn lại không ràng buộc gì thêm.