#include <bits/stdc++.h>
using namespace std;
const int64_t inf = 1e15;
struct line {
int64_t m, b;
line() : m(0), b(-inf) {}
line(int64_t m, int64_t b) : m(m), b(b) {}
int64_t operator()(int64_t x) { return m * x + b; }
};
struct query {
int64_t a, b, st, en, i;
};
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
int64_t n, m, wait, q;
cin >> n >> m >> wait >> q;
vector<int64_t> arr(m + 1);
vector<line> lines(m + 1);
for (int i = 1; i <= m; ++i) {
cin >> arr[i];
arr[i] += wait;
lines[i] = {i, -arr[i]};
}
vector<int> seg, lef(4 * m), rig(4 * m), cnt(4 * m);
auto _add_query = [&](auto &&self, int v, int tl, int tr, int l, int r, int i, int mode) {
if (tr < l || r < tl) {
return;
}
if (l <= tl && tr <= r) {
if (mode == 0) {
cnt[v]++;
} else {
seg[cnt[v]++] = i;
}
return;
}
int tm = (tl + tr) / 2;
self(self, 2 * v, tl, tm, l, r, i, mode);
self(self, 2 * v + 1, tm + 1, tr, l, r, i, mode);
};
auto prepare_query = [&](int l, int r, int i) { _add_query(_add_query, 1, 1, m, l, r, i, 0); };
auto prepare = [&]() {
seg.resize(accumulate(cnt.begin(), cnt.end(), 0));
for (int i = 0, cur_l = 0; i < 4 * m; ++i) {
lef[i] = cur_l, rig[i] = cur_l + cnt[i];
cnt[i] = lef[i];
cur_l = rig[i];
}
};
auto add_query = [&](int l, int r, int i) { _add_query(_add_query, 1, 1, m, l, r, i, 1); };
vector<query> queries;
for (int64_t i = 0, a, b; i < q; ++i) {
cin >> a >> b;
int st = lower_bound(arr.begin() + 1, arr.end(), a + b) - arr.begin();
int en = upper_bound(arr.begin() + 1, arr.end(), b + wait) - arr.begin() - 1;
if (st <= en) {
queries.emplace_back(a, b, st, en, i);
}
}
sort(queries.begin(), queries.end(), [&](const query &a, const query &b) { return a.a > b.a; });
for (int i = 0; i < queries.size(); ++i) {
prepare_query(queries[i].st, queries[i].en, i);
}
prepare();
for (int i = 0; i < queries.size(); ++i) {
add_query(queries[i].st, queries[i].en, i);
}
vector<int64_t> ans(q, -inf);
vector<line> dq(m);
int ptr = 0;
auto process = [&](int v, int tl, int tr) {
ptr = 0;
for (int i = tl; i <= tr; ++i) {
auto compare = [&](const line &l, const line &b, const line &c) {
return (l.b - b.b) * (c.m - l.m) < (l.b - c.b) * (b.m - l.m);
};
while (ptr >= 2 && compare(lines[i], dq[ptr - 1], dq[ptr - 2])) {
ptr--;
}
dq[ptr++] = lines[i];
}
for (int _ = lef[v]; _ < rig[v]; ++_) {
int i = seg[_];
int64_t x = queries[i].a;
while (ptr >= 2 && dq[ptr - 2](x) > dq[ptr - 1](x)) {
ptr--;
}
ans[queries[i].i] = max(ans[queries[i].i], dq[ptr - 1](x));
}
};
auto answer_queries = [&](auto &&self, int v, int tl, int tr) -> void {
if (tl != tr) {
int tm = (tl + tr) / 2;
self(self, 2 * v, tl, tm);
self(self, 2 * v + 1, tm + 1, tr);
}
process(v, tl, tr);
};
answer_queries(answer_queries, 1, 1, m);
for (auto &[a, b, st, en, i] : queries) {
ans[i] = min(en - st + 1, (a * en - b - ans[i]) / a);
}
for (int64_t &i : ans) {
cout << max(i, int64_t(0)) << '\n';
}
}
