题目描述

小码哥是个贪吃的孩子，这天，大厨小W为小码哥准备了$n$道菜，排成一排，编号从$1$到$n$。小码哥不仅贪吃还挑食（好孩子不要学小码哥哦），他对第$i$道菜有一个喜恶度$a_i$，对于喜欢的菜，这个值是非负的，对于他不喜欢的菜，这个值是负的。小码哥虽然贪吃，但他也会吃撑，所以他会先选择一个区间$[l,r]$，然后把编号在这个区间中的菜全部吃掉，最后的满意度就是这些菜喜恶度的和。

大厨小W对小码哥的挑食习惯生了气，于是他准备考考小码哥，他会给出$m$次询问，每次询问给出一个区间$[a,b]$，对于一次询问，小码哥需要找到一个$[a,b]$的子区间$[c,d]$，使得他吃掉这个子区间的菜得到的满意度尽可能高。

然而，小码哥学艺不精，很难快速找到正确的子区间，你能帮帮他吗？

输入格式

第一行输入两个整数$n,m$； 第二行输入$n$个整数$a_i$； 接下来$m$行，每行输入两个整数$a,b$，表示一次询问。

输出格式

输出共$m$行，每行输出三个整数$c,d,s$。表示选择的子区间为$[c,d]$，满意度为$s$。小码哥不能不吃。如果存在多组解，输出$c$最小的解，如果$c$最小的解也有多组，输出$d$最小的解。

样例输入 #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\leq n,m\leq 10^5,|a_i|\leq 10^4,1\leq a\leq b\leq n$。