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;
using ll = int64_t;
class CerrDummy {
} cerrDummy;
template <class T>
CerrDummy& operator<<(CerrDummy& cd, const T&) {
  return cd;
}
using charTDummy = char;
using traitsDummy = char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy& cd,
                      basic_ostream<charTDummy, traitsDummy>&(
                          basic_ostream<charTDummy, traitsDummy>&)) {
  return cd;
}
using pi = pair<ll, ll>;
using vi = vector<ll>;
using ld = long double;
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (ll i = ll(0); i < ll((ll)v.size()); i++) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}
ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}
void printSpace() { printf(" "); }
void printEoln() { printf("\n"); }
void print(ll x, ll suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1) printEoln();
  if (suc == 2) printSpace();
}
string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}
char* readCharArray() {
  static char buf[3341000];
  static ll bufUsed = 0;
  char* ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}
template <class T, class U>
void chmax(T& a, U b) {
  if (a < b) a = b;
}
template <class T, class U>
void chmin(T& a, U b) {
  if (b < a) a = b;
}
template <class T>
T Sq(const T& t) {
  return t * t;
}
void Yes(bool ex = true) {
  cout << "YES" << endl;
  if (ex) exit(0);
}
void No(bool ex = true) {
  cout << "NO" << endl;
  if (ex) exit(0);
}
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
ll mod;
template <class T, class U>
void add(T& a, U b) {
  a += b;
  if (a >= mod) a -= mod;
}
template <class T, class U>
void sub(T& a, U b) {
  a -= b;
  if (a < 0) a += mod;
}
template <class T, class U>
void mult(T& a, U b) {
  a = ((ll)a * b) % mod;
}
ll modPow(ll a, ll p) {
  ll s = 1;
  while (p) {
    if (p & 1) mult(s, a);
    mult(a, a);
    p >>= 1;
  }
  return s;
}
ll modInv(ll a) { return modPow(a, mod - 2); }
const ll Vmax = 1001000;
ll fact[Vmax], factInv[Vmax], invs[Vmax];
void InitFact() {
  ll vv = mod;
  fact[0] = 1;
  for (ll i = ll(1); i < ll(vv); i++) {
    fact[i] = fact[i - 1];
    mult(fact[i], i);
  }
  factInv[vv - 1] = modInv(fact[vv - 1]);
  for (ll i = vv - 2; i >= 0; i--) {
    factInv[i] = factInv[i + 1];
    mult(factInv[i], i + 1);
  }
  for (ll i = vv - 1; i >= 1; i--) {
    invs[i] = factInv[i];
    mult(invs[i], fact[i - 1]);
  }
}
ll Choose(ll n, ll k) {
  return ll(fact[n]) * factInv[n - k] % mod * factInv[k] % mod;
}
ll Binom(ll a, ll b) {
  return ll(fact[a + b]) * factInv[a] % mod * factInv[b] % mod;
}
signed main() {
  ll n = read(), m = read(), a = read(), q = read();
  vi ans(n, 0);
  a %= q;
  if (a > 0) {
    ll x = 1;
    {
      ll cur = a;
      while (cur != 1) {
        x++;
        cur *= a;
        cur %= q;
      }
    }
    cerrDummy << x << endl;
    mod = x;
    InitFact();
    ll w = 0;
    for (ll i = n - 1; i >= 0; i--) {
      ll c = n - 1 - i;
      if (c <= m) add(w, Choose(m, c));
      ans[i] = 1;
      ll cur = a, rem = w;
      while (rem) {
        if (rem & 1) {
          ans[i] *= cur;
          ans[i] %= q;
        }
        cur *= cur;
        cur %= q;
        rem >>= 1;
      }
    }
  }
  for (ll i = ll(0); i < ll(n); i++) print(ans[i], i == n - 1 ? 1 : 2);
}
