J. Just Use an Umbrella
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

As an attempt to convince you that Vancouver is a wonderful city, here are a few well-known facts:

  • Winters are very rainy.
  • The weather forecast is incredibly accurate and can accurately forecast the weather for an entire season (of course, it rains every second).
  • The rain will get to you, no matter the umbrella.

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).

Input

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$$$.

Output

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$$$.

Example
Input
6 4
3 1 4 1 5 9
1 3 3
1 6 0
2 2 999
2 5 2
Output
1
23
0
5