#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;
struct line {
ll k, b;
line() {
k = 0; b = 0;
}
line(ll k, ll b) {
this->k = k;
this->b = b;
}
ll get(ll x) {
return k * x + b;
}
};
class convexHull {
public:
void init(int sz) {
d.resize(2 * sz);
l = sz;
r = sz;
}
void addLine(ll k, ll b) {
while(r - l > 1 && (d[r - 2].b - b) * (d[r - 1].k - d[r - 2].k) <= (d[r - 2].b - d[r - 1].b) * (k - d[r - 2].k)) {
r--;
}
d[r++] = {k, b};
}
ll query(ll x) {
while(r - l > 1 && (d[l + 1].b - d[l].b) <= x * (d[l].k - d[l + 1].k)) {
l++;
}
return d[l].get(x);
}
private:
int l, r;
vector < line > d;
};
bool cmpl(line l1, line l2) {
return l1.k > l2.k;
}
ll n, m, l, q;
vector < ll > t;
vector < line > a;
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);
a.resize(m);
for(int i = 0; i < m; i++) {
cin >> t[i];
a[i] = {-i, t[i] + l};
}
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();
ll L = -1, R = ind + 1;
while(R - L > 1) {
ll mid = (L + R) >> 1;
vector < line > tmp;
for(int j = mid; j <= ind; j++) {
tmp.push_back(a[j]);
}
sort(tmp.begin(), tmp.end(), cmpl);
convexHull ch;
ch.init(tmp.size());
for(auto x: tmp) ch.addLine(x.k, x.b);
ll mi = ch.query(x);
if(mi + (mid - 1) * x >= b) R = mid;
else L = mid;
}
res[Q[i].num] = ind + 1 - R;
}
}
for(int i = 0; i < q; i++) {
cout << res[i] << endl;
}
return 0;
}
