409327: GYM103485 I On The Way To Shopping

This is the harder version of the problem. The only difference between the two versions are the constraints on $$$n$$$ and $$$q$$$.

Marcos is buying shirts in the website MaratonEgito. In his shopping cart, he made a list of $$$n$$$ shirts, the i-th shirt has cost $$$a_i$$$. Marcos is waiting the confirmation of Stefano to finish his purchase, but Stefano changes his mind very frequently. Stefano considered $$$q$$$ scenarios, each one defined by the tuple $$$(l, r, d)$$$ having the following meaning. Stefano considered purchasing some of shirts in the range $$$[l, r]$$$ of Marcos' list spending at most $$$d$$$. When he considers a scenario, he obeys the following rule: if he decides to buy a shirt whose cost is $$$x$$$, he also buys all shirts in the range $$$[l, r]$$$ whose value is at most $$$x$$$. In other words, if Stefano decides to buy a shirt in the range, he needs to buy all the other shirts in the range whose price is less or equal. Marcos is losing his patience, and needs to calculate for each of the scenarios $$$(l, r, d)$$$, given by Stefano, the maximum money he can spend. Help Marcos and print the maximum money Stefano can spend in each of his scenarios. In this problem, each scenario must be answered on the fly!

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n , q, \leq 10^5$$$). The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$). The next $$$n$$$ lines contain tree integers representing a decision $$$x_i$$$, $$$y_i$$$, $$$z_i$$$.

The conversion to a query is defined below. $$$resp_i$$$ is the answer of the $$$i$$$ -th reflection.

$$$l_i = 1 + (x_i + resp_{i-1} - 1) \% n$$$

$$$r_i = 1 + (y_i + resp_{i-1} - 1) \% n$$$

$$$d_i = (z_i + resp_{i-1})$$$

$$$1 \leq l_i \leq r_i \leq n$$$.

$$$0 \leq d_i \leq 10^{15}$$$.

$$$1 \leq x_i,y_i \leq n$$$, $$$-10^{15} \leq z_i \leq 10^{15}$$$.

The value of $$$resp_0$$$ is 0 and you need to print $$$resp_i$$$ for $$$i$$$ from 1 to $$$q$$$.

For each scenario, print $$$resp_i$$$, the maximum Marcos can spend on this scenario.

4 1
3 4 6 5
1 3 10

7

5 1
2 4 4 4 3
1 4 13

2

3 3
5 10 15
1 1 5
3 3 5
2 2 5

5
10
15