Chợ nổi là một nét văn hóa lâu đời của Khu vực Đồng bằng sông Cửu Long, cũng là điểm du lịch đẹp mà nhiều đoàn tham quan ghé thăm. Đến với Chợ nổi bạn có thể thuê những chiếc xuồng tham quan mua sắm và thưởng thức các món ăn ngon đậm chất miền Tây. Một đoàn khách tham quan có n người được đánh số thứ tự từ 1 đến n, du khách thứ i có cân nặng là ai. Do hiện tại có nhiều khách du lịch nên đoàn tham quan chỉ thuê được một chiếc xuồng có trọng tải là k và chỉ chở được hai du khách có cân nặng không vượt quá k để đảm bảo an toàn cho du khách. Hướng dẫn viên muốn bố trí cho hai du khách xuống xuồng trước, các du khách còn lại sẽ chờ để xuống xuồng tham quan trong các lượt tiếp theo hoặc có thể tản bộ dọc theo bờ sông để tham quan và thư giãn. Yêu cầu: Hãy cho biết có bao nhiêu cách chọn ra hai du khách bố trí xuống xuồng để tham quan mà vẫn phải bảo đảm an toàn (tổng cân nặng không vượt quá k)

Dữ liệu vào:

• Dòng thứ nhất ghi hai số nguyên dương ~n, k~. (~1 \le n,k \le 10^6~)
• Dòng thứ hai ghi n số nguyên dương ~a_1, a_2,....,a_n~(~1 \le a_i \le 10^6~)

Dữ liệu ra:

• Gồm một dòng ghi một số nguyên dương là số cách chọn ra hai du khách bố trí xuống xuồng để tham quan mà vẫn phải đảm bảo an toàn.

Ví dụ:

Input

5 90
40 45 55 42 52

Output

3

Ràng buộc:

• Có 60% số test tương ứng 60% số điểm n ~n \le 10^3~.
• Có 40% số test tương ứng 40% số điểm ~n \le 10^6~.

Số nguyên tố là số nguyên dương chỉ có duy nhất hai ước là 1 và chính nó. Ví dụ: số 11 là số nguyên tố vì nó chỉ có hai ước là 1 và 11; số 15 không phải số nguyên tố vì nó có 4 ước gồm 1, 3, 5 , 15; số 1 không phải là số nguyên tố vì nó có 1 ước là 1.

Yêu cầu: Cho số nguyên ~N~ (~1 ≤ N ≤ 2.10^5~) và N đoạn số nguyên (~1 ≤ L_i ≤ R_i ≤ 10^7~). Hãy tìm số lượng số nguyên tố thuộc mỗi đoạn

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ~N~.
• ~N~ dòng tiếp theo, dòng thứ i chứa hai số nguyên(ngăn cách nhau bởi một khoảng trắng)

Dữ liệu ra:

-Gồm ~N~ dòng, dòng thứ i ghi một số nguyên là số lượng số nguyên tố thuộc đoạn .

Ví dụ:

Input

2
14 16
11 25

Output

0
5

Ràng buộc:

• Có 40% số test tương ứng 40% số điểm của bài với ~1 \le N \le 10^3; 1 \le L \le R \le 10^3~
• Có 60% số test tương ứng 60% số điểm của bài với ~10^3 < N \le 2.10^5; 1 \le L \le R \le 10^7~.

Cho một dãy gồm ~N~ số nguyên đánh số từ 1 đến N (~A_1, A_2,…, A_N; |a_i| ≤ 10^9~) và được sắp xếp thành một vòng tròn theo chiều kim đồng hồ.

Yêu cầu: Hãy tìm tổng lớn nhất ~K~ số liên tiếp trong vòng tròn trên.

Dữ liệu vào:

• Dòng 1. Ghi 2 số nguyên dương ~N, K~ (~0 < K < N ≤ 10^5~) cách nhau một dấu cách.
• Dòng 2. Chứa ~N~ số nguyên là các phần tử ~A_i~ của dãy, mỗi số có giá trị tuyệt đối không vượt quá ~10^6~, giữa các số cách nhau một dấu cách.

Dữ liệu ra:

• Dòng 1: Ghi số nguyên duy nhất là tổng lớn nhất của ~K~ số liên tiếp nhau tìm được trong vòng tròn số.

Ví dụ

Input

5 3
10 2 3 5 7

Output

22

Ràng buộc:

• 50% số test: ~0 ≤ K< N ≤ 10^4~ ;
• 50% số test: ~10^4 < K < N ≤ 10^5~ ;