406718: GYM102503 O Gravity Superfight

After hearing reports of a girl with incredible gravitational powers from members of the Port Mafia, Chuuya Nakahara eagerly went to visit this potential rival by the name of Nitta Hina. To his shock upon seeing her, however, Hina was merely a teen! After a momentary revelling in his height superiority, Chuuya challenged Hina to a game testing their gravitational ability. Hina was hesitant, but agreed on the condition that Chuuya would buy her a bowl of ikura afterwards.

Of course, having heard rumors of Hina and her yakuza father Yoshifumi's exploits (such as their elimination of a rival gang without help; massacred, dude), and as the vessel of the powerful Arahabaki, Chuuya was aware that a one on one match of power between them would lead to large-scale destruction. Instead, Chuuya suggested a game of control. The game would take place in a Port Mafia owned warehouse. The warehouse contains $$$n$$$ piles of crates lined up in a row, with each pile having a stack of $$$A_i$$$ crates. Define a subrange $$$[l, r]$$$ of all these piles to contain the piles $$$A_l, A_{l+1}, \ldots, A_r$$$. Now the instability of a subrange is the maximum difference in crate height between any two piles contained in the subrange. More formally, given a subrange $$$[l, r]$$$, its instability is defined as the maximum value of $$$|A_i - A_j|$$$ where $$$l \le i, j \le r$$$. Now, the game Hina and Chuuya will play goes as follows. First, they will agree on a subrange $$$[l, r]$$$ and a value $$$k$$$. Then they take turns transferring crates one at a time, carried only by their gravitational powers, from another Port Mafia warehouse with unlimited crates onto the subrange $$$[l, r]$$$. They cannot move crates already in the subrange $$$[l, r]$$$. There will be exactly $$$k$$$ turns altogether (and hence $$$k$$$ crates moved). If either of them destroy or drop a crate during their turn, they lose! Otherwise, Hina's goal is to maximize the instability of the selected subrange while Chuuya's goal is to minimize it.

Upon arrival at the warehouse, however, Hina decided to take a nap. For her, this fight was rather reminiscent to the challenges of a certain blonde-haired girl. Little did she know, this carefree confident behavior was for Chuuya rather reminiscent of a certain dark brown-haired guy. Hina's behavior thus infuriated Chuuya, making him determined to utterly win against Hina. Chuuya believes he utterly wins if the instability of the chosen subrange is minimized after the $$$k$$$ turns, assuming he places the crates on the piles optimally and Hina places them as stupidly as possible (as if she's playing to lose). Let's call this minimal value $$$c$$$. While Hina was sleeping, Chuuya was able to think of $$$q$$$ likely games with their own $$$l$$$, $$$r$$$, and $$$k$$$, in the warehouse. However, he has yet to compute each game's $$$c$$$. Help Chuuya compute this!

The first line of input contains $$$n$$$ and $$$q$$$, the number of piles in the warehouse and the number of possible games Chuuya is thinking of, respectively.

The second line of input contains $$$n$$$ space-separated integers $$$A_1, A_2, \ldots, A_n$$$, the number of crates in each pile.

The next $$$q$$$ lines each contain three space-separated integers $$$l$$$, $$$r$$$, and $$$k$$$, describing a game setting Chuuya is thinking of.

For each query, print a single line containing a single integer denoting the value $$$c$$$ for the game Chuuya is thinking of. Since $$$c$$$ may be very large, only output its remainder when divided by $$$1234567890$$$.

$$$1 \le n \le 3 \cdot 10^5$$$

$$$1 \le q \le 3 \cdot 10^5$$$

$$$1 \le A_i \le 10^9$$$

$$$1 \le k \le 10^{12}$$$

Subtask 1 (25 points): $$$n, q \le 200$$$

Subtask 2 (24 points): $$$n, q \le 5000$$$

Subtask 3 (36 points): $$$n, q \le 60000$$$

Subtask 4 (15 points): $$$n, q \le 300000$$$

5 5
1 2 3 7 4
3 5 10
1 4 8
2 5 1
2 5 2
2 5 3

0
3
4
4
3

For the first query, we consider the boxes in the range $$$[3,5]$$$, which have 3, 7, and 4 crates in each pile, respectively. There are 10 turns in total, meaning Hina and Chuuya each get 5 turns, and thus 5 crates each to move onto the piles. If Hina were stupid enough to place all 5 of her crates on the 3rd pile, and Chuuya were smart enough to put 1 crate on the 4th pile and 4 crates on the 5th pile, then all three piles would have 8 crates in them, giving an instability of 0.

For the third query, it can be verified that placing the 1 crate on the 2nd pile would give the smallest instability of 4.