/**
* Author: Nicholas Winschel
* Created: 05.10.2023 22:07:36
**/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
void answer(int X);
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]);
int inf = 1e9+500;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
V<vi> r(2*N);
vi f(2*N, -1);
for (int i = 0; i < M; i++) {
if (f[R[i][0]] == -1 && f[R[i][1]] == -1) {
f[R[i][0]] = R[i][1]+N;
f[R[i][1]] = R[i][0]+N;
} else if (f[R[i][0]] == -1) {
f[R[i][0]] = R[i][1];
if (f[R[i][1]+N]==-1) {
f[R[i][1]+N]=R[i][0]+N;
}
} else if (f[R[i][1]] == -1) {
f[R[i][1]] = R[i][0];
if (f[R[i][0]+N]==-1) {
f[R[i][0]+N]=R[i][1]+N;
}
} else if (f[R[i][0]+N] == -1 || f[R[i][1]+N]==-1) {
if (f[R[i][0]+N]==-1) f[R[i][0]+N]=R[i][1];
if (f[R[i][1]+N]==-1) f[R[i][1]+N]=R[i][0];
}
}
for (int i = 0; i < N; i++) {
if (f[i+N]==-1) f[i+N]=f[i];
r[f[i]].push_back(i);
r[f[i+N]].push_back(i+N);
}
vi ub(2*N, inf), b(2*N,inf);
V<bool> vis(2*N);
auto dfs = [&](int v, int c, auto &&dfs) -> int {
if (vis[v]) return c;
vis[v]=true;
ub[v]=c;
int ret = 0;
for (int x : r[v]) {
ret = max(ret, dfs(x,c+1,dfs));
}
return ret;
};
int cub = dfs(P,0,dfs);
swap(ub,b);
vis=V<bool>(2*N);
int cb = dfs(P+N,0,dfs);
swap(ub,b);
for (int i = 0; i < Q; i++) {
int K = G[i];
int ans = 0;
for (int i = 0; i < N; i++) {
if ((ub[i] <= K && (ub[i] == K || (cub && (K-ub[i])%cub == 0)))
|| (b[i] <= K && (b[i] == K || (cb && (K-b[i])%cb == 0)))) ans++;
}
answer(ans);
}
}
