// #define INTERACTIVE
// #define FAST_EXECUTION
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
const long long INF = std::numeric_limits<long long>::max() / 4;
const long long MOD = 998244353;
#ifdef ONLINE_JUDGE
#define debug(x) do { } while (0)
#define debug2(x, y) do { } while (0)
#define debug3(x, y, z) do { } while (0)
#define debugendl() do { } while (0)
#define debugmatrix(m) do { } while (0)
#else
#define debug(x) cerr << #x << " = " << x << endl
#define debug2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl
#define debug3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl
#define debugendl() cerr << endl
#define debugmatrix(m) cerr << #m << " = " << endl; for (auto v: m) { for (auto w: v) cerr << w << " "; cerr << endl; }
#endif
#define LL long long
#define L long
#define ULL unsigned long long
#define I int
#define UI unsigned int
#define D double
#define V(T) std::vector<T>
#define W(T) std::vector<std::vector<T>>
#define S(T) std::set<T>
#define P(T, U) std::pair<T, U>
#define M(T, U) std::map<T, U>
#define ALL(a) a.begin(), a.end()
#define REP(n) for (int t = 0; t < n; ++t)
#define FOR(i, n) for (int i = 0; i < n; ++i)
#define FFOR(i, j, n) for (int i = j; i < n; ++i)
#define FOR_S(i, n, k) for (int i = 0; i < n; i += k)
#define RFOR(i, n) for (int i = n-1; i >= 0; --i)
#define RFOR_S(i, n, k) for (int i = n-1; i >= 0; i -= k)
#define IN(a, b) (a.find(b) != a.end())
#define MAX_IN(A) *(max_element(A.begin(), A.end()))
#define MIN_IN(A) *(min_element(A.begin(), A.end()))
#define MAX_AT(A) (max_element(A.begin(), A.end()) - A.begin())
#define MIN_AT(A) (min_element(A.begin(), A.end()) - A.begin())
#define SUM(A) accumulate(A.begin(), A.end(), 0LL)
#define PRO(A) accumulate(A.begin(), A.end(), 1LL, multiplies<long long>())
#define COUNT(A, x) count(A.begin(), A.end(), x)
#define EXISTS(A, cond) any_of(A.begin(), A.end(), cond)
#define FORALL(A, cond) all_of(A.begin(), A.end(), cond)
#define GCD(a, b) std::gcd((a), (b))
#define LCM(a, b) std::lcm((a), (b))
#define SORT(a) sort(ALL(a))
#define DSORT(a) sort(ALL(a), greater<>())
#define ORD(c) (c-'a')
#define mp make_pair
#define test_cases() LL t; cin >> t; while (t--) solve()
#define endl '\n'
#ifndef INTERACTIVE
#define faster_io() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#else
#define faster_io() do { } while (0)
#endif
#ifdef FAST_EXECUTION
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#endif
template<typename A, typename B> std::pair<A, B> operator+(const std::pair<A, B> &a, const std::pair<A, B> &b) { return {a.first + b.first, a.second + b.second}; }
template<typename A, typename B> std::pair<A, B> operator-(const std::pair<A, B> &a, const std::pair<A, B> &b) { return {a.first - b.first, a.second - b.second}; }
template<typename T> std::pair<T, T> operator*(const std::pair<T, T> &a, const T& b) { return {b * a.first, b * a.second}; }
template<typename T> std::pair<T, T> operator*(const T& b, const std::pair<T, T> &a) { return {b * a.first, b * a.second}; }
bool pair_cmp_second(const std::pair<long long, long long> &a, const std::pair<long long, long long> &b) { return a.second < b.second || (a.second == b.second && a.first < b.first); }
template<typename A, typename B> std::ostream& operator<<(std::ostream &out, const std::pair<A, B> &p);
template<typename A, typename B> std::istream& operator>>(std::istream &in, std::pair<A, B> &p);
template<typename T> std::ostream& operator<<(std::ostream &out, const std::vector<T> &v);
template<typename T> std::istream& operator>>(std::istream &in, std::vector<T> &v);
std::istream& operator>>(std::istream &in, bool &b) { char c; in >> c; b = (c == '1'); return in; }
std::ostream& operator<<(std::ostream &out, const bool &b) { return out << (b ? '1' : '0'); }
std::istream& operator>>(std::istream &in, std::vector<bool> &v) { char c; FOR(i, v.size()) { in >> c; v[i] = (c == '1'); } return in; }
template<typename A, typename B> std::ostream& operator<<(std::ostream &out, const std::pair<A, B> &p) { return out << "(" << p.first << ", " << p.second << ")"; }
template<typename A, typename B> std::istream& operator>>(std::istream &in, std::pair<A, B> &p) { return in >> p.first >> p.second; }
template<typename T> std::ostream& operator<<(std::ostream &out, const std::vector<T> &v) { for (const T &x : v) out << x << " "; return out; }
template<typename T> std::istream& operator>>(std::istream &in, std::vector<T> &v) { for (T &x : v) in >> x; return in; }
template<typename F>
LL first_true(LL lo, LL hi, F pred) {
while (lo < hi) {
LL mid = lo + (hi - lo) / 2;
if (pred(mid))
hi = mid;
else
lo = mid + 1;
}
return lo;
}
template<typename F>
LL last_true(LL lo, LL hi, F pred) {
while (lo < hi) {
LL mid = lo + (hi - lo + 1) / 2;
if (pred(mid))
lo = mid;
else
hi = mid - 1;
}
return lo;
}
using namespace std;
void count_routes(int N,int M,int P,int R[][2],int Q,int* G) {
int S = 2 * N;
V(int) graph(S);
V(P(int, int)) edges(N, {-1, -1});
FOR(i, M) {
int u = R[i][0], v = R[i][1];
if (edges[u].first == -1)
edges[u].first = v;
else
edges[u].second = v;
if (edges[v].first == -1)
edges[v].first = u;
else
edges[v].second = u;
}
FOR(i, N) {
int v1 = edges[i].first;
int v2 = edges[i].second;
graph[i] = (edges[v1].first == i ? v1 + N : v1);
if (v2 == -1)
graph[i + N] = graph[i];
else
graph[i + N] = (edges[v2].first == i ? v2 + N : v2);
}
V(V(int)) rev(S);
V(int) indeg(S, 0);
FOR(i, S) {
rev[graph[i]].push_back(i);
++indeg[graph[i]];
}
queue<int> q;
V(bool) in_cycle(S, true);
FOR(i, S) if (indeg[i] == 0)
q.push(i);
while (!q.empty()) {
int v = q.front();
q.pop();
in_cycle[v] = false;
int to = graph[v];
if (--indeg[to] == 0)
q.push(to);
}
V(int) cycle_len(S, 0);
V(bool) seen_cycle(S, false);
FOR(i, S) if (in_cycle[i] && !seen_cycle[i]) {
int len = 0;
int v = i;
do {
seen_cycle[v] = true;
v = graph[v];
++len;
} while (v != i);
v = i;
do {
cycle_len[v] = len;
v = graph[v];
} while (v != i);
}
auto get_dist = [&](int target) {
V(int) dist(S, -1);
queue<int> bfs;
dist[target] = 0;
bfs.push(target);
while (!bfs.empty()) {
int v = bfs.front();
bfs.pop();
for (int u : rev[v]) {
if (dist[u] == -1) {
dist[u] = dist[v] + 1;
bfs.push(u);
}
}
}
return dist;
};
V(int) dist0 = get_dist(P);
V(int) dist1 = get_dist(P + N);
V(LL) ans(Q, 0);
auto add_target = [&](int target, const V(int)& dist) {
if (!in_cycle[target]) {
unordered_map<int, int> freq;
FOR(i, N) if (dist[i] != -1)
++freq[dist[i]];
FOR(i, Q) {
auto it = freq.find(G[i]);
if (it != freq.end())
ans[i] += it->second;
}
return;
}
int len = cycle_len[target];
V(V(int)) bucket_dist(len), bucket_query(len);
FOR(i, N) if (dist[i] != -1)
bucket_dist[dist[i] % len].push_back(dist[i]);
FOR(i, Q) if (G[i] >= 0)
bucket_query[G[i] % len].push_back(i);
FOR(r, len) {
SORT(bucket_dist[r]);
for (int idx : bucket_query[r])
ans[idx] += upper_bound(ALL(bucket_dist[r]), G[idx]) - bucket_dist[r].begin();
}
};
add_target(P, dist0);
add_target(P + N, dist1);
FOR(i, Q)
answer((int)ans[i]);
}
