One of the longest-running events of the Office Olympics is the Toilet High Jump. This event was initially introduced to the Olympics by Thomas Crapper in 1905 as a means to get his employees more excited to sell toilets. The event rewards the ability to jump to very tall heights, with the gold medal being awarded to the employee who can jump the highest.
The way the event is structured is as follows: The $$$n$$$ employees of Crapper & Co. each have predetermined "jump heights" $$$j_i$$$ (measured in units) that determine the maximum height they can jump. The event will consist of $$$m$$$ rounds. Initially, there is a sequence of $$$k$$$ tiles containing exactly one toilet each. During the $$$i$$$-th round, Thomas will choose two indices $$$l_i$$$ and $$$r_i$$$ (subject to $$$1 \leq l_i \leq r_i \leq k$$$) and then an integer $$$x_i$$$ and stack exactly $$$x_i$$$ unique toilets upon the existing toilets in the tiles $$$l_i, l_i + 1, \dots, r_i$$$. That is to say, the number of toilets within each of the tiles in the range $$$[l_i, r_i]$$$ will increase by $$$x_i$$$.
Importantly, each toilet has a height of 1 unit, and when a new toilet is added to a tile, the height of the toilets in that tile increases by 1 unit. Once the toilets in the $$$i$$$-th round have been added, each of the $$$n$$$ employees will attempt to jump from tile $$$1$$$ to tile $$$k$$$. Initially, each employee will be standing atop the pile of toilets in tile $$$1$$$, and to jump from tile $$$i$$$ to tile $$$i+1$$$ (assuming the current heights of toilets in tiles $$$i$$$ and $$$i+1$$$ are $$$h_i$$$ and $$$h_{i+1}$$$, respectively), the employee must have a jump height of at least $$$\text{max}(0, h_{i+1} - h_i)$$$. Obviously, it could be the case that some employees cannot finish the course and won't earn a point for that specific round.
As the referee of the event, your job is simple. You must carefully observe each round and determine how many employees earn points after each of the $$$m$$$ rounds. Then, you must report this information to Thomas Crapper so that he may determine the winner (and thus the employee(s) who will receive the gold medal). Note that toilets are not reset between rounds, that is, added toilets remain stacked in their respective tiles.
The input will begin with a line containing three space-separated integers, $$$n$$$ ($$$1 \leq n \leq 10^5$$$), $$$m$$$ ($$$1 \leq m \leq 10^5$$$), and $$$k$$$ ($$$1 \leq k \leq 10^5$$$) as described above.
The next line of input will consist of $$$n$$$ space-separated integers $$$j_i$$$ ($$$1 \leq j_i \leq 10^{18}$$$), denoting the jump heights of the $$$n$$$ employees.
The next $$$m$$$ lines of input will each describe one of the rounds of the event. Each of these $$$m$$$ lines will consist of three space-separated integers $$$l_i$$$, $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq k$$$), and $$$x_i$$$ ($$$1 \leq x_i \leq 2 \cdot 10^9$$$). These three integers describe the $$$i$$$-th round of the event as explained above.
Your output should consist of exactly $$$m$$$ lines, one for each of the rounds of the event. The $$$i$$$-th line of output should represent the number of employees who are able to complete the $$$i$$$-th round of the event.
5 4 5 1 2 3 4 5 2 5 2 1 1 3 3 4 4 1 2 3
4 5 2 5
