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;
struct Scanner {
  bool hasNext = 1;
  bool hasRead = 1;
  int nextInt() {
    hasRead = 0;
    int res = 0;
    char flag = 1, ch = getchar();
    while (ch != EOF && !isdigit(ch)) {
      hasRead = 1;
      flag = (ch == '-') ? -flag : flag;
      ch = getchar();
    }
    while (ch != EOF && isdigit(ch)) {
      hasRead = 1;
      res = res * 10 + (ch - '0');
      ch = getchar();
    }
    if (ch == EOF) hasNext = 0;
    return res * flag;
  }
  long long nextLL() {
    hasRead = 0;
    long long res = 0;
    char flag = 1, ch = getchar();
    while (ch != EOF && !isdigit(ch)) {
      hasRead = 1;
      flag = (ch == '-') ? -flag : flag;
      ch = getchar();
    }
    while (ch != EOF && isdigit(ch)) {
      hasRead = 1;
      res = res * 10 + (ch - '0');
      ch = getchar();
    }
    if (ch == EOF) hasNext = 0;
    return res * flag;
  }
  char nextChar() {
    hasRead = 0;
    char ch = getchar();
    while (ch != EOF && isspace(ch)) {
      hasRead = 1;
      ch = getchar();
    }
    if (ch == EOF) hasNext = 0;
    return ch;
  }
  int nextString(char *str) {
    hasRead = 0;
    int len = 0;
    char ch = getchar();
    while (ch != EOF && isspace(ch)) {
      hasRead = 1;
      ch = getchar();
    }
    while (ch != EOF && !isspace(ch)) {
      hasRead = 1;
      str[++len] = ch;
      ch = getchar();
    }
    str[len + 1] = 0;
    if (ch == EOF) hasNext = 0;
    return len;
  }
} sc;
long long rd() {
  long long x = sc.nextLL();
  return x;
}
void rd(int &x) { x = sc.nextInt(); }
void rd(long long &x) { x = sc.nextLL(); }
void rd(char &x) { x = sc.nextChar(); }
void rd(char *x) { sc.nextString(x); }
template <typename T1, typename T2>
void rd(pair<T1, T2> &x) {
  rd(x.first);
  rd(x.second);
}
template <typename T>
void rd(T *x, int n) {
  for (int i = 1; i <= n; ++i) rd(x[i]);
}
void printInt(int x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x >= 10) printInt(x / 10);
  putchar('0' + x % 10);
}
void printLL(long long x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x >= 10) printLL(x / 10);
  putchar('0' + x % 10);
}
void pr(int x, char ch = '\n') {
  printInt(x);
  putchar(ch);
}
void pr(long long x, char ch = '\n') {
  printLL(x);
  putchar(ch);
}
template <typename T1, typename T2>
void pr(pair<T1, T2> x, char ch = '\n') {
  pr(x.first, ' ');
  pr(x.second, ch);
}
template <typename T>
void pr(T *x, int n) {
  for (int i = 1; i <= n; ++i) pr(x[i], " \n"[i == n]);
}
template <typename T>
void pr(vector<T> &x) {
  int n = x.size();
  for (int i = 1; i <= n; ++i) pr(x[i - 1], " \n"[i == n]);
}
template <typename T>
void cmin(T &x, T y) {
  if (y < x) x = y;
}
template <typename T>
void cmax(T &x, T y) {
  if (y > x) x = y;
}
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double EPS = 1e-9;
const int MAXN = 2e6 + 10;
int p[MAXN], ptop;
int pm[MAXN];
void sieve(int n) {
  pm[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!pm[i]) p[++ptop] = i, pm[i] = i;
    for (int j = 1; j <= ptop; ++j) {
      int t = i * p[j];
      if (t > n) break;
      pm[t] = p[j];
      if (i % p[j])
        ;
      else
        break;
    }
  }
}
int phi(int n) {
  int res = n;
  for (int i = 1; p[i] * p[i] <= n; ++i) {
    if (n % p[i] == 0) {
      res = res / p[i] * (p[i] - 1);
      while (n % p[i] == 0) n /= p[i];
    }
  }
  if (n > 1) res = res / n * (n - 1);
  return res;
}
int n, m, a, q;
long long MOD;
long long inv[MAXN], fac[MAXN], invfac[MAXN];
long long qpow(long long x, long long n, long long MOD) {
  long long res = 1;
  for (; n; n >>= 1) {
    if (n & 1) res = res * x % MOD;
    x = x * x % MOD;
  }
  return res;
}
void init(int n) {
  inv[1] = 1;
  for (int i = 2; i <= n; ++i) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
  fac[0] = 1, invfac[0] = 1;
  for (int i = 1; i <= n; ++i) {
    fac[i] = fac[i - 1] * i % MOD;
    invfac[i] = invfac[i - 1] * inv[i] % MOD;
  }
}
long long ddC[MAXN];
long long prefixC[MAXN];
long long C(long long n, long long m) {
  if (n < m) return 0;
  return fac[n] * invfac[n - m] % MOD * invfac[m] % MOD;
}
long long A[MAXN];
struct Solver {
  void InitOnce() { sieve(MAXN - 1); }
  void Read() {
    rd(n);
    rd(m);
    rd(a);
    rd(q);
  }
  void Solve() {
    for (MOD = 1;; ++MOD) {
      if (qpow(a, MOD, q) == 1) break;
    }
    init(max(n, m));
    for (int i = 0; i <= n; ++i) ddC[n - i] = C(m, i);
    ddC[n + 1] = 0;
    for (int i = n; i >= 0; --i) prefixC[i] = prefixC[i + 1] + ddC[i];
    a %= q;
    for (int i = 1; i <= n; ++i) A[i] = qpow(a, prefixC[i], q) % q;
    pr(A, n);
  }
} solver;
int main() {
  solver.InitOnce();
  int t = 1;
  t = INF;
  while (t--) {
    solver.Read();
    if (!sc.hasRead) break;
    solver.Solve();
    if (!sc.hasNext) break;
  }
  return 0;
}
