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;
int phi(int n) {
  int result = n;
  for (int 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 expo(long long base, long long exponent, long long mod) {
  long long ans = 1;
  while (exponent != 0) {
    if ((exponent & 1) == 1) {
      ans = ans * base;
      ans = ans % mod;
    }
    base = base * base;
    base %= mod;
    exponent >>= 1;
  }
  return ans % mod;
}
void solve() {
  int N, M, a, Q;
  cin >> N >> M >> a >> Q;
  int temp = 1;
  long long beta = a;
  for (;;) {
    if (beta == 1) break;
    beta = (1LL * beta * a) % Q;
    temp++;
  }
  vector<long long> x(M + 1);
  x[0] = 1;
  int alpha = phi(temp);
  for (int i = 1; i < M + 1; i++) {
    x[i] = x[i - 1] * (M + 1 - i);
    x[i] %= temp;
    x[i] *= expo(i, alpha - 1, temp);
    x[i] %= temp;
  }
  x.resize(N);
  for (int i = 1; i < N; i++) {
    x[i] = (x[i - 1] + x[i]) % temp;
  }
  for (int i = 0; i < N; i++) {
    x[i] = expo(a, x[i], Q);
  }
  reverse((x).begin(), (x).end());
  for (int i = 0; i < N; i++) cout << x[i] << " ";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
