#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define endl '\n'
//#pragma GCC optimize("Ofast")
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair < int, int >;
using pll = pair < ll, ll >;
const ll INF = 4e18;
const ll DIM = 1000007;
const ll DIMQ = 2007;
const ld PI = 3.1415926535;
const int mod = 1e9 + 7;
vector < ll > b;
class convexHull {
public:
void init(int sz) {
d.resize(2 * sz);
l = sz;
r = sz;
}
void addLine(int k) {
while(r - l > 1 && (b[-d[r - 2]] - b[-k]) * ll(d[r - 1] - d[r - 2]) <= (b[-d[r - 2]] - b[-d[r - 1]]) * ll(k - d[r - 2])) {
r--;
}
d[r++] = k;
}
ll query(ll x) {
while(r - l > 1 && (b[-d[l + 1]] - b[-d[l]]) <= x * ll(d[l] - d[l + 1])) {
l++;
}
return (ll)d[l] * x + b[-d[l]];
}
private:
int l, r;
vector < int > d;
};
class segTree {
public:
void init(int sz) {
this->sz = sz;
T.resize(4 * sz + 7);
build(0, 0, sz - 1);
}
ll query(int L, int R, ll x) {
return query(0, 0, sz - 1, L, R, x);
}
int queryFast(int ind, ll x, ll t0) {
nodes.clear();
getNodes(0, 0, sz - 1, 0, ind);
int res = ind + 1;
ll mi = INF;
for(int i = nodes.size() - 1; i >= 0; i--) {
if(min(T[nodes[i].first].query(x), mi) + ll(nodes[i].second.first - 1) * x >= t0) {
res = min(res, nodes[i].second.first);
mi = min(mi, T[nodes[i].first].query(x));
}
else {
int tmp = descent(nodes[i].first, nodes[i].second.first, nodes[i].second.second, x, mi, t0);
res = min(res, tmp);
break;
}
}
return res;
}
private:
void build(int val, int tl, int tr) {
T[val].init((tr - tl + 1));
for(int i = tl; i <= tr; i++) T[val].addLine(-i);
if(tl == tr) return;
int tm = (tl + tr) >> 1;
build(2 * val + 1, tl, tm);
build(2 * val + 2, tm + 1, tr);
}
ll query(int val, int tl, int tr, int L, int R, ll x) {
if(L <= tl && tr <= R) return T[val].query(x);
if(tl > R || tr < L) return INF;
int tm = (tl + tr) >> 1;
return min(query(2 * val + 1, tl, tm, L, R, x), query(2 * val + 2, tm + 1, tr, L, R, x));
}
void getNodes(int val, int tl, int tr, int L, int R) {
if(L <= tl && tr <= R) {
nodes.push_back({ val, {tl, tr} });
return;
}
if(tl > R || tr < L) return;
int tm = (tl + tr) >> 1;
getNodes(2 * val + 1, tl, tm, L, R);
getNodes(2 * val + 2, tm + 1, tr, L, R);
}
int descent(int val, int tl, int tr, ll x, ll mi, ll t0) {
if(tl == tr) {
if(min(T[val].query(x), mi) + ll(tl - 1) * x >= t0) return tl;
else return sz;
}
int tm = (tl + tr) >> 1;
if(min(T[2 * val + 2].query(x), mi) + (ll)tm * x >= t0) {
return min(descent(2 * val + 1, tl, tm, x, min(mi, T[2 * val + 2].query(x)), t0), tm + 1);
}
else {
return descent(2 * val + 2, tm + 1, tr, x, mi, t0);
}
}
vector < pair < int, pii > > nodes;
int sz;
vector < convexHull > T;
}segt;
ll n, m, l, q;
vector < ll > t;
struct query {
ll x, b, num;
};
bool cmp(query q1, query q2) {
return q1.x < q2.x;
}
vector < query > Q;
vector < ll > res;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef IloveCP
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin >> n >> m >> l >> q;
t.resize(m);
b.resize(m);
for(int i = 0; i < m; i++) {
cin >> t[i];
b[i] = t[i] + l;
}
segt.init(m);
res.resize(q);
for(int i = 0; i < q; i++) {
ll x, b;
cin >> x >> b;
Q.push_back({x, b, i});
}
sort(Q.begin(), Q.end(), cmp);
for(int i = 0; i < q; i++) {
ll x = Q[i].x, b = Q[i].b;
auto it = upper_bound(t.begin(), t.end(), b);
if(it == t.begin()) {
res[Q[i].num] = 0;
}
else {
it--;
int ind = it - t.begin();
res[Q[i].num] = ind + 1 - segt.queryFast(ind, x, b);
}
}
for(int i = 0; i < q; i++) {
cout << res[i] << endl;
}
return 0;
}
