#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline)) static
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
using ll = long long;

#define IC isdigit(c)
#define GC c=getchar()
void rd(auto &x) { x = 0; char GC; bool f = 0;
	for (; !IC; GC) f |= c == '-';
	for (; IC; GC) x = x * 10 + c - 48;
	if (f) x = -x;
}
void rd(auto &x, auto &...y) { rd(x); rd(y...); }
#define meow(...) fprintf(stderr, __VA_ARGS__)
#define Assert(e) if (!(e)) { meow("AF@%d\n", __LINE__); exit(__LINE__); }

const ll LIM = 1e15;
ll f[41], g[41], P;

int main() {
	// freopen("arrebol.in", "r", stdin);
	// freopen("arrebol.out", "w", stdout);

	int T;
	rd(f[0], g[0], T, P);
	bool fF = 0, fG = 0;
	U (i, 1, 40) {
		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 (!fF) {
			if (f[i] > i) fF = 1;
			f[i] = max(f[i], ll(i));
		} else f[i] %= P;
		if (!fG) {
			if (g[i] > i) fG = 1;
			g[i] = max(g[i], ll(i));
		} else g[i] %= P;
	}
	U (i, 1, 40) f[i] %= P, g[i] %= P;

	set<pair<ll, int>> que; vector<pair<ll, ll>> dF, dG;
	dF.emplace_back(0, f[0]);
	dG.emplace_back(0, g[0]);
	U (i, 1, 40)
		dF.emplace_back(i, (f[i] - f[i - 1] + P) % P),
		dG.emplace_back(i, (g[i] - g[i - 1] + P) % P);
	auto acc = [&](vector<pair<ll, ll>> &v, ll p) -> ll {
		auto it = lower_bound(v.begin(), v.end(), make_pair(p, -1ll));
		if (it == v.end() || it->first != p)
			return 0;
		return it->second;
	};
	U (i, 1, 40) que.emplace(i, 0), que.emplace(i, 1);
	while (que.size()) {
		auto [u, t] = *que.begin(); que.erase(que.begin());
		if (t == 0) {
			if (2 * u <= LIM) que.emplace(2 * u, 1);
			if (3 * u <= LIM) que.emplace(3 * u, 1);
			if (5 * u <= LIM) que.emplace(5 * u, 1);
			if (7 * u <= LIM) que.emplace(7 * u, 1);
		} else {
			if (2 * u <= LIM) que.emplace(2 * u, 0);
			if (3 * u <= LIM) que.emplace(3 * u, 0);
			if (4 * u <= LIM) que.emplace(4 * u, 0);
			if (5 * u <= LIM) que.emplace(5 * u, 0);
		}
		if (u <= 40) continue;
		if (t == 0) {
			ll res = 0;
			if (!(u % 2)) res += acc(dG, u / 2);
			if (!(u % 3)) res += acc(dG, u / 3);
			if (!(u % 5)) res += acc(dG, u / 5);
			if (!(u % 7)) res += acc(dG, u / 7);
			dF.emplace_back(u, res % P);
		} else {
			ll res = 0;
			if (!(u % 2)) res += acc(dF, u / 2);
			if (!(u % 3)) res += acc(dF, u / 3);
			if (!(u % 4)) res += acc(dF, u / 4);
			if (!(u % 5)) res += acc(dF, u / 5);
			dG.emplace_back(u, res % P);
		}
	}
	clog << fF << ' ' << fG << endl;

	U (i, 1, dF.size() - 1) {
		assert(dF[i].first > dF[i - 1].first);
		(dF[i].second += dF[i - 1].second) %= P;
	}
	U (i, 1, dG.size() - 1) {
		assert(dG[i].first > dG[i - 1].first);
		(dG[i].second += dG[i - 1].second) %= P;
	}
	
	while (T--) {
		ll x; rd(x);
		if (x <= 20) {
			printf("%lld %lld\n", f[x], g[x]);
			continue;
		}
		auto itF = --upper_bound(dF.begin(), dF.end(), make_pair(x, LONG_LONG_MAX)),
			itG = --upper_bound(dG.begin(), dG.end(), make_pair(x, LONG_LONG_MAX));
		printf("%lld %lld\n", itF->second, itG->second);
	}
}