题目背景

  “南山之首日鹊山。其首日招摇之山，临于西海之上，多桂，多金玉。有草焉，其状如韭而青华，其名日祝余，食之不饥……又东三百里，日堂庭之山，多棪木，多白猿，多水玉，多黄金。

  又东三百八十里，日猨翼之山，其中多怪兽，水多怪鱼，多白玉，多蝮虫，多怪蛇，名怪木，不可以上。……”

  《山海经》是以山为纲，以海为线记载古代的河流、植物、动物及矿产等情况，而且每一条记录路线都不会有重复的山出现。

题目描述

  某天，你的地理老师想重游《山海经》中的路线，为了简化问题，老师已经把每座山用一个整数表示他对该山的喜恶程度，他想知道第 $a$ 座山到第 $b$ 座山的中间某段路$(i,j)$。能使他感到最满意，即 $(i,j)$ 这条路上所有山的喜恶度之和是 $(c,d)$ 的最大值（$a\le c\le d\le b$）。于是老师便向你请教，你能帮助他吗?

  值得注意的是，在《山海经》中，第 $i$ 座山只能到达第 $i+1$ 座山。

形式化题意

请你维护一个序列，支持区间查询最大字段和并输出最大字段和的位置，如果有多组解，则输出最靠左的一组解。

输入格式

  输入第$1$行是两个数 : $n,m$（$2 \le n \le 10^5,1 \le m \le 10^5$），$n$ 表示一共有 $n$ 座山，$m$ 表示老师想查询的数目。

  第2行是 $n$ 个整数，代表 $n$ 座山的喜恶度，绝对值均小于 $10000$。

  以下$m$行每行有 $a,b$ 两个数，$1 \le a \le j \le b \le m$，表示第 $a$ 座山到第 $b$ 座山。

输出格式

  一共有 $m$ 行，每行有 $3$ 个数 $i,j,s$，表示从第 $i$ 座山到第 $j$ 座山总的喜恶度为 $s$。显然，对于每个查询，有 $a \le i \le j \le b$，如果有多组解，则输出最靠左的一组解。

样例 #1

样例输入 #1

5 3
5 -6 3 -1 4
1 3
1 5
5 5

样例输出 #1

1 1 5
3 5 6
5 5 4

提示

本题对于初学线段树较难。

由于出题人眼瞎 希望大家学习新的算法，增强了数据，把1~5测试点开到了$10^6$ 请使用 线性算法 优秀的卡常通过此题

（如果你是用线段树，只能过6~10测试点是正常的）