Cho một số nguyên dương N. Hãy đếm xem có bao nhiêu bộ số (A,B) thoả mãn điều kiện sau:

• 1 ≤ A ≤ B ≤ N;

• A * B là số chẵn.

Dữ liệu: Vào từ thiết bị vào chuẩn gồm một dòng chứa một số nguyên dương N (N ≤ 10^9).

Kết quả: Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên duy nhất là số bộ số thoả mãn.

Ví dụ:

Input:

5

Output:

9

Giải thích: Các bộ số thoả mãn: (1,2), (1, 4), (2, 2), (2,3), (2,4), (2,5), (3,4), (4, 4), (4,5)

Ràng buộc:

• 60% số test tương ứng với 60% số điểm có N ≤ 10^3;

• 20% số test khác tương ứng với 20% số điểm có N ≤ 10^6;

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

Cho một mảng gồm n số nguyên, nhiệm vụ của bạn là đếm số mảng con (dãy con các phần tử liên tiếp) có tổng bằng x.

Đầu vào: Dòng đầu tiên có hai số nguyên n và x: kích thước của mảng và tổng mục tiêu x. Dòng tiếp theo có n số nguyên a1, a2..., an: các phần tử trong mảng

1 <= n <= 2*10^5; -10^9 <= x, a i ≤ 10^9

Đầu ra: In một số nguyên là số lượng mảng con.

Input 01:

5 7
2 4 1 2 7

Output 01:

3

Input 02:

10 5
2 3 0 -1 1 4 1-2 2 7

Output 02:

10

Cho dãy a gồm n số nguyên dương phân biệt a1, a2, ..., an

Một số x được gọi là số thiếu thứ k của dãy a nếu x là số nguyên dương nhỏ thứ k không nằm trong dãy a.

Cho q truy vấn. Ở truy vấn thứ i (1 ≤ i ≤ q) hãy tìm số thiếu thứ k của dãy a.

Input:

• Dòng đầu tiên chứa hai số nguyên dương n, q (n, q ≤ 10^5);

• Dòng thứ hai chứa n số nguyên a1, a2, ..., an (1 ≤ a1 < az <...< an ≤ 10^18);

• q dòng sau, dòng thứ i chứa số nguyên dương ki (ki ≤ 10^18 ,1 ≤ i ≤ q)

Output: In ra q dòng tương ứng với kết quả của q truy vấn.

Input:

4 3
3 5 6 7
2
5
3

Output:

2
9
4

Cho một robot được lập trình di chuyển trên một hàng ngang gồm các ô vuông. Mỗi ô được đặt tên bằng các kí tự theo thứ tự từ 'A' đến 'Z' và được lặp lại vô hạn. Ban đầu robot xuất phát ở ô thứ 1 có tên là 'A' và nhảy đến các ô tiếp theo quy luật: lần 1 nhảy 1 ô, lần 2 nhảy 2 ô, lần 3 nhảy 3 ô, ..., lần N nhảy N ô. Vậy sau N lần nhảy thì robot đang ở ô nào?

Dữ liệu nhập vào:

Gồm một số nguyên dương N là số lần nhảy của robot (N ≤ 10^9).

Kết quả in ra: Một kí tự duy nhất là tên của ô sau N lần robot nhảy.

Ràng buộc:

• Có 60% số test ứng với 60% số điểm của bài thỏả mãn: N ≤ 10^3;

• 20% số test khác ứng với 20% số điểm của bài thoả mãn: N ≤ 10^6;

• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Ví dụ:

Input 01:

1

Output 01:

B

Giải thích: Sau 1 lần nhảy, robot ở ô thứ 2, có tên là kí tự B.

Input 02:

4

Output 02:

K

Giải thích: Sau 4 lần nhảy, robot ở ô thứ 11, có tên là kí tự K.

Input 03:

7

Output 03:

C

Giải thích: Sau 7 lần nhảy, robot ở ô thứ 29, có tên là kí tự C.

Có N ngôi nhà nằm thẳng hàng. Bạn cần tô màu cho mỗi ngôi nhà bằng một trong 3 màu: Đỏ, Xanh lá, Xanh dương. Chi phí để tô nhà i màu Đỏ là R[i], màu Xanh lá là G[i], màu Xanh dương là B[i]. Yêu cầu: Hai ngôi nhà liền kề không được có cùng màu. Hãy tìm chi phí thấp nhất để tô màu tất cả ngôi nhà.

Dữ liệu vào:

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

N dòng tiếp theo: Mỗi dòng chứa 3 số nguyên R[i], G[i], B[i].

Dữ liệu ra:

Chi phí thấp nhất.

Ví dụ:

Input:

3 
14 2 11 
11 14 5 
14 3 10

Output:

10