Codepowers

효원이는 해외 유명 Online Judge 사이트인 Codepowers의 회원이다. Codepowers는 회원들에게 레이팅 시스템을 제공하는데, 매주 열리는 라운드에 참여하면 레이팅을 매겨준다.

효원이는 라운드에 $N$번 참여했다. 효원이의 초기 레이팅 $X$와 각 라운드에 참여한 후 레이팅의 증감이 수열 $A$로 주어진다. 수열 $A$의 원소 $A\_i$는 $i$번째 라운드에 참여한 직후의 레이팅에서 그 라운드에 참여하기 직전의 레이팅을 뺀 값이다.

자신이 기대한 만큼 높은 레이팅 점수를 받지 못한 효원이는 목표 레이팅보다 낮은 레이팅을 언제 받았는지 궁금해한다.

$M$개의 쿼리가 주어진다. 각 쿼리마다 효원이가 $l$번째 라운드에 참여한 직후부터 $r$번째 라운드에 참여하기 직전까지 레이팅이 $K$보다 낮은 횟수를 출력하라.

첫째 줄에 정수 $N$, $M$, $K$, $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)$

둘째 줄에는 수열 $A$를 이루고 있는 정수 $A\_i$가 주어진다. $(-10^4 \leq A\_i \leq 10^4)$

셋째 줄부터 $M$줄에 걸쳐 쿼리가 주어진다. 각 줄에는 $j$번째 쿼리의 정보 $l\_j$, $r\_j$가 주어진다. $(1 \leq l\_j < r\_j \leq N+1)$

$M$줄에 걸쳐 각 쿼리의 답을 출력한다.