수확

IOI 농장은 큰 원형 호수 주변에 있는 사과 농장이다. 호수의 둘레는 $L$미터이다.

직원은 1번부터 $N$번까지 $N$명이고, 사과나무는 1번부터 $M$번까지 $M$그루이다.

시각 0에 직원 $i$는 호수의 가장 북쪽 지점에서 시계 방향으로 $A_i$미터 떨어진 곳에서 기다린다. $A_i$ 값은 모두 다르다. 사과나무 $j$는 가장 북쪽 지점에서 시계 방향으로 $B_j$미터 떨어진 곳에 자란다. $B_j$ 값은 모두 다르다. 어떤 직원의 시작 위치에도 사과나무는 없다.

사과나무마다 동시에 달려 있는 사과는 최대 한 개이다. 직원이 나무에서 사과를 수확하면, 정확히 $C$초 뒤에 그 나무에 새 사과가 열린다. 시각 0에는 모든 사과나무에 사과가 달려 있다. 모든 직원은 시계 방향으로 호수를 돌며 초속 1미터로 걷는다. 직원이 사과가 달린 나무에 도착하면 그 사과를 수확한다. 도착한 순간 새 사과가 열리면 그 사과도 수확한다. 수확에 걸리는 시간은 무시한다.

K 사장은 직원들의 효율을 알고 싶어 한다. 각 질의 $k$에 대해, 직원 $V_k$가 시각 $T_k$까지 수확한 사과의 수를 구하라. 시각 $T_k$에 수확한 사과도 포함한다.

첫째 줄에 $N$, $M$, $L$, $C$가 주어진다. 둘째 줄에 $A_1, \ldots, A_N$이, 셋째 줄에 $B_1, \ldots, B_M$이 주어진다. 다음 줄에 $Q$가 주어지고, 이어서 $Q$개의 줄에 $V_k$와 $T_k$가 주어진다.

N M L C
A1 ... AN
B1 ... BM
Q
V1 T1
...
VQ TQ

$Q$개의 줄을 출력한다. $k$번째 줄에는 $k$번째 질의의 답을 출력한다.

• $1 \le N \le 200000$
• $1 \le M \le 200000$
• $N + M \le L \le 10^9$
• $1 \le C \le 10^9$
• $0 \le A_i < L$ ($1 \le i \le N$)
• $A_i < A_{i+1}$ ($1 \le i \le N-1$)
• $0 \le B_j < L$ ($1 \le j \le M$)
• $B_j < B_{j+1}$ ($1 \le j \le M-1$)
• $A_i \ne B_j$ ($1 \le i \le N$, $1 \le j \le M$)
• $1 \le Q \le 200000$
• $1 \le V_k \le N$ ($1 \le k \le Q$)
• $1 \le T_k \le 10^{18}$ ($1 \le k \le Q$)

시간 제한은 3000 ms이고, 메모리 제한은 512 MB이다.