#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
#define ff first
#define ss second
#define pi pair<ll, ll>
#define pll pair<long long, long long>
#define vi vector<ll>
#define vll vector<long long>
#define vpi vector<pair<ll,ll>>
#define vpll vector<pair<long long, long long>>
#define pb push_back
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define forall(it,x) for(auto& it:(x))
#define mp make_pair
pi operator+(pi a, pi b) { return mp(a.ff+b.ff, a.ss+b.ss); }
pi operator-(pi a, pi b) { return mp(a.ff-b.ff, a.ss-b.ss); }
#pragma GCC optimize("O3,unroll-loops")
#ifdef _WIN32
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endif
inline ll readint() {
char c = getchar_unlocked();
while((c < '0' || c > '9') && c != '-') c = getchar_unlocked();
bool neg = false;
if(c == '-') neg = true, c = getchar_unlocked();
ll res = 0;
while(c >= '0' && c <= '9') res = res * 10 + c - '0', c = getchar_unlocked();
return neg? -res : res;
}
char _buf[40];
inline void printint(ll n) {
if(n == 0) putchar_unlocked('0');
if(n < 0) putchar_unlocked('-'), n = -n;
ll i = 0;
for(; n > 0; n /= 10) _buf[i++] = n % 10 + '0';
while(i--) putchar_unlocked(_buf[i]);
putchar_unlocked('\n');
}
ll inf = 8e18 + 100;
ll base = 1;
ll sufit(ll a, ll b) {
if (b < 0) a = -a, b = -b;
return (a + b - 1) / b;
}
struct CHT {
vector<pair<ll, pair<ll, ll>>> hull;
ll cross(pair<ll, ll> x, pair<ll, ll> y) {
auto[a,b] = x;
auto[c,d] = y;
return sufit(d-b, a-c);
}
void add_funk(pair<ll, ll> ff) {
auto[a,b] = ff;
while(hull.size()) {
auto &x = hull.back();
auto cr = cross({a,b}, x.second);
if(cr < x.first) hull.pop_back();
else {
hull.push_back({cr, {a,b}});
break;
}
}
if(hull.empty()) {
hull.push_back({-1,{a,b}});
}
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n=readint();
ll m=readint();
ll L=readint();
ll q=readint();
vector<ll> T(m);
for(ll i=0; i<m; ++i) {
T[i]=readint();
T[i] += L;
}
vector<ll> A(q), B(q);
for(ll i=0; i<q; ++i) {
A[i]=readint();
B[i]=readint();
}
vector<ll> M(q, -inf);
//Build
base = 1;
while(base < m) base <<= 1;
vector<vector<int>> childs(2*base);
for(ll i=0; i<m; ++i) {
ll x = i+base;
while(x > 0) {
childs[x].pb(i);
x/=2;
}
}
vector<vector<int>> odp(2*base);
//Query
vector<pair<ll, int>> S;
for(ll i=0; i<q; ++i) S.pb({A[i], i});
sort(all(S));
for(auto[useless, idx] : S) {
ll a = lower_bound(all(T), B[idx]) - T.begin();
ll b = upper_bound(all(T), B[idx] + L) - T.begin() - 1;
if(a > b) continue;
if(a==b) {
odp[a+base].pb(idx);
continue;
}
a+=base-1;
b+=base+1;
while(a/2 != b/2) {
if(a%2==0) odp[a+1].pb(idx);
if(b%2==1) odp[b-1].pb(idx);
a/=2; b/=2;
}
}
for(int i=1; i<2*base; ++i) {
CHT cht;
for(auto idx : childs[i]) {
cht.add_funk(mp(idx, -T[idx]));
}
int pt = 0;
for(auto idx : odp[i]) {
ll X = A[idx];
while(pt + 1 < (ll)cht.hull.size() && X >= cht.hull[pt + 1].ff) {
pt++;
}
ll val = cht.hull[pt].ss.ff * X + cht.hull[pt].ss.ss;
M[idx] = max(M[idx], val);
}
cht.hull.clear();
}
for(ll t=0; t<q; ++t) {
ll cnt = upper_bound(all(T), B[t] + L) - lower_bound(all(T), B[t]);
ll ile_lower = lower_bound(all(T), B[t]) - T.begin();
M[t] += B[t] + A[t] - 1;
M[t] += A[t]*(1 - ile_lower);
M[t] = max(0LL, M[t]);
M[t] /= A[t];
ll O = max(0LL, cnt - M[t]);
printint(O);
}
return 0;
}
