#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
long long floor_div(long long a, long long b) { // integer floor division
return (a / b) - ((a ^ b) < 0 && a % b);
}
namespace Treap {
struct TreapNode {
int prior, sz;
long long value, lazy = 0;
TreapNode *l, *r;
TreapNode(long long v = 0) : prior(rnd()), sz(1), value(v), l(NULL), r(NULL) {}
};
using pt = TreapNode*;
int sz(pt t) { return t ? t->sz : 0; }
void upd(pt t) { if (t) t->sz = sz(t->l) + sz(t->r) + 1; }
void apply(pt t, long long x) { if (t) t->value += x, t->lazy += x; }
void push(pt t) {
if (!t) return;
apply(t->l, t->lazy);
apply(t->r, t->lazy);
t->lazy = 0;
}
void split(pt t, pt &l, pt &r, long long key) { // l will have all values <= key
push(t);
if (!t) {
l = r = NULL;
} else if (t->value > key) {
split(t->l, l, t->l, key), r = t;
} else {
split(t->r, t->r, r, key), l = t;
}
upd(t);
}
void merge(pt &t, pt l, pt r) {
push(l), push(r);
if (!l || !r) {
t = l ? l : r;
} else if (l->prior > r->prior) {
merge(l->r, l->r, r), t = l;
} else {
merge(r->l, l, r->l), t = r;
}
upd(t);
}
void erase(pt t, long long x) {
push(t);
if (!t) return;
if (t->value > x) {
erase(t->l, x);
} else if (t->value < x) {
erase(t->r, x);
} else if (t->value == x) {
pt to_be_del = t;
merge(t, t->l, t->r);
delete to_be_del;
}
upd(t);
}
void clear(pt t) {
if (!t) return;
clear(t->l);
clear(t->r);
t = NULL;
delete t;
}
void get(pt t, vector<long long> &res) {
push(t);
if (!t) return;
get(t->l, res);
res.emplace_back(t->value);
get(t->r, res);
}
void update(pt &root, long long x) { // increase all elements in treap by x under modulo mod
pt l, r;
apply(root, x);
}
void insert(pt &root, long long x) {
pt l, r;
split(root, l, r, x);
merge(l, l, new TreapNode(x));
merge(root, l, r);
}
vector<long long> get(pt root) {
vector<long long> res;
get(root, res);
return res;
}
int order_of_key(pt &root, long long x) { // find number of values <= x
pt l, r;
int res;
split(root, l, r, x);
res = sz(l);
merge(root, l, r);
return res;
}
pt unite(pt l, pt r) {
push(l), push(r);
if (!l) return r;
if (!r) return l;
if (l->prior < r->prior) swap(l, r);
pt lt, rt;
split(r, lt, rt, l->value);
l->l = unite(l->l, lt);
l->r = unite(l->r, rt);
upd(l);
return l;
}
}
int N, M, L, C;
vector<int> A, B;
vector<int> next_vertex; // next vertex A[] after a tree has just finished visited A[i] and gave it an apple
vector<int> next_distance; // distance to next_vertex (time needed)
vector<int> first_vertex; // first vertex that tree[] meets
vector<int> first_distance; // the distance in time
vector<bool> in_cycle; // whether a vertex v is part of a cycle or not
vector<long long> cycle_length; // the length of a cycle vertex v is part of
vector<int> cycle_start; // the start of the cycle, where pos[start] = 0
vector<long long> pos_in_cycle; // the positions / distance
namespace Naive { // O(N^2 log N) solution, unoptimized version of the main ideas for full solution
vector<multiset<long long>> meeting_time; // first time a vertex meets certain trees under modulo len
vector<long long> initial_overflow; // sum of all floor(i / len) for meeting_time (the original value)
void NaiveGetMeetingTime() { // Naive O(N^2 log N)
meeting_time.resize(N);
for (int ci = 0; ci < M; ci++) {
int v = first_vertex[ci];
long long len = first_distance[ci];
vector<bool> vis(N, false);
do {
vis[v] = true;
meeting_time[v].emplace(len);
len += next_distance[v];
v = next_vertex[v];
} while (!vis[v]);
}
}
long long NaiveQuery(int V, long long T) {
if (!in_cycle[V]) {
int lb = 0; // lower bound, will be implemented later
for (auto &i : meeting_time[V]) {
if (i <= T) lb++;
}
return lb;
}
// V is in a cycle
long long len = cycle_length[V];
long long res = 0;
for (auto &i : meeting_time[V]) {
long long cur = floor_div(T, len) - floor_div(i, len) + ((i % len) <= (T % len)); // equivalent to div(T - i, len) + 1
res += max(cur, 0ll);
}
return res;
}
}
void BuildGraph() {
{ // build initial graph
next_vertex.resize(N);
next_distance.resize(N);
for (int i = 0; i < N; i++) {
int next_loc = (A[i] - C) % L; // go counter clockwise
if (next_loc < 0) next_loc += L;
if (next_loc < A[0]) next_loc += L;
next_vertex[i] = upper_bound(begin(A), end(A), next_loc) - begin(A) - 1;
next_distance[i] = C + (next_loc - A[next_vertex[i]]);
}
first_vertex.resize(M);
first_distance.resize(M);
for (int i = 0; i < M; i++) {
int next_loc = B[i]; // go counter clockwise
if (next_loc < A[0]) next_loc += L;
first_vertex[i] = upper_bound(begin(A), end(A), next_loc) - begin(A) - 1;
first_distance[i] = (next_loc - A[first_vertex[i]]);
}
}
{ // find information about the cycles
int mark = 0;
vector<int> vis(N, 0);
in_cycle.resize(N, false);
cycle_length.resize(N, -1);
cycle_start.resize(N, -1);
pos_in_cycle.resize(N, -1);
auto Calc = [&](int i) {
mark++;
int cur = i;
do {
vis[cur] = mark;
cur = next_vertex[cur];
} while (!vis[cur]);
if (vis[cur] != mark) { // this cycle is already processed before
return;
}
int st = cur;
long long len = 0;
do {
cycle_start[cur] = st;
pos_in_cycle[cur] = len;
in_cycle[cur] = true;
len += next_distance[cur];
cur = next_vertex[cur];
} while (cur != st);
cycle_length[cur] = len;
};
// process cycles
for (int i = 0; i < N; i++) {
if (vis[i]) continue;
Calc(i);
}
}
}
vector<long long> answer;
vector<vector<pair<long long, int>>> query; // query[V] = (T, query_index)
vector<vector<long long>> first_meeting_cycle; // first time trees meet a cycle (time)
vector<vector<long long>> first_meeting_tree; // first time trees meet a non-cucle (which musy be a tree) (time)
void SolveTree() { // also solves the case for broken cycle
vector<vector<int>> adj(N);
for (int i = 0; i < N; i++) {
if (in_cycle[i] && cycle_start[i] == next_vertex[i]) continue; // the edge to be cut in a broken cycle
if (!in_cycle[i] && in_cycle[next_vertex[i]]) continue;
adj[next_vertex[i]].emplace_back(i);
}
vector<Treap::pt> treap(N, NULL);
function<void(int)> dfs = [&](int cur) {
for (auto &nxt : adj[cur]) {
dfs(nxt);
treap[cur] = unite(treap[cur], treap[nxt]);
}
for (auto &nw : first_meeting_tree[cur]) {
Treap::insert(treap[cur], nw);
}
for (auto &q : query[cur]) {
answer[q.second] = Treap::order_of_key(treap[cur], q.first);
}
Treap::update(treap[cur], next_distance[cur]);
};
// calculate answer for tree part
for (int i = 0; i < N; i++) {
if (!in_cycle[i] && in_cycle[next_vertex[i]]) {
dfs(i);
// next_vertex is now part of a cycle
vector<long long> elements = Treap::get(treap[i]);
Treap::clear(treap[i]);
for (auto &e : elements) {
first_meeting_cycle[next_vertex[i]].emplace_back(e);
first_meeting_tree[next_vertex[i]].emplace_back(e);
}
}
}
// calculate contribution of broken cycle
for (int i = 0; i < N; i++) {
if (in_cycle[i] && cycle_start[i] == next_vertex[i]) {
dfs(i);
Treap::clear(treap[i]);
}
}
}
void SolveCycle(int r) { // solves the case for cycles, excluding the broken cycle case
long long initial_overflow = 0;
long long len = cycle_length[r];
int cur = r;
Treap::pt treap = NULL;
vector<long long> all_meeting_time;
vector<pair<long long, int>> all_queries; // pair of (T - pos[orginal_position], query_id)
do {
for (auto &nw : first_meeting_cycle[cur]) {
long long distance = nw + (len - pos_in_cycle[cur]);
all_meeting_time.emplace_back(distance);
}
for (auto &q : query[cur]) {
all_queries.emplace_back(q.first - pos_in_cycle[cur], q.second);
}
cur = next_vertex[cur];
} while (cur != r);
sort(begin(all_meeting_time), end(all_meeting_time), greater<long long>());
sort(begin(all_queries), end(all_queries));
for (auto &q : all_queries) {
while (!all_meeting_time.empty() && all_meeting_time.back() <= q.first) {
Treap::insert(treap, all_meeting_time.back() % len);
initial_overflow += floor_div(all_meeting_time.back(), len);
all_meeting_time.pop_back();
}
answer[q.second] += 1ll * floor_div(q.first, len) * Treap::sz(treap) - initial_overflow + Treap::order_of_key(treap, q.first % len);
}
Treap::clear(treap);
}
void SolveCycle() {
for (int i = 0; i < N; i++) {
if (in_cycle[i] && cycle_start[i] == i) {
SolveCycle(i);
}
}
}
void SolveQuery() {
first_meeting_cycle.resize(N);
first_meeting_tree.resize(N);
for (int i = 0; i < M; i++) {
int v = first_vertex[i];
if (in_cycle[v]) {
first_meeting_cycle[v].emplace_back(first_distance[i]);
first_meeting_tree[v].emplace_back(first_distance[i]);
} else {
first_meeting_tree[v].emplace_back(first_distance[i]);
}
}
SolveTree();
SolveCycle();
}
void Solve() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N >> M >> L >> C;
A.resize(N), B.resize(M);
for (auto &i : A) cin >> i;
for (auto &i : B) cin >> i;
int Q;
cin >> Q;
answer.resize(Q, -1);
query.resize(N);
for (int i = 0; i < Q; i++) {
int V; long long T;
cin >> V >> T;
query[--V].emplace_back(T, i);
}
BuildGraph();
SolveQuery();
for (int i = 0; i < Q; i++) {
cout << answer[i] << "\n";
}
}
int main() {
Solve();
return 0;
}
