Typical Query Problem#235
You are given two integers and and array consisting of integers. You are given queries of format l \: r \: x. After each query, you have to:
subtract from all elements on a segment [l;r] of array ;
tell whether there exist a good segment on the array . A segment is considered good if len(S) \ge L and avg(S) \le C, where len(S) denotes the length of the segment and avg(S) denotes the average value on segment .
The first line of input contains four integers , (1 \le L \le n \le 2 \cdot 10^5), (1 \le q \le 2 \cdot 10^5), (-10^9 \le C \le 10^9).
The second line of input contains integers a_i (-10^9 \le a_i \le 10^9) — given array .
The following lines contain three integers , (1 \le l \le r \le n), (0 \le x \le 10^7) each — description of the queries.
Print lines, each consisting of YES, if there exists a good segment , or NO otherwise.
Example 1
( points): n \le 3;
( points): n \le 100, q \le 1000;
( points): q = 1, C = 0;
( points): C = 0;
( points): q = 1;
( points): no additional restrictions.