题目描述

南京有一条著名的购物街。购物街嘛，就是一排整齐的商店啦~

导游小 Z 每次都会把游客团带到购物街里走一段，然后选择一个商店进去购物。

小 Z 接待的游客都是购物狂，他们恨不得将店内的商品洗劫一空，也就是说，只要他们能买，就一定会继续买（钱够不够你不用考虑，他们都有信用卡可以透支）。

但是有一点，他们都非常讲究平等、很谦虚，每个人都不能忍受比别人多买什么东西或者少买什么东西，于是他们每个人最后买的商品数量都是一样的。这虽然导致他们没办法每次都把商店搬空，但是每次已经给店家带来一大笔生意了，店家已经非常感谢了！为了表示感谢，店家决定把游客们买完之后剩下来那几件没卖掉的商品就送给导游小 Z 了。

贪心的小 Z 自然希望自己能获赠的商品数量越大越好啦~

现在告诉你这一排共 $n$ 个商店（标号为 $0$ 到 $n-1$）每个商店里的商品总数，每次小 Z 会带一批共 $p$ 个游客的旅游团，到其中 $u$ 号商店和 $v$ 号商店之间逛一逛，请你帮小 Z 在所逛的商店区间内选择一个，告诉小 Z 他最多能获赠多少件商品。

输入格式

第一行，包含两个整数 $n,m$，分别表示商店个数和小 Z 带来的旅游团个数。

接下来一行，包含 $n$ 个整数 $a_i$，表示第 $i$ 个商店的商品总数。

接下来 $m$ 行，每行三个整数 $u,v,p$，表示这个旅游团逛 $u$ 号商店和 $v$ 号商店之间的商店（包含 $u$ 和 $v$），且这个旅游团的人数为 $p$。

输出格式

共输出 $m$ 行，每行一个整数，第 $i$ 行输出第 $i$ 个旅游团购物后，小 Z 最多能获赠的商品数量。

5 5
2 4 6 8 10
0 1 2
1 4 3
2 4 2
1 1 9
0 4 7

0
2
0
4
6

提示

样例解释

第一个旅游团， $2$ 个人， $0$ 号商店到 $1$ 号商店的区间。若去 $1$ 号商店，共 $2$ 件商品，每人买 $1$ 件，剩 $0$ 件。若去 $2$ 号商店，共 $4$ 件商品，每人买 $2$ 件，剩 $0$ 件。所以，小 Z 最多获赠 $0$ 件。

第二个旅游团， $3$ 个人，小 Z 选择带他们去 $4$ 号商店，共 $8$ 件商品，每人买 $2$ 件商品（因为每人 $3$ 件不够），剩下 $2$ 件，小 Z 最多获赠就是 $2$ 件。 可以验证去其它商店小 Z 最多获赠的商品不会达到 $2$ 件。

数据范围

对于 $100\%$ 的数据，$1 \leq n\leq 10^6,1 \leq m\leq 5\times 10^4,0\leq a_i\leq 10^3,2\leq p\leq 10^3,0\leq u,v\leq n-1$。