Типова задача на запити#235
Дано два цілі числа та та масив , що складається з цілих чисел. Дано запитів формату l \: r \: x. Після кожного запиту потрібно:
відняти від усіх елементів на відрізку [l;r] масиву ;
сказати, чи існує гарний відрізок в масиві . Відрізок вважається гарним, якщо len(S) \ge L та avg(S) \le C, де len(S) позначає довжину відрізка , а avg(S) позначає середнє значення на відрізку .
Перший рядок містить чотири цілі числа , (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).
Другий рядок містить цілих чисел a_i (-10^9 \le a_i \le 10^9) — заданий масив .
Наступні рядків містять три цілих числа , (1 \le l \le r \le n), (0 \le x \le 10^7) кожен — опис запитів.
Виведіть рядків, кожен з яких містить YES, якщо існує гарний відрізок , або NO у протилежному випадку.
Приклад 1
( балів): n \le 3;
( балів): n \le 100, q \le 1000;
( балів): q = 1, C = 0;
( балів): C = 0;
( балів): q = 1;
( балів): без додаткових обмежень.