#include "garden.h"
#include "gardenlib.h"
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
#include<vector>
int a,b,c,t,h,p,q,check,p1,q1,y,z,sz1,sz2,v[150003][2],ch2[150003][2],ch1[150003][2],x[150003][2],D1[150003][2],D2[150003][2],cycle1[150003][2],cycle2[150003][2];
void count_routes(int N,int M,int P,int R[][2],int Q,int G[])
{
a=N;b=M;
c=P+1;
for(int i=0;i<b;i++)
{
if(x[R[i][0]+1][0]==0)x[R[i][0]+1][0]=R[i][1]+1;
else if(x[R[i][0]+1][1]==0)x[R[i][0]+1][1]=R[i][1]+1;
if(x[R[i][1]+1][0]==0)x[R[i][1]+1][0]=R[i][0]+1;
else if(x[R[i][1]+1][1]==0)x[R[i][1]+1][1]=R[i][0]+1;
}
for(int i=1;i<=a;i++)
{
if(x[i][1]==0)x[i][1]=x[i][0];
}
p=c;q=0;t=0;
D1[p][q]=0;
ch1[p][q]=1;
v[p][q]=1;
p1=-1;q1=-1;
while(1)
{
if(q==0)p1=x[p][0];
else p1=x[p][1];
if(p==x[p1][0])q1=1;
else q1=0;
if(p1==c&&q1==0)break;
else
{
if(v[p1][q1]==1)break;
v[p1][q1]=1;
p=p1;q=q1;
t++;
}
}
if(p1==c&&q1==0)
{
p=c;q=0;
cycle1[p][q]=t+1;
while(1)
{
if(q==0)p1=x[p][0];
else p1=x[p][1];
if(p==x[p1][0])q1=1;
else q1=0;
if(p1==c&&q1==0)break;
p=p1;q=q1;
ch1[p][q]=1;
D1[p][q]=t;t--;
cycle1[p][q]=cycle1[c][0];
}
}
memset(v,0,sizeof(v));
p=c;q=1;t=0;
D2[p][q]=0;
ch2[p][q]=1;
v[p][q]=1;
p1=-1;q1=-1;
while(1)
{
if(q==0)p1=x[p][0];
else p1=x[p][1];
if(p==x[p1][0])q1=1;
else q1=0;
if(p1==c&&q1==1)break;
else
{
if(v[p1][q1]==1)break;
v[p1][q1]=1;
p=p1;q=q1;
t++;
}
}
if(p1==c&&q1==1)
{
p=c;q=1;
cycle2[p][q]=t+1;
while(1)
{
if(q==0)p1=x[p][0];
else p1=x[p][1];
if(p==x[p1][0])q1=1;
else q1=0;
if(p1==c&&q1==1)break;
p=p1;q=q1;
ch2[p][q]=1;
D2[p][q]=t;
cycle2[p][q]=cycle2[c][1];
t--;
}
}
memset(v,0,sizeof(v));
for(int i=1;i<=a;i++)
{
for(int j=0;j<2;j++)
{
if(ch1[i][j])continue;
p=i;q=j;t=0;
v[i][j]=1;
while(1)
{
if(q==0)p1=x[p][0];
else p1=x[p][1];
if(p==x[p1][0])q1=1;
else q1=0;
t++;
if(ch1[p1][q1])break;
else if(v[p1][q1])break;
p=p1;q=q1;
v[p][q]=1;
}
if(ch1[p1][q1])
{
y=p1;z=q1;
p=i;q=j;
ch1[p][q]=1;
D1[p][q]=D1[y][z]+t;
cycle1[p][q]=cycle1[y][z];
while(1)
{
if(q==0)p1=x[p][0];
else p1=x[p][1];
if(p==x[p1][0])q1=1;
else q1=0;
t--;
if(p1==y&&q1==z)break;
p=p1;q=q1;
ch1[p][q]=1;
D1[p][q]=D1[y][z]+t;
cycle1[p][q]=cycle1[y][z];
}
}
}
}
memset(v,0,sizeof(v));
for(int i=1;i<=a;i++)
{
for(int j=0;j<2;j++)
{
if(ch2[i][j])continue;
p=i;q=j;t=0;
v[i][j]=1;
while(1)
{
if(q==0)p1=x[p][0];
else p1=x[p][1];
if(p==x[p1][0])q1=1;
else q1=0;
t++;
if(ch2[p1][q1])break;
else if(v[p1][q1])break;
p=p1;q=q1;
v[p][q]=1;
}
if(ch2[p1][q1])
{
y=p1;z=q1;
p=i;q=j;
ch2[p][q]=1;
D2[p][q]=D2[y][z]+t;
cycle2[p][q]=cycle2[y][z];
while(1)
{
if(q==0)p1=x[p][0];
else p1=x[p][1];
if(p==x[p1][0])q1=1;
else q1=0;
t--;
if(p1==y&&q1==z)break;
p=p1;q=q1;
ch2[p][q]=1;
D2[p][q]=D2[y][z]+t;
cycle2[p][q]=cycle2[y][z];
}
}
}
}
int ans;
for(int i=0;i<Q;i++)
{
ans=0;
for(int j=1;j<=a;j++)
{
if(ch1[j][0]&&(D1[j][0]==G[i]||(cycle1[j][0]&&G[i]>D1[j][0]&&(G[i]-D1[j][0])%cycle1[j][0]==0)))
{
ans++;
}
else if(ch2[j][0]&&(D2[j][0]==G[i]||(cycle2[j][0]&&G[i]>D2[j][0]&&(G[i]-D2[j][0])%cycle2[j][0]==0)))
{
ans++;
}
}
answer(ans);
}
}
