#include<bits/stdc++.h>
using namespace std;
int p;
int qow(int a,int n){
	int ans=1;
	for(;n;n>>=1){
		if(n&1) ans=((long long)ans*a)%p;
		a=((long long)a*a)%p;
	}
	return ans;
}
inline int inverse(int a){
	return qow(a,p-2);
}
int f[110000];
int g[110000];
int h[210000];
const int C=(1<<15);
struct cp{
	double x,y;
	inline cp() {}
	inline cp(double xx,double yy) :x(xx),y(yy) {}
	inline cp operator +(const cp &b) const{return cp(x+b.x,y+b.y);}
	inline cp operator -(const cp &b) const{return cp(x-b.x,y-b.y);}
	inline cp operator *(const cp &b) const{return cp(x*b.x-y*b.y,x*b.y+y*b.x);}
	inline cp operator *(const double &b) const{return cp(x*b,y*b);}
	inline cp operator ~() const{return cp(x,-y);}
}x2[1<<20],y2[1<<20],z2[1<<20],w2[1<<20];
const double pi=acos(-1);
int rev[1<<20];
cp cc[1<<20][2];
int k,N;
double inv;
void fft(cp *a,int type){
	for(int i=0;i<N;i++){
		if(rev[i]>i) swap(a[i],a[rev[i]]);
	}
	for(int i=0;i<k;i++){
		for(int j=0;j<N;j+=(1<<(i+1))){
			for(int l=j;l<j+(1<<i);l++){
				cp x=a[l]+cc[(l-j)<<(k-1-i)][type]*a[l+(1<<i)],y=a[l]-cc[(l-j)<<(k-1-i)][type]*a[l+(1<<i)];
				a[l]=x;
				a[l+(1<<i)]=y;
			}
		}
	}
	if(type) {
		for(int i=0;i<N;i++) a[i]=a[i]*inv;
	}
} 
void multiply(int n,int m){
	for(k=1;;k++){
		if((1<<k)>n+m) break;
	}
	N=(1<<k);
	inv=1.0/N;
	for(int i=0;i<N;i++){
		rev[i]=0;
		for(int j=0;j<k;j++){
			if((i>>j)&1) rev[i]^=(1<<(k-1-j));
		}
	}
	for(int i=0;i<N;i++) cc[i][0]=cp(cos((2*pi*i)/N),sin((2*pi*i)/N));
	for(int i=0;i<N;i++) cc[i][1]=cp(cos((2*pi*i)/N),-sin((2*pi*i)/N));
	for(int i=0;i<=n;i++) x2[i]=cp(f[i]/C,f[i]%C);
	for(int i=n+1;i<N;i++) x2[i]=cp(0,0);
	fft(x2,0);
	for(int i=0;i<=m;i++) y2[i]=cp(g[i]/C,g[i]%C);
	for(int i=m+1;i<N;i++) y2[i]=cp(0,0);
	fft(y2,0);
	for(int i=0;i<N;i++) z2[i]=x2[i]*y2[i];
	fft(z2,1);
	w2[0]=(~x2[0])*y2[0];
	for(int i=1;i<N;i++) w2[i]=(~x2[N-i])*y2[i];
	fft(w2,1);
	for(int i=0;i<=n+m;i++){
		long long xxx,yyy,zzz;
		yyy=z2[i].y+0.4;
		yyy%=p;
		xxx=(z2[i].x+w2[i].x)/2+0.4;
		xxx%=p;
		zzz=(w2[i].x-z2[i].x)/2+0.4;
		zzz%=p;
		h[i]=(xxx*C*C+yyy*C+zzz)%p;
	}
}
int ff[30000]={};
int gg[30000]={}; 
void cdx(int l,int r){
	if(l==r){
		ff[l]=(ff[l]+1ll*(gg[l]+gg[l-1]))%p;
		ff[l]=((long long)inverse(l)*ff[l])%p;
		int u=23333/l;
		for(int i=1;i<=u;i++) gg[i*l]=(gg[i*l]+(long long)ff[l]*l)%p;
		return;
	}
	int mid=(l+r)/2;
	cdx(l,mid);
	if(l==2){
		for(int i=0;i<=mid;i++) f[i]=ff[i];
		for(int i=0;i<=mid;i++) g[i]=gg[i];
		multiply(mid,mid);
		for(int i=mid+1;i<=r;i++) ff[i]=(ff[i]+2ll*h[i])%p;
		cdx(mid+1,r);
		return;
	}
	for(int i=0;i<=r-l;i++) f[i]=gg[i];
	for(int i=0;i<=mid-l;i++) g[i]=ff[i+l];
	multiply(r-l,mid-l);
	for(int i=mid+1;i<=r;i++) ff[i]=(ff[i]+2ll*h[i-l])%p; 
	for(int i=0;i<=mid-l;i++) f[i]=gg[i+l];
	for(int i=0;i<=r-l;i++) g[i]=ff[i];
	multiply(mid-l,r-l);
	for(int i=mid+1;i<=r;i++) ff[i]=(ff[i]+2ll*h[i-l])%p;
	cdx(mid+1,r);
}
int main(){
	int _;
	scanf("%d%d",&_,&p);
	for(int i=1;i<=23333;i++) gg[i]=1; 
	cdx(2,23333);
	while(_--){
		int n;
		scanf("%d",&n);
		printf("%d\n",n>1 ? (2*ff[n])%p : 1);
	}
	return 0;
}