#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e6+6;

vector<int>vec;
int f[N],g[N];
int T,mod;

int F(int i,int j) {
    if(vec[i-1]%j) return 0;
    return f[lower_bound(vec.begin(),vec.end(),vec[i-1]/j)-vec.begin()+1];
}
int G(int i,int j) {
    if(vec[i-1]%j) return 0;
    return g[lower_bound(vec.begin(),vec.end(),vec[i-1]/j)-vec.begin()+1];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>f[0]>>g[0]>>T>>mod;
    for(int i=1;i<=14;++i)
        f[i]=max(i,g[i/2]+g[i/3]+g[i/5]+g[i/7])%mod,
        g[i]=max(i,f[i/2]+f[i/3]+f[i/4]+f[i/5])%mod;
    for(int i=14;i;--i)
        f[i]=(f[i]-f[i-1]+mod)%mod,g[i]=(g[i]-g[i-1]+mod)%mod;

    int n=1e15;
    for(int i=1;i<=13;++i)
        for(int j=i;j<=n;j*=2) for(int k=j;k<=n;k*=3)
            for(int l=k;l<=n;l*=5) for(int h=l;h<=n;h*=7)
                vec.push_back(h);
    sort(vec.begin(),vec.end()),vec.erase(unique(vec.begin(),vec.end()),vec.end());

    int sz=vec.size();
    for(int i=14;i<=sz;++i) 
        f[i]=(G(i,2)+G(i,3)+G(i,5)+G(i,7))%mod,
        g[i]=(F(i,2)+F(i,3)+F(i,4)+F(i,5))%mod;
    for(int i=1;i<=sz;++i) f[i]=(f[i]+f[i-1])%mod,g[i]=(g[i]+g[i-1])%mod;

    for(int i=1,x;i<=T;++i)
        cin>>x,cout<<f[upper_bound(vec.begin(),vec.end(),x)-vec.begin()]<<" "<<g[upper_bound(vec.begin(),vec.end(),x)-vec.begin()]<<'\n';

    return 0;
}