Consider an array A with N elements, all being the same integer a.

Define the product transformation as a simultaneous update Ai = Ai·Ai + 1, that is multiplying each element to the element right to it for <image>, with the last number AN remaining the same. For example, if we start with an array A with a = 2 and N = 4, then after one product transformation A = [4, 4, 4, 2], and after two product transformations A = [16, 16, 8, 2].

Your simple task is to calculate the array A after M product transformations. Since the numbers can get quite big you should output them modulo Q.

Input

The first and only line of input contains four integers N, M, a, Q (7 ≤ Q ≤ 109 + 123, 2 ≤ a ≤ 106 + 123, <image>, <image> is prime), where <image> is the multiplicative order of the integer a modulo Q, see notes for definition.

Output

You should output the array A from left to right.

Example

Input

2 2 2 7


Output

1 2 

Note

The multiplicative order of a number a modulo Q <image>, is the smallest natural number x such that ax mod Q = 1. For example, <image>.
#include <bits/stdc++.h>
using namespace std;
template <class T>
using vv = vector<vector<T>>;
template <class T>
ostream &operator<<(ostream &os, const vector<T> &t) {
  os << "{";
  for (int(i) = 0; (i) < (t.size()); ++(i)) {
    os << t[i] << ",";
  }
  os << "}" << endl;
  return os;
}
template <class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &t) {
  return os << "(" << t.first << "," << t.second << ")";
}
template <class T>
inline bool MX(T &l, const T &r) {
  return l < r ? l = r, 1 : 0;
}
template <class T>
inline bool MN(T &l, const T &r) {
  return l > r ? l = r, 1 : 0;
}
vector<string> s_p_l_i_t(const string &s, char c) {
  vector<string> v;
  int d = 0, f = 0;
  string t;
  for (char c : s) {
    if (!d && c == ',')
      v.push_back(t), t = "";
    else
      t += c;
    if (c == '\"' || c == '\'') f ^= 1;
    if (!f && c == '(') ++d;
    if (!f && c == ')') --d;
  }
  v.push_back(t);
  return move(v);
}
void e_r_r(vector<string>::iterator it) {}
template <typename T, typename... Args>
void e_r_r(vector<string>::iterator it, T a, Args... args) {
  if (*it == " 1" || *it == "1")
    cerr << endl;
  else
    cerr << it->substr((*it)[0] == ' ', it->length()) << " = " << a << ", ";
  e_r_r(++it, args...);
}
long long MOD;
long long modpow(long long r, long long n, long long m = MOD) {
  long long re = 1, d = r % m;
  if (n < 0) (n %= m - 1) += m - 1;
  for (; n; n /= 2) {
    if (n & 1) (re *= d) %= m;
    (d *= d) %= m;
  }
  return re;
}
vector<long long> fact, finv, inv;
long long comb(long long n, long long r) {
  if (n < r || r < 0) return 0;
  if (n < MOD && r < MOD) return fact[n] * finv[n - r] % MOD * finv[r] % MOD;
  return comb(n / MOD, r / MOD) * comb(n % MOD, r % MOD);
}
class Doralion {
  void Modinvs(vector<long long> &re, int n) {
    re.resize(n + 1);
    re[1] = 1;
    for (int i = 2; i <= n; ++i) re[i] = re[MOD % i] * (MOD - MOD / i) % MOD;
  }
  void Facts(vector<long long> &re, int n) {
    re.resize(n + 1);
    re[0] = 1;
    for (int(i) = 0; (i) < (n); ++(i)) re[i + 1] = re[i] * (i + 1) % MOD;
  }
  void Factinvs(vector<long long> &re, const vector<long long> &inv, int n) {
    re.resize(n + 1);
    re[0] = 1;
    for (int(i) = 0; (i) < (n); ++(i)) re[i + 1] = re[i] * inv[i + 1] % MOD;
  }

 public:
  Doralion(int n) {
    Modinvs(inv, n);
    Facts(fact, n);
    Factinvs(finv, inv, n);
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(0);
  long long n, m, a, q;
  cin >> n >> m >> a >> q;
  long long mod = 1;
  for (long long p = a; p != 1; (p *= a) %= q) ++mod;
  MOD = mod;
  Doralion doralion(2123456);
  vector<long long> sum(m + 1);
  for (int(i) = 0; (i) < (m + 1); ++(i)) sum[i] = comb(m, i);
  for (int(i) = 0; (i) < (m); ++(i)) sum[i + 1] += sum[i];
  vector<long long> re(n);
  for (int(i) = 0; (i) < (n); ++(i)) re[i] = sum[min(m, n - 1 - i)];
  for (int(i) = 0; (i) < (n); ++(i))
    cout << modpow(a, re[i], q) << " \n"[i + 1 == n];
  return 0;
}
