Codepowers

Hyowon is a member of Codepowers, a well-known overseas online judge. Codepowers gives its members a rating system. Each time a member joins a weekly round, the site assigns a rating.

Hyowon has taken part in $N$ rounds. Hyowon's initial rating $X$ and the change in rating after each round are given as a sequence $A$. The element $A_i$ is the rating right after the $i$-th round minus the rating right before that round.

Hyowon did not earn the rating expected, and wants to know when the rating fell below the target.

$M$ queries are given. For each query, print the number of times the rating was lower than $K$ from right after round $l$ to right before round $r$.

The first line contains integers $N$, $M$, $K$, and $X$. $(1 \leq N \leq 10^5, 1 \leq M \leq 10^6, -10^9 \leq K \leq 10^9, -10^4 \leq X \leq 10^4)$

The second line contains the integers $A_i$ that make up the sequence $A$. $(-10^4 \leq A_i \leq 10^4)$

From the third line onward, $M$ lines follow, each giving the query $l_j$, $r_j$ for the $j$-th query. $(1 \leq l_j < r_j \leq N+1)$

Print $M$ lines, each containing the answer to one query.