#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef long double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds2;
vi people;
vi apple;
int timer=0;
int to[222222];
ll w[222222];
vector<ll> apples[222222];
int n,m; ll L,C;
ll D(ll x, ll y)
{
if(x<=y) return y-x;
return L-(x-y);
}
vector<vi> cycles;
int visited[222222];
int iscyc[222222];
set<int> path;
void getcycles(int u)
{
//cerr<<u<<' '<<visited[u]<<'\n';
if(visited[u]==2)
{
iscyc[u]=1; cycles.back().pb(u);
}
path.insert(u);
if(visited[to[u]]>0&&path.find(to[u])==path.end())
{
visited[u]=1; return ;
}
if(visited[to[u]]==2) return ;
if(visited[to[u]]==1)
{
if(visited[u]==1) cycles.pb({});
visited[to[u]]=2;
getcycles(to[u]);
return ;
}
//unvisited
visited[to[u]]=1;
getcycles(to[u]);
}
vi T[222222]; //tree edges
pbds* A[222222]; //debug
ll shift[222222];
ll ans[222222];
vi adj[222222];
int subsize[222222];
void dfs(int u, int p=-1)
{
subsize[u]=1;
for(int v:adj[u])
{
if(iscyc[v]) continue;
if(v==p) continue;
T[u].pb(v);
dfs(v,u);
subsize[u]+=subsize[v];
}
}
vector<pair<ll,int> > queries[222222];
void getA(int u, int p=-1)
{
//for(ll x:apples[u]) A[u].insert({x,++timer}); //later change to dsu on tree
if(T[u].empty())
{
A[u] = new pbds;
}
for(int v:T[u])
{
getA(v,u);
if(v==T[u][0])
{
A[u]=A[v];
shift[u]=shift[v]+w[v];
}
else
{
while(!A[v]->empty())
{
ii x = *(A[v]->begin());
A[v]->erase(A[v]->begin());
A[u]->insert({x.fi+shift[v]+w[v]-shift[u],x.se});
}
}
}
for(ll x:apples[u]) A[u]->insert({x-shift[u],++timer});
if(iscyc[u]) return ;
for(ii x:queries[u])
{
int z = x.se; ll t = x.fi;
//cerr<<"HERE "<<z<<' '<<A[u]->order_of_key({t+1-shift[u],-1})<<'\n';
ans[z] = A[u]->order_of_key({t+1-shift[u],-1});
}
}
ll flr(ll a, ll b)
{
if(a>=0) return a/b;
else return -((abs(a)+b-1)/b);
}
ll md(ll a, ll b)
{
a%=b;
if(a<0) a+=b;
return a;
}
ll ans2[222222];
struct Fenwick
{
vector<ll> t;
Fenwick(int n)
{
t.assign(n+1,0);
}
void reset(int n)
{
t.assign(n+1, 0);
}
void update(int p, ll v)
{
for (; p < (int)t.size(); p += (p&(-p))) t[p] += v;
}
ll query(int r) //finds [1, r] sum
{
ll sum = 0;
for (; r; r -= (r&(-r))) sum += t[r];
return sum;
}
ll query(int l, int r) //finds [l, r] sum
{
if(l == 0) return query(r);
return query(r) - query(l-1);
}
};
pbds2 st[810111];
vi affected;
int mx[810111];
void update(int id, int l, int r, int pos, int v)
{
if(pos>=r||pos<l) return ;
if(v>mx[id]) mx[id]=v;
affected.pb(id);
st[id].insert(v);
if(r-l<2) return ;
int mid=(l+r)>>1;
update(id*2,l,mid,pos,v); update(id*2+1,mid,r,pos,v);
}
int query(int id, int l, int r, int ql, int qr, int v) //# of elements >= v
{
if(ql>=r||l>=qr) return 0;
if(v>mx[id]) return 0;
if(ql<=l&&r<=qr) return st[id].size()-st[id].order_of_key(v);
int mid=(l+r)>>1;
return query(id*2,l,mid,ql,qr,v)+query(id*2+1,mid,r,ql,qr,v);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
const bool DEBUG=0;
srand(12345);
for(int cc=1;;cc++)
{
n=m=L=C=0;
if(!DEBUG) cin>>n>>m>>L>>C;
people.clear(); apple.clear();
if(DEBUG)
{
while(n==0)
{
people.clear(); apple.clear();
L=20;
int l1 = rand()%1000;
int l2 = rand()%1000;
if(l1>l2) swap(l1,l2);
for(int i=0;i<10;i++)
{
int p = rand()%1000;
if(p<=l1) people.pb(i);
else if(p<=l2) apple.pb(i);
}
n=people.size(); m=apple.size();
C=rand()%10+1;
}
}
if(!DEBUG)
{
for(int i=0;i<n;i++)
{
ll x; cin>>x;
people.pb(x);
}
for(int i=0;i<m;i++)
{
ll x; cin>>x;
apple.pb(x);
}
}
//build the graph
cycles.clear();
for(int i=0;i<n;i++)
{
adj[i].clear();T[i].clear();w[i]=0;to[i]=0;visited[i]=0;iscyc[i]=0;
shift[i]=0;
subsize[i]=0;
apples[i].clear();
queries[i].clear();
A[i]=NULL;
}
for(int i=0;i<n;i++)
{
ll curx = people[i];
curx-=C;
curx%=L;
if(curx<0) curx+=L;
//first person that is <= curx gets it
int ub = upper_bound(people.begin(),people.end(),curx)-people.begin();
ub--;
if(ub<0)
{
ub=int(people.size())-1;
}
//ub is the person you want
//compute the length now
ll dist = 0;
if(ub<=i) dist = people[i]-people[ub];
else dist = L-(people[ub]-people[i]);
//we want dist >= C
if(dist<C)
{
ll diff = C-dist;
dist+=((diff+L-1)/L)*L; //ceil(diff/L)*L
}
w[i]=dist;
to[i]=ub;
adj[i].pb(to[i]);
adj[to[i]].pb(i);
//cerr<<i<<' '<<to[i]<<' '<<w[i]<<'\n';
}
for(int i=0;i<m;i++)
{
ll pos = apple[i];
int ub = upper_bound(people.begin(),people.end(),pos)-people.begin();
ub--;
if(ub<0)
{
ub=int(people.size())-1;
}
ll dist = D(people[ub],apple[i]);
apples[ub].pb(dist);
}
//get the cycles
for(int i=0;i<n;i++)
{
if(!visited[i])
{
path.clear();
getcycles(i);
}
}
//all cycles are stored now
//get the trees
vector<ii> QQ;
int q;
if(!DEBUG) cin>>q;
else
{
if(n==0) q=0;
else q = rand()%50+1;
}
for(int i=0;i<q;i++) ans[i]=ans2[i]=0;
for(int z=0;z<q;z++)
{
int p; ll t;
if(!DEBUG)
{
cin>>p>>t;
p--;
}
else
{
p=rand()%n;
t=rand()%50+1;
}
if(DEBUG)
{
vi curpos=people;
vi nxtapple(L,ll(1e18)+10);
for(int i=0;i<m;i++)
{
nxtapple[apple[i]]=0;
}
ll ans=0;
for(ll i=0;i<t;i++)
{
for(int i=0;i<n;i++)
{
curpos[i]++;
if(curpos[i]>=L) curpos[i]-=L;
}
for(int j=0;j<n;j++)
{
if(nxtapple[curpos[j]]<=i)
{
if(j==p) ans++;
nxtapple[curpos[j]]=i+C;
}
}
}
ans2[z]=ans;
QQ.pb({p,t});
}
queries[p].pb({t,z});
}
for(int i=0;i<n;i++)
{
if(iscyc[i])
{
dfs(i);
}
}
for(int i=0;i<n;i++)
{
for(ll &v:T[i])
{
if(subsize[v]>subsize[T[i][0]])
{
swap(v,T[i][0]);
}
}
}
//let's check if it works first
//naively push everything from the trees?
//later optimize to dsu on tree
for(int i=0;i<n;i++)
{
if(iscyc[i])
{
getA(i);
}
}
//stuff on tree, use dsu on tree
/*
for(int i=0;i<n;i++)
{
cerr<<i<<' '<<shift[i]<<'\n';
for(ii x:(*A[i])) cerr<<x.fi<<'\n';
}
*/
//stuff on cycle, store 2 sets bruh
for(int i=0;i<cycles.size();i++)
{
vi cyc = cycles[i];
ll cyclen = 0;
for(int nd:cyc) cyclen+=w[nd];
vector<pair<ll,ll> > mods;
vector<ll> coords;
{
ll curw = 0;
for(int j=0;j<cyc.size();j++)
{
for(ii x:(*A[cyc[j]]))
{
coords.pb(x.fi+shift[cyc[j]]-curw);
mods.pb({md(x.fi+shift[cyc[j]]-curw,cyclen),x.se});
}
curw+=w[cyc[j]];
}
}
{
ll curw = cyclen;
for(int j=int(cyc.size())-1;j>0;j--)
{
curw-=w[cyc[j]];
for(ii x:(*A[cyc[j]])) mods.pb({md(x.fi+shift[cyc[j]]-curw+cyclen,cyclen),x.se});
}
}
sort(mods.begin(),mods.end());
mods.erase(unique(mods.begin(),mods.end()),mods.end());
sort(coords.begin(),coords.end());
coords.erase(unique(coords.begin(),coords.end()),coords.end());
Fenwick fen(coords.size()+10);
Fenwick fen2(coords.size()+10);
{
vector<ll> V;
ll curw = 0;
for(int j=0;j<cyc.size();j++)
{
for(ii x:(*A[cyc[j]]))
{
int id = lower_bound(coords.begin(),coords.end(),x.fi+shift[cyc[j]]-curw)-coords.begin();
fen.update(id+1,flr(x.fi+shift[cyc[j]]-curw,cyclen));
fen2.update(id+1,1);
//cerr<<"INSERT "<<x.fi-curw<<' '<<id<<' '<<flr(x.fi-curw,cyclen)<<' '<<md(x.fi-curw,cyclen)<<'\n';
int lb = lower_bound(mods.begin(),mods.end(),mp(md(x.fi+shift[cyc[j]]-curw,cyclen),x.se))-mods.begin();
update(1,0,int(coords.size()),id,lb);
}
//V.pb(x.fi-curw);
for(ii qry:queries[cyc[j]])
{
int lab = qry.se;
ll T = qry.fi;
T-=curw;
int id = upper_bound(coords.begin(),coords.end(),T)-coords.begin();
id--;
if(id>=0)
{
int ub = upper_bound(mods.begin(),mods.end(),mp(md(T,cyclen)+1,-1LL))-mods.begin();
ans[lab]+=(flr(T,cyclen)+1)*1LL*fen2.query(id+1) - fen.query(id+1) - query(1,0,int(coords.size()),0,id+1,ub);
}
}
curw+=w[cyc[j]];
}
//fen = Fenwick(coords.size()+10);
//fen2 = Fenwick(coords.size()+10);
}
for(int nd:affected){mx[nd]=0; st[nd].clear();}
affected.clear();
coords.clear();
{
ll curw = cyclen;
for(int j=int(cyc.size())-1;j>0;j--)
{
curw-=w[cyc[j]];
for(ii x:(*A[cyc[j]])) coords.pb(x.fi+shift[cyc[j]]-curw+cyclen);
}
}
sort(coords.begin(),coords.end());
coords.erase(unique(coords.begin(),coords.end()),coords.end());
fen = Fenwick(coords.size()+10);
fen2 = Fenwick(coords.size()+10);
{
vector<ll> V;
ll curw = cyclen;
for(int j=int(cyc.size())-1;j>0;j--)
{
curw-=w[cyc[j]];
for(ii x:(*A[cyc[j]]))
{
int id = lower_bound(coords.begin(),coords.end(),x.fi+shift[cyc[j]]-curw+cyclen)-coords.begin();
fen.update(id+1,flr(x.fi+shift[cyc[j]]-curw+cyclen,cyclen));
fen2.update(id+1,1);
int lb = lower_bound(mods.begin(),mods.end(),mp(md(x.fi+shift[cyc[j]]-curw+cyclen,cyclen),x.se))-mods.begin();
//cerr<<"INSERT "<<x.fi-curw+cyclen<<' '<<id<<' '<<flr(x.fi-curw+cyclen,cyclen)<<' '<<md(x.fi-curw+cyclen,cyclen)<<'\n';
update(1,0,int(coords.size()),id,lb);
}
for(ii qry:queries[cyc[j-1]])
{
int lab = qry.se;
ll T = qry.fi;
T-=curw-w[cyc[j-1]];
int id = upper_bound(coords.begin(),coords.end(),T)-coords.begin();
id--;
if(id>=0)
{
//cerr<<lab<<' '<<"T: "<<T<<' '<<(flr(T,cyclen)+1)*1LL*fen2.query(id+1) - fen.query(id+1) - query(1,0,int(coords.size()),0,id+1,md(T,cyclen))<<'\n';
//cerr<<query(1,0,int(coords.size()),0,id+1,md(T,cyclen))<<' '<<fen2.query(id+1)<<' '<<fen.query(id+1)<<'\n';
int ub = upper_bound(mods.begin(),mods.end(),mp(md(T,cyclen)+1,-1LL))-mods.begin();
ans[lab]+=(flr(T,cyclen)+1)*1LL*fen2.query(id+1) - fen.query(id+1) - query(1,0,int(coords.size()),0,id+1,ub);
}
/*
for(ll x:V)
{
if(T>=x) ans[lab]+=flr(T,cyclen) - flr(x,cyclen) - (md(T,cyclen)<md(x,cyclen)) + 1;
}
*/
}
}
}
for(int nd:affected) {mx[nd]=0;st[nd].clear();}
affected.clear();
}
if(!DEBUG)
{
for(int z=0;z<q;z++)
{
cout<<ans[z]<<'\n';
}
return 0;
}
for(int z=0;z<q;z++)
{
if(ans2[z]!=ans[z])
{
cerr<<"FAIL AT "<<z<<" ans = "<<ans[z]<<" ans2 = "<<ans2[z]<<'\n';
freopen("harvest-fail.out","w",stdout);
cout<<n<<' '<<m<<' '<<L<<' '<<C<<'\n';
for(int i=0;i<n;i++) cout<<people[i]<<' ';
cout<<'\n';
for(int i=0;i<m;i++) cout<<apple[i]<<' ';
cout<<'\n';
cout<<q<<'\n';
for(ii x:QQ) cout<<x.fi+1<<' '<<x.se<<'\n';
return 0;
}
}
cerr<<"Case #"<<cc<<" complete\n";
}
}
