U234960 山海经

``` “南山经之首，曰鹊山。其首曰招摇之山，临于西海之上，多桂，多金玉。 有草焉，其状如韭而青华，其名日祝余，食之不饥…… 又东三百里，曰堂庭之山，多棪木，多白猿，多水玉，多黄金。 又东三百八十里，曰猿翼之山，其中多怪兽，水多怪鱼，多白玉，多蝮虫，多怪蛇，名怪木，不可以上。” ```

《山海经》是以山为纲，以海为线记载古代的河流、植物、动物及矿产等情况，而且每一条记录路线都不会有重复的山出现。 某天，你的地理老师想重游《山海经》中的路线，为了简化问题，老师已经把每座山用一个整数表示他对该山的喜恶程度，他想知道第 $a$ 座山到第 $b$ 座山的中间哪段路 $(i, j)$ 能使他感到最满意。于是老师便向你请教，你能帮助他吗? 值得注意的是，在《山海经》中，第 $i$ 座山只能到达第 $i+1$ 座山。 我们定义一段路的满意程度为这条路上所有山的喜恶度之和。

第一行，两个整数：$n, m$，表示一共有 $n$ 座山和表示老师想查询的数目。 第二行是 $n$ 个整数，代表 $n$ 座山的喜恶度，绝对值均小于 $10000$。 接下来 $m$ 行每行有 $a, b$ 两个数，表示老师要从第 $a$ 座山到第 $b$ 座山。

一共有 $m$ 行，每行有三个数 $i, j, s$，表示从第 $i$ 座山到第 $j$ 座山总的喜恶度为 $s$。 如果有多组解，则输出i最小的，如果i也相等，则输出j最小的解。

**【数据范围】** 对于 $100\%$ 的数据， $2 \le n \le 10^5, 1 \le a \le b \le m \le 10^5$