Description

Given a sequence of $n$ positive integers $a_1, a_2, \cdots, a_n$ and an integer $m$, find a subinterval $[i, j]$, that is, a consecutive part of the sequence $a_i, a_{i + 1}, \cdots, a_{j - 1}, a_j$, such that the sum of this subinterval is as large as possible while not exceeding $m$. If multiple intervals meet the requirement, output the one with the smallest $i$.

Input Format

The input has two lines.

The first line contains two integers $n, m$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

Output Format

Output one line with three integers, representing the left endpoint, the right endpoint, and the cumulative sum of the interval that meets the requirement.

5 10
2 3 4 5 6

1 3 9

Hint

Subtask 1 (10 points): $n \le 200$.

Subtask 2 (20 points): $n \le 3000$.

Subtask 3 (30 points): $n \le 10^5$.

Subtask 4 (40 points): $n \le 4 \times 10^6$.

For $100\%$ of the testdata, $1 \leq n \leq 4 \times 10^6$, $1 \leq m \leq 10^9$, $0 \leq a_1, a_2, \cdots, a_n \leq 10^5$.

Translated by ChatGPT 5