// Starcraft 2 enjoyer //
#include "gardenlib.h"
#include "garden.h"
#include <bits/stdc++.h>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 3e5 + 5;
const int M = 11;
const int B = 18;
const long long K = 2;
const int LG = 20;
const long long INF = 1e18 + 5;
const int P = 31;
const int MOD = 998244353;
const int nx[] = {0, 1, 0, -1}, ny[] = {-1, 0, 1, 0};
pair<int, int> best[N][2];
vector<int> adj[N], v;
int dis[N], cyclelen, nxt[N], pos[N], stcycle, ans[N], cnt[N], num[N];
bool vis[N];
queue<int> cur;
void count_routes(int n, int m, int p, int r[][2], int q, int g[])
{
for (int x = 0; x < n; x++)
{
best[x][0] = best[x][1] = {-1, -1};
}
for (int x = 0; x < m; x++)
{
auto [a, b] = r[x];
int w = m - x;
best[a][1] = max(best[a][1], {w, b});
if (best[a][0] < best[a][1])
swap(best[a][0], best[a][1]);
best[b][1] = max(best[b][1], {w, a});
if (best[b][0] < best[b][1])
swap(best[b][0], best[b][1]);
}
for (int x = 0; x < n; x++)
{
for (int y = 0; y < 2; y++)
{
auto [a, b] = best[x][y];
if (a == -1)
{
tie(a, b) = best[x][0];
}
int i = 2 * x;
i += y;
if (best[b][0].first == a)
{
adj[2 * b + 1].push_back(i);
// cout << 2 * b + 1 << " " << i << "\n";
nxt[i] = 2 * b + 1;
}
else
{
adj[2 * b].push_back(i);
// cout << 2 * b << " " << i << "\n";
nxt[i] = 2 * b;
}
}
}
// cout << "\n";
for (int x = 0; x < 2; x++)
{
for (int y = 0; y <= 2 * n; y++)
{
vis[y] = 0;
dis[y] = -1;
cnt[y] = 0;
num[y] = 0;
}
dis[2 * p + x] = 0;
cur.push(2 * p + x);
while (!cur.empty())
{
int c = cur.front();
cur.pop();
for (int i : adj[c])
{
if (vis[i])
continue;
dis[i] = dis[c] + 1;
vis[i] = 1;
cur.push(i);
}
}
for (int y = 0; y <= 2 * n; y++)
{
vis[y] = 0;
}
// for (int y = 0; y < n; y++)
// {
// cout << dis[2 * y] << " " << dis[2 * y + 1] << "dis\n";
// }
v.clear();
v.push_back(2 * p + x);
vis[2 * p + x] = 1;
pos[2 * p + x] = v.size();
stcycle = -1;
while (true)
{
int i = nxt[v.back()];
if (vis[i])
{
cyclelen = v.size() - pos[i];
stcycle = pos[i];
break;
}
vis[i] = 1;
v.push_back(i);
pos[i] = v.size();
}
vector<pair<int, int>> query, dist;
for (int y = 0; y < q; y++)
{
query.push_back({g[y], y});
}
for (int y = 0; y < n; y++)
{
// if (dis[y] != -1)
dist.push_back({dis[2 * y], 2 * y});
}
sort(query.begin(), query.end());
sort(dist.begin(), dist.end());
int cid = 0;
for (int y = 0; y < q; y++)
{
auto &[w, id] = query[y];
while (cid < dist.size())
{
if (dist[cid].first <= w)
cnt[dist[cid].first % cyclelen]++, num[dist[cid++].first]++;
else
break;
}
if (stcycle != 1)
{
// cout << 2 * p + x << "\n";
if (w < 2 * n)
ans[id] += num[w];
}
else
{
ans[id] += cnt[w % cyclelen];
}
}
}
for (int x = 0; x < q; x++)
{
answer(ans[x]);
}
}
