#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#define int long long
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
const int MAXN = 2e6 + 10;
const int MAXQ = 5e5 + 10;
int n, m, l, q;
int t[MAXN];
struct Query {
int a;
int b;
int32_t id;
} r[MAXQ];
int ans[MAXQ];
bool cmp(Query x, Query y) {
return x.a < y.a;
}
int slope[MAXN], intercept[MAXN];
inline bool should_popfront(int32_t j, int32_t k, int x) {
return (__int128) x * slope[j] + intercept[j] > (__int128) x * slope[k] + intercept[k];
}
inline bool should_popback(int32_t prev, int32_t cur, int32_t nxt) {
return (__int128) (t[cur] - t[prev]) * (nxt - cur) > (__int128) (t[nxt] - t[cur]) * (cur - prev);
}
int32_t LLright[22][MAXN], LLleft[22][MAXN];
struct Node {
int8_t lvl;
int32_t frontptr = -1, backptr = -1;
int eval(int x) {
int32_t* right = LLright[lvl];
int32_t* left = LLleft[lvl];
while (frontptr < backptr && should_popfront(frontptr, right[frontptr], x)) {
frontptr = right[frontptr];
left[frontptr] = -1;
}
return x * slope[frontptr] + intercept[frontptr];
}
void insert(int32_t ts) {
int32_t* right = LLright[lvl];
int32_t* left = LLleft[lvl];
while (frontptr < backptr && should_popback(left[backptr], backptr, ts)) {
backptr = left[backptr];
right[backptr] = -1;
}
if (backptr != -1) {
right[backptr] = ts;
left[ts] = backptr;
}
else frontptr = ts;
backptr = ts;
}
} seg[1 << 22]; // oh my days....
void init(int l, int r, int idx, int lvl = 0) {
seg[idx].lvl = static_cast<int16_t>(lvl);
for (int i=l; i<=r; i++) {
seg[idx].insert(i);
}
if (l == r) return;
int mid = (l + r) >> 1;
init(l, mid, (idx << 1) + 1, lvl + 1);
init(mid + 1, r, (idx << 1) + 2, lvl + 1);
}
int qu(int l, int r, int constl, int constr, int idx, int temp) {
if (l <= constl && constr <= r) return seg[idx].eval(temp);
int mid = (constl + constr) >> 1;
if (mid < l || r < constl) return qu(l, r, mid+1, constr, (idx<<1) + 2, temp);
else if (constr < l || r < mid+1) return qu(l, r, constl, mid, (idx<<1) + 1, temp);
else {
return min(qu(l, r, constl, mid, (idx<<1) + 1, temp), qu(l, r, mid+1, constr, (idx<<1) + 2, temp));
}
}
int compute(int L, int R, int temp) { // 0 <= L <= R < m
return qu(L, R, 0, m - 1, 0, temp);
}
void solve(int tc) {
cin >> n >> m >> l >> q;
for (int i=0; i<m; i++) cin >> t[i];
for (int i=0; i<m; i++) slope[i] = -i, intercept[i] = t[i];
init(0, m - 1, 0);
for (int i=1; i<=q; i++) {
cin >> r[i].a >> r[i].b;
r[i].id = i;
}
sort(r+1, r+q+1, cmp);
for (int ii=1; ii<=q; ii++) {
int a = r[ii].a, b = r[ii].b;
int L = 0, R = 0;
{
int lb = 0, rb = m - 1;
while (lb < rb) {
int mid = (lb + rb + 1) >> 1;
if (t[mid] <= b) lb = mid;
else rb = mid - 1;
}
if (t[lb] > b) L = -1, R = -1;
else R = lb;
}
if (L != -1) {
int lb = 0, rb = m - 1;
while (lb < rb) {
int mid = (lb + rb) >> 1;
if (t[mid] + l >= b) rb = mid;
else lb = mid + 1;
}
if (t[lb] + l < b) L = -1, R = -1;
else L = lb;
}
if (L == -1 || R == -1) {
ans[r[ii].id] = 0;
continue;
}
if (L > R) {
ans[r[ii].id] = 0;
continue;
}
// L, R are 0-based
int y = compute(L, R, a);
int lb = L, rb = R + 1;
while (lb < rb) {
int mid = (lb + rb) >> 1;
int bound = b - (mid - 1) * a - l;
if (y >= bound) rb = mid;
else lb = mid + 1;
}
ans[r[ii].id] = R - lb + 1;
}
for (int i=1; i<=q; i++) cout << ans[i] << "\n";
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
for (int i=1; i<=t; i++) {
solve(i);
}
}
