You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定 $n$ 个正整数组成的数列 $a_1, a_2, \cdots, a_n$ 和一个整数 $m$。求出这个数列中的一个子区间 $[i, j]$，也就是在这个数列中连续的数字 $a_i, a_{i + 1}, \cdots, a_{j - 1}, a_j$，使得这个子区间的和在不超过 $m$ 的情况下最大。如果有多个区间符合要求，请输出 $i$ 最小的那一个。

输入格式

输入共两行。

第一行，两个整数 $n, m$；

第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$。

输出格式

一行，三个整数，表示符合题意的区间的左端点、右端点和累加和。

样例 #1

样例输入 #1

5 10
2 3 4 5 6

样例输出 #1

1 3 9

提示

子任务 1（10分）：$n\le 200$ ；

子任务 2（20分）：$n\le 3000$ ；

子任务 3（30分）：$n\le 10^5$ ；

子任务 4（40分）：$n\le 4\times 10^6$ 。

对于 $100\%$ 的数据，$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$。