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;
inline int read() {
  char ch = getchar();
  int x = 0, f = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int fac[2000010], inv[2000010], f[2000010];
inline int Power(int x, int y, int Q) {
  int ret = 1;
  while (y) {
    if (y & 1) ret = 1ll * ret * x % Q;
    x = (1ll * x * x) % Q;
    y >>= 1;
  }
  return ret;
}
int main() {
  int n = read(), m = read(), a = read(), Q = read();
  int p = 1;
  for (int i = a; i != 1; i = (1ll * i * a % Q), p++)
    ;
  fac[1] = 1;
  for (int i = (2); i <= (max(n, m)); i++) fac[i] = 1ll * fac[i - 1] * i % p;
  inv[0] = inv[1] = 1;
  for (int i = (2); i <= (max(n, m)); i++)
    inv[i] = 1ll * (p - p / i) * inv[p % i] % p;
  for (int i = (2); i <= (max(n, m)); i++)
    inv[i] = 1ll * inv[i - 1] * inv[i] % p;
  f[0] = 1;
  for (int i = (1); i <= (m); i++) {
    f[i] = (f[i - 1] + (1ll * fac[m] * inv[m - i] % p * inv[i] % p)) % p;
  }
  for (int i = (m + 1); i <= (n); i++) f[i] = f[i - 1];
  for (int i = n; i >= 1; i--) printf("%d ", Power(a, f[i - 1], Q));
  return 0;
}
