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;
int n, m, a, q;
int MOD;
int const N = 1e6 + 1e5 + 13;
int f[N], invf[N];
int dp[N], ans[N];
int phi(int n) {
  int ret = n;
  for (int i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      ret -= ret / i;
      while (n % i == 0) n /= i;
    }
  }
  if (n != 1) ret -= ret / n;
  return ret;
}
int bp(int x, int d, int MOD) {
  int ret = 1;
  int cur = x;
  while (d) {
    if (d & 1) ret = ret * 1LL * cur % MOD;
    cur = cur * 1LL * cur % MOD;
    d >>= 1;
  }
  return ret;
}
void precalc() {
  f[0] = invf[0] = 1;
  for (int i = 1; i < N; ++i) {
    int v = i;
    dp[i] = dp[i - 1];
    while (v % MOD == 0) {
      ++dp[i];
      v /= MOD;
    }
    f[i] = f[i - 1] * 1LL * v % MOD;
    invf[i] = bp(f[i], MOD - 2, MOD);
  }
}
int getC(int k, int n) {
  if (k > n) return 0;
  int rem = dp[n] - dp[k] - dp[n - k];
  if (rem > 0) return 0;
  int ret = f[n];
  ret = ret * 1LL * invf[k] % MOD;
  ret = ret * 1LL * invf[n - k] % MOD;
  return ret;
}
void findMod() {
  int p = phi(q);
  vector<int> d;
  for (int i = 2; i * i <= p; ++i) {
    if (p % i == 0) {
      d.push_back(i);
      d.push_back(p / i);
    }
  }
  d.push_back(p);
  sort(d.begin(), d.end());
  for (int i = 0; i < d.size(); ++i) {
    if (bp(a, d[i], q) == 1) {
      MOD = d[i];
      return;
    }
  }
  assert(false);
}
void solve() {
  scanf("%d %d %d %d", &n, &m, &a, &q);
  findMod();
  precalc();
  int deg = 0;
  for (int i = 0; i < n; ++i) {
    deg += getC(i, m);
    deg %= MOD;
    ans[n - 1 - i] = bp(a, deg, q);
  }
  for (int i = 0; i < n; ++i) printf("%d ", ans[i]);
}
int main() {
  solve();
  return 0;
}
