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;
vector<long long> oneVector;
long long gcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
inline long long gcd(long long a, long long b) { return gcd(a, b, a, b); }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long llrand() {
  const long long lsbToFill = (sizeof(long long) << 3) - 1;
  const long long bitsFilledInIteration = __builtin_popcountll(RAND_MAX);
  long long number = 0;
  for (long long lsbFilled = 0; lsbFilled <= lsbToFill;
       lsbFilled += bitsFilledInIteration) {
    number ^= (((long long)rand()) << lsbFilled);
  }
  return number & numeric_limits<long long>::max();
}
long long q;
vector<long long> operator*(const vector<long long> &a,
                            const vector<long long> &b) {
  vector<long long> result(int((a).size()));
  for (int i = (0); i < (int((a).size())); ++i) {
    for (int j = (0); j < (int((b).size())); ++j) {
      int k = (i + j) % int((b).size());
      result[j] = (a[i] * b[k] % q + result[j]);
    }
  }
  return result;
}
template <class T>
inline T sqr(const T &x) {
  return x * x;
}
template <class T>
T binpow(const T &a, long long n) {
  return n == 0 ? oneVector : sqr(binpow(a, n / 2)) * (n % 2 ? a : oneVector);
}
inline long long sqr(int x) { return sqr<long long>(x); }
long long binpow(long long a, long long n, long long modulo) {
  return n == 0 ? 1
                : sqr(binpow(a, n / 2, modulo)) % modulo * (n % 2 ? a : 1) %
                      modulo;
}
long long phi(long long n) {
  long long result = n;
  for (long long i = 2; i * i <= n; ++i)
    if (n % i == 0) {
      while (n % i == 0) n /= i;
      result -= result / i;
    }
  if (n > 1) result -= result / n;
  return result;
}
long long inverse(long long n, long long modulo, long long phi) {
  return binpow(n, phi - 1, modulo);
}
vector<long long> solve(int n, int m, long long a) {
  vector<long long> powers(n);
  vector<long long> factoreal(m + 1);
  factoreal[0] = 1;
  long long ORDER = 1;
  long long aPower = a;
  while (aPower != 1) {
    aPower = aPower * a % q;
    ++ORDER;
  }
  for (int i = 1; i <= m; ++i) {
    factoreal[i] = factoreal[i - 1] * i % ORDER;
  }
  if (1 == n) {
    powers[0] = 1;
  } else {
    const long long PHI = phi(ORDER);
    vector<long long> binom(n);
    for (int i = (0); i < (min(m + 1, n)); ++i) {
      binom[i] = factoreal[m] * inverse(factoreal[i], ORDER, PHI) % ORDER *
                 inverse(factoreal[m - i], ORDER, PHI) % ORDER;
    }
    powers[0] = 1;
    for (int i = (1); i < (n); ++i) {
      powers[i] = (powers[i - 1] + binom[i]) % ORDER;
    }
  }
  vector<long long> answer(n);
  for (int i = n - 1; i >= 0; --i) {
    answer[n - i - 1] = binpow(a, powers[i], q);
  }
  return answer;
}
vector<long long> bf(int n, int m, long long A) {
  vector<vector<long long> > a(m + 1, vector<long long>(n, A));
  for (int i = (0); i < (m); ++i) {
    for (int j = (0); j < (n - 1); ++j) {
      a[i + 1][j] = a[i][j] * a[i][j + 1] % q;
    }
    a[i + 1][n - 1] = a[i][n - 1];
  }
  return a[m];
}
void generate(int &n, int &m, long long &a) {
  q = 7919;
  n = 1 + rand() % 20;
  m = 1 + rand() % 20;
  a = 2 + rand() % 100;
}
void stress() {
  while (true) {
    int n, m;
    long long a;
    generate(n, m, a);
    const auto o = solve(n, m, a);
    const auto aa = bf(n, m, a);
    if (o != aa) {
      cerr << n << ' ' << m << ' ' << a << ' ' << q << endl;
      break;
    }
  }
}
int main(int argc, const char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  srand((unsigned int)time(NULL));
  int n, m;
  long long a;
  while (cin >> n >> m >> a >> q) {
    vector<long long> answer = solve(n, m, a);
    for (int i = (0); i < (int((answer).size())); ++i) {
      cout << answer[i] << ' ';
    }
    cout << endl;
  }
  return 0;
}
