#include<map>
#include<queue>
#include<cstdio>
#include<algorithm>
#define int long long
// #define inf 0x3f3f3f3f
// #define getchar getchar_unlocked
// #define putchar putchar_unlocked
template<typename T>void read(T &x){
	x=0;bool f=0;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f)x=-x;
}
void write(char x){putchar(x);}
template<typename T>void write(T x){
	if(x<0)putchar('-'),x=-x;
	char stk[24];int cnt=0;
	do stk[++cnt]=x%10+48,x/=10;while(x);
	for(;cnt;)putchar(stk[cnt--]);
}
template<typename T,typename ...Args>void read(T &x,Args &...args){read(x);read(args...);}
template<typename T,typename ...Args>void write(T x,Args ...args){write(x);write(args...);}
template<typename T>T min(T x,T y){return x<y?x:y;}
template<typename T>T max(T x,T y){return x>y?x:y;}
const int maxn=1e6+4,lim=1e15;int id[maxn],tot,f[maxn],g[maxn],T,mod;
std::priority_queue<int,std::vector<int>,std::greater<int> >que;std::map<int,bool>mp;
int get_f(int x,int y){
	if(x%y)return 0;
	int tmp=std::lower_bound(id+1,id+tot+1,x/y)-id;
	return f[tmp];
}
int get_g(int x,int y){
	if(x%y)return 0;
	int tmp=std::lower_bound(id+1,id+tot+1,x/y)-id;
	return g[tmp];
}
void init(){
	for(int i=1;i<=13;++i)que.emplace(i);
	for(;que.size();){
		int x=que.top();que.pop();
		if(x>lim||mp[x])continue;;mp[x]=1;
		id[++tot]=x;
		que.emplace(x*2ll);que.emplace(x*3ll);que.emplace(x*5ll);que.emplace(x*7ll);
	}
}
signed main(){
	read(f[0],g[0],T,mod);
	for(int i=1;i<=13;++i){
		f[i]=max(i,g[i/2]+g[i/3]+g[i/5]+g[i/7]);
		g[i]=max(i,f[i/2]+f[i/3]+f[i/4]+f[i/5]);
	}
	for(int i=13;i;--i)f[i]=f[i]-f[i-1],g[i]=g[i]-g[i-1];
	init();
	for(int i=14;i<=tot;++i){
		f[i]=(get_g(id[i],2)+get_g(id[i],3)+get_g(id[i],5)+get_g(id[i],7))%mod;
		g[i]=(get_f(id[i],2)+get_f(id[i],3)+get_f(id[i],4)+get_f(id[i],5))%mod;
	}
	for(int i=1;i<=tot;++i)(f[i]+=f[i-1])%=mod,(g[i]+=g[i-1])%=mod;
	for(;T--;){
		int x;read(x);
		int tmp=std::upper_bound(id+1,id+tot+1,x)-id-1;
		write(f[tmp],' ',g[tmp],'\n');
	}
	return 0;
}