// O(M + Q(logQ + logM))
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
bool convex(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) {
auto [ax, ay] = a;
auto [bx, by] = b;
auto [cx, cy] = c;
assert(ax < bx and bx < cx);
return (bx - ax) * (cy - by) - (by - ay) * (cx - bx) > 0;
}
class IncrementalConvexHull {
vector<pair<ll, ll>> ori;
vector<pair<ll, ll>> v;
public:
IncrementalConvexHull() {}
void add(ll x, ll y) {
auto p = make_pair(x, y);
while (v.size() >= 2 and !convex(v[v.size() - 2], v[v.size() - 1], p)) v.pop_back();
v.push_back(p);
ori.push_back(p);
}
// -lx + y が最小となる点を返す
pair<ll, ll> get_min(ll l) {
assert(!v.empty());
int ok = v.size() - 1, ng = -1;
while (abs(ok - ng) > 1) {
int m = (ok + ng) / 2;
if (v[m].second + (v[m + 1].first - v[m].first) * l <= v[m + 1].second) ok = m;
else ng = m;
}
return v[ok];
}
vector<pair<ll, ll>> get_original_points() {
return ori;
}
void clear() {
ori.clear();
v.clear();
}
bool empty() {
return ori.empty();
}
};
class DecrementalConvexHull {
vector<pair<ll, ll>> pt;
vector<vector<pair<ll, ll>>> ls;
vector<pair<ll, ll>> v;
int n, iter;
public:
DecrementalConvexHull() : n(0), iter(0) {}
void build(const vector<pair<ll, ll>> &points) {
pt = points;
ls.clear();
v.clear();
n = pt.size();
iter = 0;
ls.resize(n);
for (int i = n - 1; i >= 0; i--) {
while (v.size() >= 2 and !convex(pt[i], v[v.size() - 1], v[v.size() - 2])) {
ls[i].push_back(v.back());
v.pop_back();
}
v.push_back(pt[i]);
}
}
void del() {
assert(iter < n);
assert(v.back() == pt[iter]);
v.pop_back();
while (!ls[iter].empty()) {
v.push_back(ls[iter].back());
ls[iter].pop_back();
}
++iter;
}
// -lx + y が最小となる点を返す
pair<ll, ll> get_min(ll l) {
assert(iter < n);
assert(!v.empty());
int ok = v.size() - 1, ng = -1;
while (abs(ok - ng) > 1) {
int m = (ok + ng) / 2;
if (v[m].second + (v[m + 1].first - v[m].first) * l <= v[m + 1].second) ok = m;
else ng = m;
}
return v[ok];
}
bool empty() {
return iter == n;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n, m, L, q;
cin >> n >> m >> L >> q;
vector<ll> t(m);
for (ll &i: t) cin >> i;
vector<ll> a(q), b(q);
for (int i = 0; i < q; i++) {
cin >> a[i] >> b[i];
}
vector<int> ord(q);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) { return b[i] < b[j]; });
vector<ll> ans(q);
int nl = 0, nr = 0;
IncrementalConvexHull right;
DecrementalConvexHull left;
for (int i: ord) {
int l = lower_bound(t.begin(), t.end(), b[i] - L) - t.begin();
int r = upper_bound(t.begin(), t.end(), b[i]) - t.begin();
assert(nl <= l and nr <= r);
while (nr < r) {
right.add(nr, t[nr] + L);
++nr;
}
while (nl < l) {
if (left.empty()) {
left.build(right.get_original_points());
right.clear();
}
left.del();
++nl;
}
auto get_val = [&](pair<ll, ll> p) -> ll {
auto [x, y] = p;
return (y - b[i]) / a[i] + (r - 1 - x);
};
ans[i] = r - l;
if (!left.empty()) ans[i] = min(ans[i], get_val(left.get_min(a[i])));
if (!right.empty()) ans[i] = min(ans[i], get_val(right.get_min(a[i])));
}
for (int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
}
