Problem Description

Nanjing has a famous shopping street. A shopping street is just a neat row of stores.

Every time, the tour guide Xiao Z leads a tour group to walk along a segment of the shopping street, and then chooses one store to go in and shop.

All tourists that Xiao Z receives are shopaholics. They would like to buy everything in the store. In other words, as long as they can buy, they will keep buying (you do not need to consider whether they have enough money; they all have credit cards and can overdraw).

However, there is one more rule: they care a lot about equality and are very modest. No one can stand buying more or fewer items than others, so in the end, the number of items each person buys must be exactly the same. This means they cannot always empty the store, but they still bring the store a lot of business each time, and the store owners are very grateful. To show their thanks, the store owner decides to give the unsold items left after the tourists finish buying to the tour guide Xiao Z.

Greedy Xiao Z naturally hopes to receive as many gifted items as possible.

You are given that there are $n$ stores in total in this row (numbered from $0$ to $n-1$), and the total number of items in each store. Each time, Xiao Z brings a tour group of $p$ tourists, and they stroll among the stores between store $u$ and store $v$ (inclusive). Please help Xiao Z choose one store within the visited interval, and tell him the maximum number of items he can receive as a gift.

Input Format

The first line contains two integers $n,m$, representing the number of stores and the number of tour groups brought by Xiao Z.

The next line contains $n$ integers $a_i$, where $a_i$ is the total number of items in store $i$.

The next $m$ lines each contain three integers $u,v,p$, indicating that this tour group strolls among the stores between store $u$ and store $v$ (including $u$ and $v$), and the group size is $p$.

Output Format

Output $m$ lines in total. Each line contains one integer. On the $i$-th line, output the maximum number of items Xiao Z can receive as a gift after the $i$-th tour group finishes shopping.

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

Hint

Sample Explanation

For the first tour group, there are $2$ people, and the interval is from store $0$ to store $1$. If they go to store $1$, there are $2$ items in total, each person buys $1$ item, and $0$ items are left. If they go to store $2$, there are $4$ items in total, each person buys $2$ items, and $0$ items are left. Therefore, Xiao Z can receive at most $0$ items as a gift.

For the second tour group, there are $3$ people. Xiao Z chooses to take them to store $4$, which has $8$ items in total. Each person buys $2$ items (because $3$ items per person is not possible), leaving $2$ items. Thus, the maximum gift Xiao Z can receive is $2$ items. You can verify that choosing any other store will not allow Xiao Z to receive as many as $2$ items.

Constraints

For $100\%$ of the testdata, $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$.

Translated by ChatGPT 5