Bạn được cho một mảng gồm n số nguyên, và nhiệm vụ của bạn là tìm bốn giá trị (tại bốn vị trí khác nhau) sao cho tổng của chúng bằng x.

Input:

Dòng đầu tiên chứa hai số nguyên n và x — kích thước mảng và tổng cần tìm.

Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ — các giá trị trong mảng.

Output:

In ra bốn số nguyên: chỉ số của bốn phần tử tạo thành tổng x.

Nếu có nhiều đáp án, bạn có thể in ra bất kỳ một đáp án nào.

Nếu không có lời giải, in ra IMPOSSIBLE.

Ràng buộc:

~1 \le n \le 1000~

~1 \le x,a_i \le 10^9~

Ví dụ :

Input:

8 15
3 2 5 8 1 3 2 3

Output:

1 2 4 7

Cho mảng A gồm N số nguyên và một số K. Em được phép chọn một phần tử bất kỳ và lật ngược dấu của nó (nhân với -1). Thao tác này PHẢI được thực hiện đúng K lần (một phần tử có thể bị lật nhiều lần). Hãy tìm tổng lớn nhất của các phần tử trong mảng sau khi lật đủ K lần.

Dữ liệu vào:

Dòng 1: Hai số nguyên N và K (1 <= N <= 10^5; 1 <= K <= 10^4).

Dòng 2: N số nguyên Ai (-100 <= Ai <= 100).

Kết quả ra: Tổng lớn nhất đạt được.

Ví dụ:

Input:

4 1
4 2 3 -1

Output:

10

(Chỉ lật số -1 thành 1. Mảng trở thành 4, 2, 3, 1 -> Tổng 10).

Câu lạc bộ Truyền thông của Khoa Công nghệ Thông tin - Đại học Công nghệ Thông tin và Truyền thông (ICTU) vừa cho ra mắt chuỗi series video giới thiệu về các ngành học cực kỳ hấp dẫn gồm N tập. Các tập phim này được phát sóng theo thứ tự từ 1 đến N, trong đó tập thứ i có thời lượng là Ai giây.

Các bạn sinh viên tại ký túc xá đang mở chiến dịch "Cày view" để ủng hộ kênh của khoa. Tuy nhiên, quy tắc tính view hợp lệ của hệ thống là: Bạn phải xem các tập liên tiếp nhau thì mới được tính là một "chuỗi trải nghiệm". Nếu xem nhảy cóc, hệ thống sẽ không ghi nhận đóng góp cho chiến dịch.

Mỗi sinh viên (tương ứng với một truy vấn Q) có một quỹ thời gian rảnh T giây khác nhau (do lịch học quân sự hoặc lịch thực hành tại không giống nhau). Các bạn muốn biết với T giây đó, mình có thể xem được tối đa bao nhiêu tập phim liên tiếp.

Nhiệm vụ

Hãy viết chương trình giúp các "Chiến thần cày view" Khoa Công nghệ Thôn tin tính toán số lượng tập phim tối đa có thể xem được ứng với mỗi khoảng thời gian rảnh T.

Dữ liệu vào (Input):

• Dòng 1: Số nguyên N (1 <= N <= 10^4) – Tổng số tập phim của series.

• Dòng 2: N số nguyên A1, A2, ..., An (1 <= Ai <= 10^4) – Thời lượng từng tập.

• Dòng 3: Số nguyên Q (1 <= Q <= 10^4) – Số lượng sinh viên tham gia cày view.

• Q dòng tiếp theo: Mỗi dòng là một số nguyên T (1 <= T <= 10^8) – Thời gian rảnh của sinh viên đó.

Kết quả ra (Output):

• Với mỗi sinh viên, in ra số lượng tập phim liên tiếp nhiều nhất mà họ có thể xem.

Ví dụ:

Input:

5
4 2 3 1 5
3
7
10
15

Output:

3
4
5

• T=7: Có thể xem 3 tập liên tiếp {2, 3, 1} tổng 6s <= 7s.

• T=10: Có thể xem 4 tập liên tiếp {4, 2, 3, 1} tổng 10s <= 10s.

• T=15: Có thể xem cả 5 tập (tổng là 15s).

Cho mảng A gồm N số nguyên không âm. Bạn đang đứng ở vị trí đầu tiên (index 1). Giá trị A[i] cho biết bạn có thể nhảy tối đa A[i] bước từ vị trí i. Hãy tìm số bước nhảy ít nhất để đến được vị trí cuối cùng (index N).

Dữ liệu vào:

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

Dòng 2: N số nguyên A[i].

Dữ liệu ra:

Số bước nhảy ít nhất.

Ví dụ:

Input:

5 
2 3 1 1 4

Output:

2