#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int lim=3e15,lowlim=15;
int f[20],g[20],df[20],dg[20];
int mod,f0,g0,T;
map<int,int>valf,valg,visf,visg;
vector<int>F,G,Fpos,Gpos;
priority_queue<int,vector<int>,greater<int>>havf,havg;
int FtoG[4]={2,3,4,5},GtoF[4]={2,3,5,7};
signed main(){
	cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);
	cin>>(f[0]=df[0])>>(g[0]=dg[0])>>T>>mod;
	F.push_back(f[0]),Fpos.push_back(0),G.push_back(g[0]),Gpos.push_back(0);
	for(int i=1;i<=lowlim;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]);
		df[i]=f[i]-f[i-1],dg[i]=g[i]-g[i-1];
		valf[i]=df[i],valg[i]=dg[i];
		havf.push(i),havg.push(i);
	}
	while(havf.size()||havg.size()){
		if(havf.size()&&(!havg.size()||havf.top()<=havg.top())){
			int now=havf.top();
//			if(now<21)cout<<"CHK:"<<now<<" "<<valf[now]<<"\n";
//			cout<<"F:"<<now<<"\n";
			havf.pop();
			int dnow=valf[now];
			F.push_back(dnow),Fpos.push_back(now);
			for(int i=0;i<4;i++){
				if(now*FtoG[i]>lowlim&&now*FtoG[i]<lim){
					if(!visg[now*FtoG[i]])visg[now*FtoG[i]]=1,havg.push(now*FtoG[i]);
					valg[now*FtoG[i]]=(valg[now*FtoG[i]]+dnow)%mod;
				}
			}
		} else {
			int now=havg.top();
//			cout<<"G:"<<now<<"\n";
			havg.pop();
			int dnow=valg[now];
			G.push_back(dnow),Gpos.push_back(now);
			for(int i=0;i<4;i++){
				if(now*GtoF[i]>lowlim&&now*GtoF[i]<lim){
					if(!visf[now*GtoF[i]])visf[now*GtoF[i]]=1,havf.push(now*GtoF[i]);
					valf[now*GtoF[i]]=(valf[now*GtoF[i]]+dnow)%mod;
				}
			}
		}
	}	
	while(T--){
		int n,res=0;
		cin>>n;
		int pos=lower_bound(Fpos.begin(),Fpos.end(),n+1)-Fpos.begin();
		pos--;
		for(int i=0;i<=pos;i++)res=(res+F[i])%mod;
		cout<<res<<" ";
		res=0;
		pos=lower_bound(Gpos.begin(),Gpos.end(),n+1)-Gpos.begin();
		pos--;
		for(int i=0;i<=pos;i++)res=(res+G[i])%mod;
		cout<<res<<"\n";
	}
	return 0;
}