Типова задача на запити

Дано два цілі числа $C$ та $L$ та масив $a$, що складається з $n$ цілих чисел. Дано $q$ запитів формату $lrx$. Після кожного запиту потрібно:

1. відняти $x$ від усіх елементів на відрізку $[l;r]$ масиву $a$;

2. сказати, чи існує гарний відрізок $S$ в масиві $a$. Відрізок $S$ вважається гарним, якщо $len(S)\ge L$ та $avg(S)\le C$, де $len(S)$ позначає довжину відрізка $S$, а $avg(S)$ позначає середнє значення на відрізку $S$.

Вхідні дані

Перший рядок містить чотири цілі числа $n$, $L$ ($1\le L\le n\le 2\cdot 10^5$), $q$ ($1\le q\le 2\cdot 10^5$), $C$ ($-10^9\le C\le 10^9$).

Другий рядок містить $n$ цілих чисел $a_i$ ($-10^9\le a_i\le 10^9$) — заданий масив $a$.

Наступні $q$ рядків містять три цілих числа $l$, $r$ ($1\le l\le r\le n$), $x$ ($0\le x\le 10^7$) кожен — опис запитів.

Вихідні дані

Виведіть $q$ рядків, кожен з яких містить YES, якщо існує гарний відрізок $S$, або NO у протилежному випадку.

Приклади

Оцінювання

1. ($11$ балів): $n\le 3$;

2. ($12$ балів): $n\le 100$, $q\le 1000$;

3. ($14$ балів): $q=1$, $C=0$;

4. ($15$ балів): $C=0$;

5. ($19$ балів): $q=1$;

6. ($29$ балів): без додаткових обмежень.