#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")
const int maxn = 3e5 + 5;
vector<int> graph_shit[maxn+5], krug(maxn+5), id(maxn+5), SZ(maxn+5), bad(maxn+5), graph[maxn+5], vis(maxn+5), topo, rg[maxn+5];
vector<vector<int> > cmp;
int n, up[maxn][31], timer = 0, start;
void dfs(int u) {
vis[u] = 1;
for(int &v : graph[u])
if(!vis[v]) dfs(v);
topo.push_back(u);
}
void dfs2(int u) {
cmp.back().push_back(u);
vis[u] = 1;
for(int &v : rg[u])
if(!vis[v]) dfs2(v);
}
void dfs3(int u) {
krug[u] = timer++;
for(int &v : graph[u])
if(v != start) dfs3(v);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
n = N;
for(int i=0; i<M; i++) {
graph_shit[R[i][0]].push_back(R[i][1]);
graph_shit[R[i][1]].push_back(R[i][0]);
}
for(int i=0; i<N; i++) {
int v = graph_shit[i][0];
if(graph_shit[v][0] == i) {
graph[i].push_back(v+N);
rg[v+N].push_back(i);
} else {
graph[i].push_back(v);
rg[v].push_back(i);
}
}
for(int i=N; i<2*N; i++) {
if(graph_shit[i-N].size() == 1) {
int v = graph_shit[i-N][0];
if(graph_shit[v][0] == i-N) {
graph[i].push_back(v+N);
rg[v+N].push_back(i);
} else {
graph[i].push_back(v);
rg[v].push_back(i);
}
} else {
int v = graph_shit[i-N][1];
if(graph_shit[v][0] == i-N) {
graph[i].push_back(v+N);
rg[v+N].push_back(i);
} else {
graph[i].push_back(v);
rg[v].push_back(i);
}
}
}
for(int i=0; i<2*N; i++) if(!vis[i]) dfs(i);
for(int i=0; i<2*N; i++) vis[i] = 0;
reverse(topo.begin(), topo.end());
int koce = 1;
for(int &i : topo) {
if(vis[i]) continue;
cmp.push_back({ });
dfs2(i);
for(int &x : cmp.back()) id[x] = koce;
SZ[koce] = cmp.back().size();
if(cmp.back().size() >= 2) {
for(int &x : cmp.back()) bad[x] = 1;
timer = 0; start = cmp.back().at(0);
dfs3(cmp.back().at(0));
}
koce++;
}
for(int i=0; i<2*N; i++) up[i][0] = graph[i].back();
for(int j=1; j<31; j++)
for(int i=0; i<2*N; i++) up[i][j] = up[up[i][j-1]][j-1];
vector<ll> to_cycle(2*N, -1), cycle_id(2*N);
for(int i=0; i<2*N; i++) {
int curr = i;
ll dist = 0;
for(int j=30; j>=0; j--) {
if(!bad[up[curr][j]]) {
dist += (1ll << j);
curr = up[curr][j];
}
}
if(bad[up[curr][0]]) {
if(bad[i]) to_cycle[i] = 0;
else to_cycle[i] = dist + 1;
if(bad[i]) cycle_id[i] = i;
else cycle_id[i] = up[curr][0];
}
}
for(int i=0; i<Q; i++) {
int ans=0;
for(int j=0; j<N; j++) {
if(to_cycle[j] != -1 && to_cycle[j] <= G[i]) {
int curr = cycle_id[j];
int K = (G[i] - to_cycle[j]) % SZ[id[curr]];
if(id[P] != id[curr] && id[P+N] != id[curr]) continue;
// for(int k=20; k>=0; k--)
// if(K & (1ll << k)) curr = up[curr][k];
// if(curr == P || curr == P + N) ans++;
if(id[P] == id[curr]) {
if(krug[curr] <= krug[P] && krug[P] - krug[curr] == K) ans++;
if(krug[curr] > krug[P] && SZ[id[curr]] - krug[curr] + krug[P] == K) ans++;
}
if(id[P+N] == id[curr]) {
if(krug[curr] <= krug[P+N] && krug[P+N] - krug[curr] == K) ans++;
if(krug[curr] > krug[P+N] && SZ[id[curr]] - krug[curr] + krug[P+N] == K) ans++;
}
} else if(to_cycle[j] == -1 || to_cycle[j] > G[i]) {
int curr = j;
for(int k=30; k>=0; k--)
if(G[i] & (1ll << k)) curr = up[curr][k];
if(curr == P || curr == P + N) ans++;
}
}
answer(ans);
}
}
