U198619 山海经

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

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

输入第1行是两个数，$n$，$m$，$2≤n≤10^5$，$1≤m≤10^5$，$n$ 表示一共有 $n$ 座山，$m$ 表示老师想查询的数目。 第2行是 $n$ 个整数，代表 $n$ 座山的喜恶度，绝对值均小于$10^4$。 以下 $m$ 行每行有 $a$，$b$ 两个数，$1≤a≤j≤b≤m$，表示第 $a$ 座山到第 $b$ 座山。

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

$2≤n≤100000$，$1≤m≤100000$