#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
int const NMAX=150005;
int const INF=1e9;
struct edge{
int id,to;
}edges[NMAX][2];
int func[2*NMAX];
vector<int>GR[2*NMAX];
int dist0[2*NMAX],dist1[2*NMAX];
void bfs(int nod,int dist[],int n){
queue<int>q;
int i;
for(i=0;i<2*n;++i)
dist[i]=INF;
dist[nod]=0;
q.push(nod);
while(!q.empty()){
int fr=q.front();
q.pop();
for(auto vec : GR[fr])
if(dist[vec]==INF){
dist[vec]=dist[fr]+1;
q.push(vec);
}
}
}
bool viz[2*NMAX];
struct destinatie{
int unde,pasi;
}dest[2];
void dfs(int nod,int n,int p,int comp){
int i;
for(i=0;i<2*n;++i)
viz[i]=0;
viz[nod]=1;
nod=func[nod];
int nrp=1;
while(!viz[nod] && nod!=2*p && nod!=2*p+1){
viz[nod]=1;
nod=func[nod];
++nrp;
}
if(nod!=2*p && nod!=2*p+1)
dest[comp].unde=2;
else
dest[comp].unde=nod%2;
dest[comp].pasi=nrp;
}
map<int,int>supl;
map<int,int>cic1;
map<int,int>cic2;
map<int,int>cic3;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
int i;
for(i=0;i<N;++i)
edges[i][0]=edges[i][1]={-1,-1};
for(i=0;i<M;++i){
int nod1=R[i][0];
int nod2=R[i][1];
if(edges[nod1][0].id==-1)
edges[nod1][0]={i,nod2};
else
if(edges[nod1][1].id==-1)
edges[nod1][1]={i,nod2};
if(edges[nod2][0].id==-1)
edges[nod2][0]={i,nod1};
else
if(edges[nod2][1].id==-1)
edges[nod2][1]={i,nod1};
}
for(i=0;i<2*N;++i){
int nod=i/2;
int tip=i%2;
if(tip==0 || (tip==1 && edges[nod][1].id==-1))
func[i]=2*edges[nod][0].to+(edges[edges[nod][0].to][0].id==edges[nod][0].id);
else
func[i]=2*edges[nod][1].to+(edges[edges[nod][1].to][0].id==edges[nod][1].id);
GR[func[i]].push_back(i);
}
bfs(2*P,dist0,N);
bfs(2*P+1,dist1,N);
dfs(2*P,N,P,0);
dfs(2*P+1,N,P,1);
vector<pair<int,int>>baleiere;
for(i=0;i<2*N;i+=2){
if(dist0[i]==INF && dist1[i]==INF)
continue;
if(dist0[i]<dist1[i]){
if(dest[0].unde==2)
++supl[dist0[i]];
else
if(dest[0].unde==0)
baleiere.push_back({dist0[i],-1});
else{
if(dest[1].unde==2){
++supl[dist0[i]];
++supl[dist1[i]];
}
else
if(dest[1].unde==1){
++supl[dist0[i]];
baleiere.push_back({dist1[i],-2});
}
else
baleiere.push_back({dist0[i],-3});
}
}
else{
if(dest[1].unde==2)
++supl[dist1[i]];
else
if(dest[1].unde==1)
baleiere.push_back({dist1[i],-2});
else{
if(dest[0].unde==2){
++supl[dist0[i]];
++supl[dist1[i]];
}
else
if(dest[0].unde==0){
++supl[dist1[i]];
baleiere.push_back({dist0[i],-1});
}
else
baleiere.push_back({dist1[i],-4});
}
}
}
for(i=0;i<Q;++i)
baleiere.push_back({G[i],i});
sort(baleiere.begin(),baleiere.end());
vector<int>ans(Q);
for(auto [pasi,tip] : baleiere){
if(tip>=0){
ans[tip]=supl[pasi];
if(dest[0].unde==0)
ans[tip]+=cic1[pasi%dest[0].pasi];
if(dest[1].unde==1)
ans[tip]+=cic2[pasi%dest[1].pasi];
if(dest[0].unde==1 && dest[1].unde==0)
ans[tip]+=cic3[pasi%(dest[0].pasi+dest[1].pasi)];
}
else{
if(tip==-1)
++cic1[pasi%dest[0].pasi];
if(tip==-2)
++cic2[pasi%dest[1].pasi];
if(tip==-3){
++cic3[pasi%(dest[0].pasi+dest[1].pasi)];
++cic3[(pasi+dest[0].pasi)%(dest[0].pasi+dest[1].pasi)];
}
if(tip==-4){
++cic3[pasi%(dest[0].pasi+dest[1].pasi)];
++cic3[(pasi+dest[1].pasi)%(dest[0].pasi+dest[1].pasi)];
}
}
}
for(i=0;i<Q;++i)
answer(ans[i]);
}
