#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using pii=pair<int,int>;
#define pb push_back
#define all(a) begin(a),end(a)

const char en='\n';
const ll MAXN=1e15,T=1e7,V=MAXN/T;

ll m,f[T+10],g[T+10],dp1[10000],dp2[10000];
int t;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>f[0]>>g[0]>>t>>m;
	for (int i=1;i<=100;++i)
	{
		f[i]=max(i*1ll,g[i/2]+g[i/3]+g[i/5]+g[i/7]);
		g[i]=max(i*1ll,f[i/2]+f[i/3]+f[i/4]+f[i/5]);
	}
	for (int i=1;i<=100;++i) f[i]%=m,g[i]%=m;
	for (int i=101;i<=T;++i)
	{
		f[i]=g[i/2]+g[i/3]+g[i/5]+g[i/7];
		g[i]=f[i/2]+f[i/3]+f[i/4]+f[i/5];
		if (f[i]>=2*m) f[i]-=2*m;
		if (f[i]>=m) f[i]-=m;
		if (g[i]>=2*m) g[i]-=2*m;
		if (g[i]>=m) g[i]-=m;
	}
	vi s2357;
	s2357.pb(1);
	while (1)
	{
		vi nov;
		for (auto x: s2357)
		{
			nov.pb(x);
			if (x*2<=V) nov.pb(x*2);
			if (x*3<=V) nov.pb(x*3);
			if (x*5<=V) nov.pb(x*5);
			if (x*7<=V) nov.pb(x*7);
		}
		sort(all(nov));
		nov.erase(unique(all(nov)),nov.end());
		if (nov==s2357) break;
		s2357=nov;
	}
	vi nov;
	for (auto x: s2357)
	{
		nov.pb(x);
		nov.pb(x*2);
		nov.pb(x*3);
		nov.pb(x*4);
		nov.pb(x*5);
		nov.pb(x*7);
	}
	sort(all(nov));
	nov.erase(unique(all(nov)),nov.end());
	vector<array<int,5>> tra;
	array<int,5> um={2,3,4,5,7};
	for (int i=0;i<(int)s2357.size();++i)
	{
		array<int,5> re;
		for (int j=0;j<5;++j)
		{
			re[j]=lower_bound(all(nov),s2357[i]*um[j])-nov.begin();
		}
		tra.pb(re);
	}
	int sm=s2357.size(),sn=nov.size();
	while (t--)
	{
		ll n;
		cin>>n;
		if (n<=T)
		{
			cout<<f[n]<<' '<<g[n]<<en;
			continue;
		}
		int i;
		if (n<=V*300)
		{
			for (i=0;i<(int)s2357.size() && n/s2357[i]>T;++i)
			{
				for (int j=0;j<5;++j)
				{
					if (n/(um[j]*s2357[i])<=T)
					{
						dp1[tra[i][j]]=f[n/(um[j]*s2357[i])];
						dp2[tra[i][j]]=g[n/(um[j]*s2357[i])];
					}
				}
			}
			for (--i;i>=0;--i)
			{
				dp1[i]=dp2[tra[i][0]]+dp2[tra[i][1]]+dp2[tra[i][3]]+dp2[tra[i][4]];
				dp2[i]=dp1[tra[i][0]]+dp1[tra[i][1]]+dp1[tra[i][2]]+dp1[tra[i][3]];
				if (dp1[i]>=2*m) dp1[i]-=2*m;
				if (dp1[i]>=m) dp1[i]-=m;
				if (dp2[i]>=2*m) dp2[i]-=2*m;
				if (dp2[i]>=m) dp2[i]-=m;
			}
		}
		else
		{
			for (int i=sm;i<sn;++i)
			{
				dp1[i]=f[n/nov[i]];
				dp2[i]=g[n/nov[i]];
			}
			for (int i=sm-1;i>=0;--i)
			{
				dp1[i]=dp2[tra[i][0]]+dp2[tra[i][1]]+dp2[tra[i][3]]+dp2[tra[i][4]];
				dp2[i]=dp1[tra[i][0]]+dp1[tra[i][1]]+dp1[tra[i][2]]+dp1[tra[i][3]];
				if (dp1[i]>=2*m) dp1[i]-=2*m;
				if (dp1[i]>=m) dp1[i]-=m;
				if (dp2[i]>=2*m) dp2[i]-=2*m;
				if (dp2[i]>=m) dp2[i]-=m;
			}
		}
		cout<<dp1[0]<<' '<<dp2[0]<<en;
	}
}