#include<cstdio>
#include<cmath>
#include<numeric>
#include<cassert>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstdlib>
using namespace std;

int read();
typedef long long ll;
#define fr(i,l,r) for(int i=(l);i<=(r);++i)
#define rf(i,l,r) for(int i=(l);i>=(r);--i)
#define fo(i,l,r) for(int i=(l);i<(r);++i)
#define foredge(i,u,v) for(int i=fir[u],v;v=to[i],i;i=nxt[i])
#define filein(File) freopen(File".in","r",stdin)
#define fileout(File) freopen(File".out","w",stdout)
#define reset(f,n) memset(f,0,sizeof(ll)*(n))
#define copy(f,g,n) memcpy(f,g,sizeof(ll)*(n))

const int N = 1 << 16 | 5;
int MOD;
ll inv[N];
ll qpow(ll a,ll x) {
	ll z=1;
	for(;x;x>>=1,a=a*a%MOD)
		if(x&1) z=z*a%MOD;
	return z;
}
namespace Poly {
	const double Pi = acos(-1);
	struct cp {
		double x,y;
		inline cp(double x = 0,double y = 0) : x(x),y(y) {}
	};
	cp operator + (const cp &a,const cp &b) {
		return cp(a.x + b.x,a.y + b.y);
	}
	cp operator - (const cp &a,const cp &b) {
		return cp(a.x - b.x,a.y - b.y);
	}
	cp operator * (const cp &a,const cp &b) {
		return cp(a.x*b.x - a.y*b.y,a.y*b.x + a.x*b.y);
	}
	cp conj(const cp &a) {
		return cp(a.x,-a.y);
	}
	cp ome[N]; int rv[N];
	int calc(int x) {int res = 1;while(res < x) res <<= 1;return res;}
	void prepare(int lim) {
		ome[0] = cp(1,0);
		for(int i = 1;i < lim;++i) {
			rv[i] = (rv[i >> 1] >> 1) | ((i&1) * (lim >> 1));
			ome[i] = cp(cos(2*Pi*i/lim),sin(2*Pi*i/lim));
		}
	}
	void FFT(cp *F,int &lim) {
		for(int i = 1;i < lim;++i)
			if(i < rv[i]) swap(F[i],F[rv[i]]);
		for(int len = 1,tmp = lim >> 1;len < lim;len <<= 1,tmp >>= 1)
			for(int st = 0;st < lim;st += len << 1) {
				cp *l = F+st,*r = l+len,res,*o = ome;
				for(int d = 0;d < len;++d) {
					res = *r * *o;
					*r = *l-res;*l = *l+res;
					++l,++r,o += tmp;
				}
			}
	}
	void MUL(ll *x,ll *y,ll *z,int lim) {
		static cp A[N],B[N],Da[N],Db[N],Dc[N],Dd[N];
		prepare(lim);
		for(int i = 0;i < lim;++i)
			x[i] = (x[i] + MOD) % MOD,y[i] = (y[i] + MOD) % MOD;
		for(int i = 0;i < lim;++i)
			A[i] = cp(x[i] & 32767,x[i] >> 15),B[i] = cp(y[i] & 32767,y[i] >> 15);
		FFT(A,lim),FFT(B,lim);
		for(int i = 0;i < lim;++i) {
			int j = lim-i&lim-1;
			cp da = (A[i] + conj(A[j])) * cp(0.5,0);
			cp db = (A[i] - conj(A[j])) * cp(0,-0.5);
			cp dc = (B[i] + conj(B[j])) * cp(0.5,0);
			cp dd = (B[i] - conj(B[j])) * cp(0,-0.5);
			Da[j] = da * dc;
			Db[j] = da * dd;
			Dc[j] = db * dc;
			Dd[j] = db * dd;
		}
		for(int i = 0;i < lim;++i)
			A[i] = Da[i] + Db[i] * cp(0,1),B[i] = Dc[i] + Dd[i] * cp(0,1);
		FFT(A,lim),FFT(B,lim);
		for(int i = 0;i < lim;++i) {
			ll da = (ll)(A[i].x / lim + 0.5) % MOD;
			ll db = (ll)(A[i].y / lim + 0.5) % MOD;
			ll dc = (ll)(B[i].x / lim + 0.5) % MOD;
			ll dd = (ll)(B[i].y / lim + 0.5) % MOD;
			z[i] = (da + (db + dc << 15) % MOD + (dd << 30) % MOD) % MOD;
		}
	}
	void getinv(ll *f,ll *g,int n) {
		static ll t[N];
		reset(g,n); g[0]=qpow(f[0],MOD-2);
		for(int lim=2;lim<=n;lim<<=1) {
			MUL(f,g,t,lim); reset(t,lim/2); t[0]=1;
			fo(i,lim/2,lim) t[i]=-t[i];
			MUL(g,t,t,lim); copy(g+lim/2,t+lim/2,lim/2);
		}
	}
	void getln(ll *f,ll *g,int n) {
		static ll t[N];
		getinv(f,g,n); reset(g+n,n);
		fo(i,0,n) t[i]=f[i+1]*(i+1)%MOD;
		reset(t+n,n);
		MUL(t,g,g,n<<1); rf(i,n-1,1) g[i]=g[i-1]*inv[i]%MOD;
		g[0]=0;
	}
	void getexp(ll *f,ll *g,int n) {
		static ll t[N];
		reset(g,n); g[0]=1;
		for(int lim=2;lim<=n;lim<<=1) {
			getln(g,t,lim);
			fo(i,0,lim) t[i]=(f[i]-t[i])%MOD; ++t[0];
			MUL(t,g,t,lim);
			copy(g+lim/2,t+lim/2,lim/2);
		}
	}
	void gnewton(ll *f,int n) {
		static ll t[N],h[N],g[N];
		f[1]=1;
		for(int lim=4;lim<=n;lim<<=1) {
			fo(i,0,lim) h[i]=0;
			++f[1];
			fo(i,1,lim/2) for(int j=1;i*j<lim;++j)
				(h[i*j]+=f[i]*inv[j]%MOD*inv[2])%=MOD;
			--f[1];
			getexp(h,t,lim);
			fo(i,0,lim) g[i]=2*f[i]%MOD;
			g[0]+=2;
			fo(i,0,lim) {
				(g[i]-=2*t[i])%=MOD;
				h[i]=-t[i];
			}
			h[0]+=2;
			getinv(h,t,lim);
			fo(i,lim,lim*2) g[i]=t[i]=0;
			MUL(g,t,h,lim<<1);
			fo(i,lim/2,lim) f[i]=-h[i];
		}
	}
}
int n;
ll f[N];
int main() {
	int t=read(); MOD=read();
	n=1<<15;
	inv[1]=1; fr(i,2,n) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
	Poly::gnewton(f,n);
	while(t--) printf("%lld\n",(f[read()]+MOD)%MOD);
	return 0;
}

inline int read() {
	static int x,c,f;x=0;f=1;
	do c=getchar(),c=='-'&&(f=-1); while(!isdigit(c));
	do x=x*10+(c&15),c=getchar(); while(isdigit(c));
	return x*f;
}