#include <iostream>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define os tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
#define ll long long
const ll N = (1<<19) + 1;
os seg[N<<1], st[N>>1];
ll segSum[N<<1], vl[N], v[N], Nxt[N], Len[N], deg[N], Ans[N], a[N];
vector<pair<ll, ll>> Quer[N];
vector<ll> vc;
multiset<pair<ll, ll>> ms;
ll n, m, l, c, q, Add;
void insert(ll i, ll v1, ll v2, ll tp, ll cur = 1, ll st = 1, ll en = N){
// if (cur == 1)
// cout<<i<<" "<<v1<<" "<<v2<<" "<<tp<<" "<<Add<<endl;
if (i >= en or i < st)
return;
if (tp == 1)
seg[cur].insert(v2 - Add), segSum[cur] += v1;
else{
// cout<<(*seg[cur].upper_bound(v2 - Add - 1))<<' ';
// if (seg[cur].find(6) != seg[cur].end())
// cout<<" ha ";
seg[cur].erase(seg[cur].upper_bound(v2 - Add - 1)), segSum[cur] -= v1;
}
// cout<<"updating "<<cur<<" :: ";
// for (ll j : seg[cur])
// cout<<j + Add<<' ';
// cout<<endl;
if (en - st == 1)
return;
ll lc = cur << 1, rc = lc | 1, mid = (st + en) >> 1;
insert(i, v1, v2, tp, lc, st, mid);
insert(i, v1, v2, tp, rc, mid, en);
}
ll get(ll K, ll l, ll r, ll r1, ll cur = 1, ll st = 1, ll en = N){ // x + add <= r1
// if (cur == 1)
// cout<<" here is a get "<<K<<" "<<r1<<" "<<endl;
if (l >= en or r <= st)
return 0;
if (l <= st and r >= en){
// cout<<st<<" "<<en<<" "<<cur<<" "<<K<<" "<<r1<<" "<<seg[cur].size()<<endl;
return K * seg[cur].size() - segSum[cur] + seg[cur].order_of_key(r1 - Add + 1);
}
ll lc = cur << 1, rc = lc | 1, mid = (st + en) >> 1;
return get(K, l, r, r1, lc, st, mid) + get(K, l, r, r1, rc, mid, en);
}
void Clear(ll cur = 1, ll st = 1, ll en = N){
if (seg[cur].size() == 0)
return;
seg[cur].clear();
segSum[cur] = 0;
if (en - st == 1)
return;
ll lc = cur << 1, rc = lc | 1, mid = (st + en) >> 1;
Clear(lc, st, mid);
Clear(rc, mid, en);
}
ll getId(ll u){
return upper_bound(begin(vc), end(vc), u) - begin(vc);
}
void Print(){
return;
for (ll i=1;i<=15;i++){
cout<<i<<"-th node :: ";
for (ll j : seg[i])
cout<<j + Add<<' ';
cout<<endl;
}
}
void solveCycle(ll vr){
// cout<<"solve Cycle containing "<<vr<<endl;
ll s = 0, Cl = 0;
for (ll i=0; vr != v[0];i++){
v[i] = vr;
s++, Cl += Len[vr];
vr = Nxt[vr];
deg[v[i]] = 0;
}
for (ll i=0;i<s;i++){
for (auto [T, id] : Quer[v[i]])
vc.push_back(T / Cl), vc.push_back(T / Cl - 1);
for (ll j : st[v[i]]){
ll T = j + vl[v[i]];
vc.push_back(T / Cl), vc.push_back(T / Cl + 1);
}
}
sort(begin(vc), end(vc));
vc.resize(unique(begin(vc), end(vc)) - begin(vc));
for (ll i=s-1, sum = 0;i>=0;i--){
sum += Len[v[i]];
for (ll j : st[v[i]]){
ll T = j + vl[v[i]] + sum;
ll k = T / Cl, r = T % Cl;
insert(getId(k), k, r, 1);
ms.insert({r, k});
// cout<<v[i]<<" "<<j<<" "<<sum<<" "<<vl[v[i]]<<endl;
}
}
// return;
// cout<<Cl<<endl;
for (ll i=0;i<s;i++){
// cout<<endl<<endl<<endl<<v[i]<<endl;
// for (auto [l, r] : ms)
// cout<<r<<" "<<l + Add<<'\n';
for (ll j : st[v[i]]){
ll T = j + vl[v[i]];
ll k = T / Cl, r = T % Cl;
ms.erase(ms.find({r - Add, k + 1}));
ms.insert({r - Add, k});
insert(getId(k+1), k+1, r, -1);
insert(getId(k), k, r, 1);
}
// cout<<v[i]<<endl;
// for (auto [l, r] : ms)
// cout<<r<<" "<<l + Add<<'\n';
Print();
for (auto [T, id] : Quer[v[i]]){
// cout<<" look here lookkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk "<<i<<" "<<T<<" "<<id<<endl;
ll k = T / Cl, r = T % Cl, j = getId(k);
// cout<<id<<" "<<k<<" "<<r<<" "<<j<<endl;
Ans[id] = get(k, 1, j, r);
Ans[id] += seg[j + N - 2].order_of_key(r - Add + 1);
}
Add += Len[v[i]];
while (ms.size() > 0 and (*rbegin(ms)).first + Add >= Cl){
auto [r, k] = *rbegin(ms);
ms.erase(prev(end(ms)));
r += Add;
insert(getId(k), k, r, -1);
insert(getId(k+1), k+1, r - Cl, 1);
ms.insert({r - Cl - Add, k+1});
}
}
Clear();
ms.clear();
Add = 0;
vc.clear();
// cout<<"done with this one"<<endl;
}
void solvePart2(){
for (ll i=1;i<=n;i++){
if (deg[i] == 1){
solveCycle(i);
}
}
}
int main(){
cin>>n>>m>>l>>c;
for (ll i=1;i<=n;i++)
cin>>a[i], a[i+n] = l + a[i];
for (ll i=n+1, it = 1;i<=n+n;i++){
ll k = c % l;
while (a[i] - a[it+1] >= k)
it++;
Nxt[i - n] = it - n * (it > n);
deg[Nxt[i - n]]++;
Len[i - n] = a[i] - a[it] + (c / l) * l;
// cout<<i - n<<" "<<Nxt[i - n]<<" "<<Len[i - n]<<'\n';
}
for (ll i=1, it = 0, b;i<=m;i++){
cin>>b;
while (a[it+1] <= b)
it++;
if (it == 0)
st[n].insert(l - a[n] + b);//, cout<<i + 10<<" "<<n<<" "<<l - a[n] + b<<endl;
else
st[it].insert(b - a[it]);//, cout<<i + 10<<" "<<it<<" "<<b - a[it]<<endl;
}
// cout<<"done1"<<endl;
cin>>q;
for (ll i=1;i<=q;i++){
ll id, T;
cin>>id>>T;
Quer[id].push_back({T, i});
}
vector<ll> lfs;
for (ll i=1;i<=n;i++){
if (deg[i] == 0)
lfs.push_back(i);
// cout<<i<<" "<<deg[i]<<endl;
}
// cout<<"done"<<endl;
while (lfs.size() > 0){
int i = lfs.back();
lfs.pop_back();
// cout<<"done with "<<i<<endl;
for (auto [T, id] : Quer[i])
Ans[id] = st[i].order_of_key(T - vl[i]);
ll j = Nxt[i];
vl[i] += Len[i];
if (st[j].size() < st[i].size())
swap(st[i], st[j]), swap(vl[i], vl[j]);
for (ll k : st[i])
st[j].insert(k + vl[i] - vl[j]);
deg[j]--;
if (deg[j] == 0)
lfs.push_back(j);
}
// cout<<"don3"<<endl;
solvePart2();
// return 0;
// cout<<"done4"<<endl;
for (ll i=1;i<=q;i++)
cout<<Ans[i]<<'\n';
}
