#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5 + 5;
struct AIB
{
vector<int> v;
vector<int> upds;
AIB (int siz) : v(siz + 2, 0) {}
void reset()
{
for(int poz:upds)
for(int i=poz;i<v.size();i+=(i&(-i)))
v[i] = 0;
upds.clear();
}
int qry(int poz)
{
assert(poz < v.size());
int aux = 0;
for(int i=poz;i>0;i-=(i&(-i)))
aux += v[i];
return aux;
}
void upd(int poz, int newv)
{
assert(0 < poz && poz < v.size());
upds.push_back(poz);
for(int i=poz;i<v.size();i+=(i&(-i)))
v[i] += newv;
}
};
struct DYNAMIC_AIB
{
const int MAXV = 1e18;
unordered_map<int,int> v;
void reset()
{
v.clear();
}
int qry(int poz)
{
poz = max(poz, 1LL);//--------------------------------------------
int aux = 0;
for(int i=poz;i<MAXV;i+=(i&(-i)))
aux += v[i];
return aux;
}
void upd(int poz, int newv)
{
for(int i=poz;i>0;i-=(i&(-i)))
v[i] += newv;
}
}dyn_aib;
int n, m, L, C;
int a[MAXN], b[MAXN];
int nxt[MAXN], cost_nxt[MAXN];
int tin[MAXN], tout[MAXN], timer, sumr[MAXN], root[MAXN];
vector<pair<int,int>> con[MAXN];
vector<int> updates[MAXN];
bool oncyc[MAXN];
vector<vector<int>> cycles;
void dfs(int nod)
{
tin[nod] = ++timer;
for(auto [adj,w]:con[nod])
{
sumr[adj] = sumr[nod] + w;
root[adj] = root[nod];
dfs(adj);
}
tout[nod] = timer;
}
void build_graph()
{
int full = C / L;
C %= L;
for(int i=1;i<=n;i++)
{
int poz = i, sum = 0;
if(a[i] - a[1] >= C)//we don't cross over 1
{
//a[i] - a[x] >= C
//a[x] <= a[i] - C
poz = (upper_bound(a + 1, a + 1 + n, a[i] - C) - a) - 1;
assert(1 <= poz && poz <= i);
sum = a[i] - a[poz];
assert(sum >= C);
}
else//we cross over 1
{
sum += a[i] - a[1];
sum += a[1] - a[n] + L;
//sum + a[n] - a[x] >= C
//a[x] <= sum + a[n] - C
poz = (upper_bound(a + 1, a + 1 + n, sum + a[n] - C) - a) - 1;
sum += a[n] - a[poz];
assert(sum >= C);
}
nxt[i] = poz;
cost_nxt[i] = sum + full * L;
//cerr<<i<<": "<<nxt[i]<<" "<<cost_nxt[i]<<" nxt & cost\n";
}
int pas = 0;
vector<int> visited(n+2, 0);
for(int i=1;i<=n;i++)
{
if(visited[i])
continue;
pas++;
int cur = i;
while(!visited[cur])
{
visited[cur] = pas;
cur = nxt[cur];
}
if(visited[cur] != pas)
continue;
int init = cur;
vector<int> cyc;
while(1)
{
cyc.push_back(cur);
if(nxt[cur] == init)
break;
cur = nxt[cur];
}
for(int x:cyc)
oncyc[x] = 1;
cycles.push_back(cyc);
}
for(int i=1;i<=n;i++)
{
if(!oncyc[i] || !oncyc[nxt[i]])
{
con[nxt[i]].push_back({i, cost_nxt[i]});
}
}
for(int i=1;i<=n;i++)
{
if(oncyc[i])
{
root[i] = i;
dfs(i);
}
}
}
void add_updates()
{
for(int i=1;i<=m;i++)
{
int poz = lower_bound(a + 1, a + 1 + n, b[i]) - a;
if(poz == 1) poz = n;
else poz--;
int first_time;
if(b[i] > a[poz])
first_time = b[i] - a[poz];
else
first_time = b[i] - a[poz] + L;
updates[poz].push_back(first_time);
//cerr<<i<<": "<<poz<<" "<<first_time<<" first time hit\n";
}
}
int rez[MAXN];
vector<pair<pair<int, int>, int>> tree_queries;//{{node, time}, qid}
void solve_tree_queries()
{
/*for(int i=0;i<tree_queries.size();i++)
{
int nod = tree_queries[i].first.first, t = tree_queries[i].first.second, qid = tree_queries[i].second;
for(int u=1;u<=n;u++)
{
if(tin[nod] <= tin[u] && tin[u] <= tout[nod])
{
for(int upd_t:updates[u])
{
if(upd_t + sumr[u] <= t + sumr[nod])
{
rez[qid]++;
}
}
}
}
}*/
vector<pair<int, pair<int, int>>> events;
for(int u=1;u<=n;u++)
{
for(int upd_t:updates[u])
{
events.push_back({upd_t + sumr[u], {-1, u}});
}
}
for(auto cv:tree_queries)
{
int nod = cv.first.first, t = cv.first.second, qid = cv.second;
events.push_back({t + sumr[nod], {qid, nod}});
}
AIB idk(n);
sort(events.begin(), events.end());
for(auto cv:events)
{
if(cv.second.first == -1)
{
idk.upd(tin[cv.second.second], +1);
}
else
{
int qid = cv.second.first, nod = cv.second.second;
rez[qid] += idk.qry(tout[nod]) - idk.qry(tin[nod] - 1);
}
}
}
vector<pair<pair<int, int>, int>> cycle_queries;//{{node, time}, qid}
void solve_cycle_queries()
{
vector<vector<int>> starts(n+2);
for(int i=1;i<=n;i++)
{
for(int upd_t:updates[i])
{
starts[root[i]].push_back(upd_t + sumr[i]);
}
}
vector<vector<pair<int,int>>> qrys(n+2);//{t, qid}
for(auto cv:cycle_queries)
{
int nod = cv.first.first, t = cv.first.second, qid = cv.second;
qrys[nod].push_back({t, qid});
}
AIB simplu(n);
for(vector<int> cyc:cycles)
{
vector<int> pref(cyc.size() + 2, 0);
for(int i=0;i+1<cyc.size();i++)
{
pref[i+1] = pref[i] + cost_nxt[cyc[i]];
}
int tot = 0;
for(int x:cyc)
tot += cost_nxt[x];
for(int i=0;i<cyc.size();i++)
{
for(auto [t,qid]:qrys[cyc[i]])
{
/*for(int j=0;j<=i;j++)
for(int upd_t:starts[cyc[j]])
if(upd_t - pref[j] <= t - pref[i])
rez[qid]++;*/
/*for(int j=0;j<cyc.size();j++)
for(int upd_t:starts[cyc[j]])
if(upd_t - pref[j] <= t - pref[i] - tot)
{
assert(tot != 0);
int x = (t - pref[i]), y = (pref[j] - upd_t);
//rez[qid] += x / tot;
//rez[qid] += y / tot;
//rez[qid] -= 2;
if((tot + y % tot) >= tot - (tot + x % tot))
rez[qid]++;
if((tot + y % tot) >= 2 * tot - (tot + x % tot))
rez[qid]++;
if((tot + y % tot) >= 3 * tot - (tot + x % tot))
rez[qid]++;
}*/
}
}
vector<pair<int, pair<int, int>>> events;//{time, {tip, val}}
for(int j=0;j<cyc.size();j++)
for(int upd_t:starts[cyc[j]])
events.push_back({upd_t - pref[j], {-1, j}});
for(int i=0;i<cyc.size();i++)
{
for(auto [t,qid]:qrys[cyc[i]])
{
events.push_back({t - pref[i], {qid, i}});
events.push_back({t - pref[i] - tot, {0, qid}});
}
}
sort(events.begin(), events.end());
simplu.reset();
dyn_aib.reset();
int suma_mare = 0;
for(auto cv:events)
{
int tip = cv.second.first;
if(tip == -1)
{
int val = cv.second.second;
simplu.upd(val + 1, +1);
dyn_aib.upd(tot + (-cv.first) % tot, +1);
suma_mare += (-cv.first) / tot;
}
else if(tip == 0)
{
int qid = cv.second.second;
rez[qid] += ((cv.first + tot) / tot - 2) * simplu.qry(n);
rez[qid] += suma_mare;
int me = tot + (cv.first + tot) % tot;
rez[qid] += dyn_aib.qry(tot - me);
rez[qid] += dyn_aib.qry(2 * tot - me);
rez[qid] += dyn_aib.qry(3 * tot - me);
}
else
{
int qid = cv.second.first, val = cv.second.second;
rez[qid] += simplu.qry(val + 1);
}
}
}
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m>>L>>C;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=m;i++)
cin>>b[i];
build_graph();
add_updates();
int q;
cin>>q;
for(int i=1;i<=q;i++)
{
int v, t;
cin>>v>>t;
if(oncyc[v])
{
cycle_queries.push_back({{v, t}, i});
}
else
{
tree_queries.push_back({{v, t}, i});
}
}
solve_tree_queries();
solve_cycle_queries();
for(int i=1;i<=q;i++)
cout<<rez[i]<<"\n";
return 0;
}
