#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
vector<pair<int, int>> factor_table;
ll power[400000];
const int N = 100000;
int spf[N];
vector<int> primes;
ll modpow(ll b, ll e, ll m) {
b %= m;
ll ret = 1;
while (e > 0) {
if (e & 1)
ret = (ret * b) % m;
b = (b * b) % m;
e >>= 1;
}
return ret;
}
ll egcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
ll x1, y1;
ll d = egcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}
ll inverse(ll a, ll m) {
ll x, y;
ll g = egcd(a, m, x, y);
if (g != 1)
return -1;
return (x % m + m) % m;
}
// returns n! % mod without taking all the multiple factors of p into account that appear in the factorial
// mod = multiple of p
// O(mod) * log(n)
int factmod(ll n, int p, const int mod) {
vector<int> f(mod + 1);
int ans = 1 % mod;
f[0] = 1 % mod;
for (int i = 1; i <= mod; i++) {
if (i % p) {
f[i] = 1LL * f[i - 1] * i % mod;
} else {
f[i] = f[i - 1];
}
}
while (n > 1) {
ans = 1LL * ans * f[n % mod] % mod;
ans = 1LL * ans * modpow(f[mod], n / mod, mod) % mod;
n /= p;
}
return ans;
}
ll g(ll n, int p) {
ll ans = 0;
while (n) {
n /= p;
ans += n;
}
return ans;
}
ll ncr(ll n, ll r, int p, int k) {
if (n < r or r < 0)
return 0;
int mod = 1;
for (int i = 0; i < k; i++) {
mod *= p;
}
ll t = g(n, p) - g(r, p) - g(n - r, p);
if (t >= k)
return 0;
ll ans = 1LL * factmod(n, p, mod);
ans = 1LL * ans * inverse(factmod(r, p, mod), mod) % mod;
ans = 1LL * ans * inverse(factmod(n - r, p, mod), mod) % mod;
ans = 1LL * ans * modpow(p, t, mod) % mod;
return ans;
}
pair<ll, ll> CRT(ll a1, ll m1, ll a2, ll m2) {
ll p, q;
ll g = egcd(m1, m2, p, q);
if (a1 % g != a2 % g)
return make_pair(0, -1);
ll m = m1 / g * m2;
p = (p % m + m) % m;
q = (q % m + m) % m;
return make_pair((p * a2 % m * (m1 / g) % m + q * a1 % m * (m2 / g) % m) % m, m);
}
void sieve() {
for(int i = 2; i < N; i++) {
if (spf[i] == 0) {
spf[i] = i;
primes.push_back(i);
}
int sz = (int) primes.size();
for (int j = 0; j < sz && i * primes[j] < N && primes[j] <= spf[i]; j++) {
spf[i * primes[j]] = primes[j];
}
}
}
ll ncr(ll n, ll r, int m) {
if (n < r or r < 0) return 0;
pair<ll, ll> ans({0, 1});
while (m > 1) {
int p = spf[m], k = 0, cur = 1;
while (m % p == 0) {
m /= p; cur *= p;
++k;
}
ans = CRT(ans.first, ans.second, ncr(n, r, p, k), cur);
}
return ans.first;
}
void fill_sieve(int n) {
factor_table.resize(n + 1);
for(int i = 1; i <= n; ++i)
factor_table[i] = pair<int, int>(i, 1);
for( int j = 2, j2 = 4; j2 <= n; (j2 += j), (j2 += ++j) ) {
if (factor_table[j].second == 1) {
int i = j, ij = j2;
while (ij <= n) {
factor_table[ij] = pair<int, int>(j, i);
i++;
ij += j;
}
}
}
}
void factor(int n, int d) {
while (n != 1) {
power[factor_table[n].first] += d;
n = factor_table[n].second;
}
}
vector<ll> mod_catalan(vector<ll> queries, ll m) {
vector<ll> catalans;
int n = (int)queries.back();
ll idx = 0;
ll val = 1;
fill_sieve(4 * n - 2);
power[1] = 1;
while (queries[idx] == 0) {
catalans.push_back(1);
idx++;
}
for (int k = 1; k <= n; k++) {
factor(4 * k - 2, 1);
factor(k + 1, -1);
if (queries[idx] == k) {
for(int i = 0; i < (4 * k - 1); i++) {
if (power[i] != 0) {
val *= modpow((ll)i, power[i], m);
val %= m;
}
}
}
while (queries[idx] == k) {
catalans.push_back((int)val);
idx++;
}
val = 1;
}
return catalans;
}
vector<ll> get_a(vector<ll> queries, ll m) {
vector<ll> even_val;
vector<ll> catalans;
ll val = 0;
ll idx = 0;
int len = (int)queries.size();
for(ll i: queries) {
if (i % 2 == 0) {
even_val.push_back(i / 2ll);
}
}
catalans = mod_catalan(even_val, m);
for (int i = 0; i < len; i++) {
val = modpow(2ll, queries[i], m);
cout << i << endl;
if (queries[i] % 2 == 0) {
val -= catalans[idx];
val %= m;
idx++;
}
queries[i] = val;
}
return queries;
}
vector<ll> get_b(vector<ll> queries, ll m) {
vector<ll> b_l;
deque<ll> b_q = {};
ll b_i = 1;
ll idx = 0;
ll mid = queries.back() / 2ll + 1ll;
for (int i = 1; i <= queries.back(); i++) {
if (i % 2) {
b_i = (2ll * b_i) % m;
} else {
b_i = (2ll * b_i - b_q.front()) % m;
b_q.pop_front();
}
if (i < mid) {
b_q.push_back(b_i);
}
while (i == queries[idx]) {
b_l.push_back(b_i);
idx++;
}
}
return b_l;
}
vector<ll> get_c(vector<ll> queries, ll m) {
vector<ll> even_range;
vector<ll> catalans;
vector<ll> a_l;
vector<ll> c_l = get_b(queries, m);
ll a;
ll even_max = 0;
for (ll i : queries) {
if (i % 2 == 0) {
even_max = i;
}
}
for (ll i = 0; i <= even_max / 2ll; i++)
even_range.push_back(i);
catalans = mod_catalan(even_range, m);
for (ll i = 0; i <= even_max / 2ll; i++) {
a = catalans[i];
for (ll j = 1; j <= i / 2ll; j++) {
a -= (catalans[i - 2ll * j] * a_l[j]) % m;
a %= m;
}
a_l.push_back(a);
}
for (ll i = 0; i < c_l.size(); i++) {
if (queries[i] % 2 == 0) {
c_l[i] -= a_l[queries[i] / 2ll];
c_l[i] %= m;
}
}
return c_l;
}
int test() {
vector<ll> result1;
vector<ll> result2;
vector<ll> result3;
vector<ll> result4;
vector<ll> idx;
vector<ll> queries;
ll m = 1000000;
// 쿼리 설정
for (int i = 1; i < 10000; i++) {
queries.push_back(i);
queries.push_back(i);
}
vector<ll> result(queries.size());
for (ll i = 0; i < queries.size(); i++) {
idx.push_back(i);
}
sort(idx.begin(), idx.end(), [&queries](size_t i, size_t j)
{ return queries[i] < queries[j]; });
sort(queries.begin(), queries.end());
result1 = mod_catalan(queries, m);
result2 = get_a(queries, m);
result3 = get_b(queries, m);
result4 = get_c(queries, m);
cout << "catalans" << endl;
for (int i = 0; i < queries.size(); i++) {
result[idx[i]] = result1[i];
if (result[idx[i]] < 0) {
result[idx[i]] += m;
}
}
for (ll i : result) {
cout << i << " ";
} cout << endl;
cout << "a" << endl;
for (int i = 0; i < queries.size(); i++) {
result[idx[i]] = result2[i];
if (result[idx[i]] < 0) {
result[idx[i]] += m;
}
}
for (ll i : result) {
cout << i << " ";
} cout << endl;
cout << "b" << endl;
for (int i = 0; i < queries.size(); i++) {
result[idx[i]] = result3[i];
if (result[idx[i]] < 0) {
result[idx[i]] += m;
}
}
for (ll i : result) {
cout << i << " ";
} cout << endl;
cout << "c" << endl;
for (int i = 0; i < queries.size(); i++) {
result[idx[i]] = result4[i];
if (result[idx[i]] < 0) {
result[idx[i]] += m;
}
}
for (ll i : result) {
cout << i << " ";
} cout << endl;
return 0;
}
int main() {
test();
ll p, q, m, Q, l;
vector<ll> queries;
vector<ll> result;
vector<ll> idx;
scanf("%lld %lld %lld %lld", &p, &q, &m, &Q);
for (int i = 0; i < Q; i++) {
scanf("%lld", &l);
queries.push_back(l);
idx.push_back(i);
}
sort(idx.begin(), idx.end(), [&queries](size_t i, size_t j)
{ return queries[i] < queries[j]; });
sort(queries.begin(), queries.end());
if (p == 1 && q == 0) {
result = get_a(queries, m);
} else if (p == 0 && q == 1) {
result = get_b(queries, m);
} else if (p == 1 && q == 1) {
result = get_c(queries, m);
} else {
return 0;
}
for (int i = 0; i < Q; i++) {
queries[idx[i]] = result[i];
if (queries[idx[i]] < 0) {
queries[idx[i]] += m;
}
}
for (ll i : queries) {
cout << i << endl;
}
return 0;
}
