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;
long long n, m, x, q, f[1000200], inv[1000200], pow2[1000200], P, phi, now,
    a[1000200], b[1000200];
long long C(long long a, long long b) {
  return f[a] * inv[b] % P * inv[a - b] % P;
}
long long sqr(long long x, long long P) { return x * x % P; }
long long poww(long long a, long long n, long long P) {
  if (n == 0) return 1;
  if (n % 2 == 0) return sqr(poww(a, n / 2, P), P);
  return sqr(poww(a, n / 2, P), P) * a % P;
}
int main() {
  scanf("%lld%lld%lld%lld", &n, &m, &x, &q);
  now = q;
  phi = q;
  long long i, j;
  for (i = 2; i * i <= q; i++) {
    if (now % i == 0) {
      phi = phi / i * (i - 1);
      while (now % i == 0) now /= i;
    }
  }
  if (now != 1) phi = phi / now * (now - 1);
  P = phi;
  for (i = 2; i * i <= phi; i++) {
    if (phi % i != 0) continue;
    if (poww(x, i, q) == 1) {
      P = i;
      break;
    }
    if (poww(x, phi / i, q) == 1) P = phi / i;
  }
  f[0] = 1;
  inv[0] = 1;
  pow2[0] = 1;
  for (i = 1; i <= m; i++) f[i] = f[i - 1] * i % P;
  for (i = 1; i <= m; i++) inv[i] = inv[i - 1] * poww(i, P - 2, P) % P;
  for (i = 1; i <= m; i++) pow2[i] = pow2[i - 1] * 2 % P;
  if (n > m) {
    for (i = 1; i <= n - m; i++) {
      a[i] = pow2[m];
    }
    for (j = 1; j <= m; j++) {
      a[n - m + j] = (a[n - m + j - 1] - C(m, j - 1)) % P + P;
      a[n - m + j] %= P;
    }
  } else {
    b[0] = 0;
    for (i = 1; i <= n; i++) {
      b[i] = b[i - 1] + C(m, i - 1);
      b[i] %= P;
    }
    for (i = 1; i <= n; i++) a[i] = b[n - i + 1];
  }
  for (i = 1; i <= n; i++) {
    printf("%lld ", poww(x, a[i], q));
  }
}
