Codepowers

효원이는 해외 유명 온라인 저지 사이트 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$개의 줄에 걸쳐 각 쿼리의 답을 출력한다.