As an attempt to convince you that Vancouver is a wonderful city, here are a few well-known facts:
Suppose we know the forecast for the next $$$n$$$ minutes. Say the amount of rain during the $$$i$$$-th minute is $$$w_i$$$. There will be $$$m$$$ students and each student will inevitably make a trip from one building to another. Attempting to stay dry, the $$$j$$$-th student carries an umbrella with an efficiency of $$$e_j$$$, meaning that the umbrella can block $$$e_j$$$ units of rain per minute. Thus, if student $$$j$$$ is outside during the $$$i$$$-th minute, the umbrella will block $$$\min(e_j, w_i)$$$ units of rain (because you can't block rain that doesn't exist). Finally, suppose student $$$j$$$ is outside from minute $$$l_j$$$ to minute $$$r_j$$$ inclusive. We want to know how wet each student gets (ie. how many units of rain will hit each student).
The first line of input contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 2\times10^5$$$), giving the number of minutes of the forecast and the number of students respectively.
The second line of input contains $$$n$$$ space-separated integers $$$w_i$$$ ($$$1 \le w_i \le 10^9$$$), giving the amount of rain during the $$$i$$$-th minute.
Each of the next $$$m$$$ lines of input contains three space-separated integers $$$l_j$$$, $$$r_j$$$, and $$$e_j$$$ ($$$1\le l_j\le r_j\le n,\ 0\le e_j\le 10^9$$$). This means the $$$j$$$-th student is outside from minute $$$l_j$$$ to minute $$$r_j$$$ inclusive, and has an umbrella of efficiency $$$e_j$$$.
The output should contain $$$m$$$ lines. The $$$j$$$-th line should contain a single integer, which is the number of units of rain that hit student $$$j$$$.
6 43 1 4 1 5 91 3 31 6 02 2 9992 5 2
1 23 0 5
