Typical Query Problem

You are given two integers $C$ and $L$ and array $a$ consisting of $n$ integers. You are given $q$ queries of format $lrx$. After each query, you have to:

1. subtract $x$ from all elements on a segment $[l;r]$ of array $a$;

2. tell whether there exist a good segment $S$ on the array $a$. A segment $S$ is considered good if $len(S)\ge L$ and $avg(S)\le C$, where $len(S)$ denotes the length of the segment $S$ and $avg(S)$ denotes the average value on segment $S$.

Input

The first line of input contains four integers $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$).

The second line of input contains $n$ integers $a_i$ ($-10^9\le a_i\le 10^9$) — given array $a$.

The following $q$ lines contain three integers $l$, $r$ ($1\le l\le r\le n$), $x$ ($0\le x\le 10^7$) each — description of the queries.

Output

Print $q$ lines, each consisting of YES, if there exists a good segment $S$, or NO otherwise.

Examples

Scoring

1. ($11$ points): $n\le 3$;

2. ($12$ points): $n\le 100$, $q\le 1000$;

3. ($14$ points): $q=1$, $C=0$;

4. ($15$ points): $C=0$;

5. ($19$ points): $q=1$;

6. ($29$ points): no additional restrictions.