Nhân dịp Giáng Sinh Tom quyết định mua tặng 2 người bạn thân của mình mỗi người một món quà. Trong cửa hàng lưu niệm có n mặt hàng khác nhau, mặt hàng thứ i có giá ~a_i~. Với tổng số tiền trong túi là ~x~, Tom quyết định sẽ mua 2 món quà khác nhau có tổng giá trị lớn nhất và tất nhiên không vượt quá khả năng chi trả của mình.

Yêu cầu: Hãy xác định tổng số tiền Tom cần chi trả.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~x~(~2 ≤ n ≤ 10^5,2 ≤ x ≤ 10^9~)
• Dòng thứ 2 chứa ~n~ số nguyên ~a_1,a_2,...,a_n~(~1 ≤a_i≤ 10^9,i=1÷n~).

Kết quả:

• Một số nguyên là số tiền cần chi trả.

Ràng buộc

• Có 50% số test thỏa mãn điều kiện ~n≤1000~
• Có 50% số test còn lại không có ràng buộc gì thêm

Ví dụ:

Input

6 18 
5 3 10 2 4 9 

Output

15 

Cho hai số nguyên dương n,m và hai dãy số nguyên ~a_1,a_2,…,a_n~; ~b_1,b_2,…b_m~.

Yêu cầu: Hãy cho biết mỗi số ~b_j~(~j=1...m~) xuất hiện bao nhiêu lần trong dãy ~a_1,a_2,…,a_n~.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên ~n~,~m~.

• Dòng thứ hai ghi lần lượt các số ~a_1,a_2,…,a_n~.

• Dòng thứ ba ghi lần lượt các số ~b_1,b_2,…,b_m~

Kết quả

Ghi m số trong đó số thứ ~j~(~j=1..m~) là số lượng của giá trị bj trong dãy ~a_1,a_2,…,a_n~;

Ràng buộc

~1 ≤ n,m ≤ 10^5~; ~|a_i| ≤ 10^9~;~(i=1...n)~; ~|b_j|≤10^9;(j=1...m)~

Ví dụ:

Input

5 3
1 2 2 5 3
2 6 1 

Output

2 0 1 

Cho số nguyên dương ~𝑛~ và dãy số nguyên dương ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~.

Yêu cầu: Hãy cho biết có bao nhiêu dãy con gồm các phần tử liên tiếp nhau có tổng đúng bằng ~𝑘~.

Dữ liệu vào:

• Dòng đầu ghi hai số nguyên dương ~𝑛~, ~𝑘~ (~1 ≤ 𝑛 ≤ 10^6; 𝑘 ≤ 10^9~)
• Dòng thứ hai ghi lần lượt các số ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~(~1 ≤ 𝑎_𝑖 ≤ 10^6~)

Kết quả:

• Ghi một số nguyên cho biết kết quả bài toán.

Ví dụ:

Input

6 8
4 3 5 2 1 8 

Output

3

Ràng buộc:

• Có 30% số test tương ứng với 30% số điểm có ~𝑛 ≤ 200~;
• Có 30% số test khác tương ứng 30% số điểm có ~𝑛 ≤ 2000~;
• Có 20% số test khác tương ứng 20% số điểm có ~𝑛 ≤ 2 × 10^5~;
• Có 20% số test còn lại tương ứng 20% số điểm không có ràng buộc gì thêm