연속해서 담는 급식 반찬

문제

학교 급식실에서는 새 반찬의 선호도를 조사하기 위해 배식대에 놓인 반찬 통 일부를 연속해서 골라 시식 코너로 옮기려 한다. 반찬 통은 왼쪽부터 오른쪽까지 한 줄로 놓여 있으며, 각 통에는 1번부터 N번까지 번호가 붙어 있다. i번 통을 옮기는 데 필요한 작업량은 양의 정수 A_i이다. 작업량은 통의 크기와 운반 거리를 함께 고려하여 미리 정한 값이다. 시식 코너 담당자는 한 번의 준비 작업에서 사용할 수 있는 작업량 K를 정했다. 선택한 모든 통의 작업량 합은 K 이하여야 한다. 통을 고를 때는 어떤 시작 번호 L과 끝 번호 R을 정하고 L번부터 R번까지의 통을 빠짐없이 골라야 한다. 가운데 통을 남겨 두거나, 서로 떨어진 두 구간을 함께 고르는 것은 허용하지 않는다. 선택한 통은 각각 한 번씩만 옮기므로 필요한 작업량은 A_L부터 A_R까지의 합이다. 담당자는 작업량 제한을 지키면서 가능한 한 많은 반찬 통을 옮기려 한다. 선택한 통의 개수는 R-L+1이다. 가장 많은 통을 옮길 수 있는 구간이 여러 개라면 시작 번호 L이 가장 작은 구간을 선택한다. 시작 번호와 통의 개수가 같으면 끝 번호도 같으므로 그 밖의 동점 처리는 필요하지 않다. 작업량 합이 같다는 이유로 다른 구간을 우선하지는 않는다. 한 통이라도 선택할 수 있으면 선택한 통의 개수와 시작 번호, 끝 번호를 차례대로 출력해야 한다. 모든 통의 작업량이 K보다 커서 아무 통도 선택할 수 없다면 세 정수 0 0 0을 출력한다. 입력으로 주어진 통의 순서를 바꾸지 않고, 위 규칙에 따라 담당자가 선택할 구간을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 둘째 줄에 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 200,000
1 ≤ K ≤ 10^15
1 ≤ A_i ≤ 10^9
모든 입력값은 정수이다.

출력

선택한 통의 개수, 시작 번호, 끝 번호를 공백으로 구분하여 한 줄에 출력한다. 선택할 수 있는 통이 없으면 0 0 0을 출력한다.

7 6
3 2 1 4 2 1 1

3 1 3

4 3
2 2 2 2

1 1 1

3 2
3 5 4

0 0 0

출처: Devin.KR 자체 제작