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;
template <int n>
using AI = array<int, n>;
const double eps = 1e-9;
const int oo = 0x3F3F3F3F;
const long long ooLL = 0x3F3F3F3F3F3F3F3FLL;
const int MOD = 1000000007;
template <typename T>
T sqr(T x) {
  return x * x;
}
const double PI = acos(-1.);
long long Round(double x) { return x < 0 ? x - .5 : x + .5; }
int main() {
  void run();
  run();
  return 0;
}
int add(int a, int b, int m) { return (a + b) % m; }
int mul(long long a, int b, int m) { return a * b % m; }
int pw(int a, int p, int m) {
  int rs = 1;
  while (p) {
    if (p & 1) rs = mul(rs, a, m);
    p >>= 1;
    a = mul(a, a, m);
  }
  return rs;
}
int inv(int a, int p) {
  int b = p, r1 = 1, r2 = 0;
  while (b) {
    int q = a / b;
    a -= q * b;
    swap(a, b);
    r1 -= q * r2;
    swap(r1, r2);
  }
  if (r1 < 0) r1 += p;
  return r1;
}
int n, m, a, q, p, rs[1 << 20];
void run() {
  scanf("%d %d %d %d", &n, &m, &a, &q);
  int a0 = a;
  p = 1;
  while (a0 != 1) a0 = mul(a0, a, q), ++p;
  int s = 1, l = 1, k = 1;
  for (int i = (n - 1), _b(0); i >= _b; --i) {
    int t = min(m + 1, n - i);
    while (k < t) {
      l = mul(l, m - k + 1, p);
      l = mul(l, inv(k, p), p);
      s = add(s, l, p);
      ++k;
    }
    rs[i] = pw(a, s, q);
  }
  for (int i = (0), _b(n); i < _b; ++i) printf("%d%c", rs[i], "\n "[i + 1 < n]);
}
