该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

小明瞎看 OI-WIKI，看出来了下一个 T1。

请注意此题独特的时间限制，这已经是 std 两倍时限。

题目描述

小明有一个长度为 $n$ 的整数数组 $a_1,...,a_n$。

现在，小明有 $Q$ 个问题，每个问题形如：

对于这个序列的区间 $[l,r]$，小明想从中取一些数字，使得取到的数字之和最大，且满足：

（1）第 $x$ 个数字必须得取。

（2）相邻两个数字中，至多只能取一个数字。

请帮小明回答每一个问题。

输入格式

第一行输入 $n,Q$。

第二行输入 $n$ 个整数 $a_1,...,a_n$。

接下来 $Q$ 行，每行三个数字 $l,r,x$。

输出格式

对于每个询问，输出一个数字表示答案，答案输出在同一行，用空格隔开。

样例输入 #1

5 5
1 -1 -2 3 1
1 5 1
1 5 2
3 4 3
2 4 2
2 5 3

样例输出 #1

4 2 -2 2 -1

下发文件

数据范围

本题共 20 个测试点。

对于全部测试数据：$1\leq n\leq 2\times 10^5,1\leq Q\leq 5\times 10^5,|a_i|\leq 10^5$。