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;
long long binomial[1000200];
long long n, m, a, q, cnt = 0l;
long long factorial[1000200];
long long order[1000200];
long long answer[1000200];
long long exp(long long b, long long deg, long long mod) {
  if (deg == 0) return 1l;
  if (deg == 1) return b;
  long long t = exp(b, deg / 2l, mod);
  if (deg % 2 == 0)
    return ((t * t) % mod);
  else
    return (((t * t) % mod) * b) % mod;
}
long long gcd(long long a, long long b) {
  if (b == 0l)
    return a;
  else
    return gcd(b, a % b);
}
long long red;
int main() {
  scanf("%I64d%I64d%I64d%I64d", &n, &m, &a, &q);
  order[0] = 1l;
  for (red = 1; red <= 1000200; red++) {
    order[red] = (order[red - 1] * a) % q;
    if (order[red] == 1l) break;
  }
  factorial[0] = 1l;
  for (int i = 1; i < red; i++)
    if (gcd(red, i) == 1l) cnt++;
  for (int i = 1; i <= m; i++) factorial[i] = (factorial[i - 1] * i) % red;
  binomial[0] = 1l;
  binomial[m] = 1l;
  for (int i = 1; i < m; i++) {
    long long m1 = m;
    long long i1 = i;
    binomial[i] = 1l;
    while (m1 > 0 || i1 > 0) {
      long long gornji = m1 % red;
      long long donji = i1 % red;
      if (gornji < donji) {
        binomial[i] = 0l;
        break;
      } else
        binomial[i] *=
            factorial[gornji] *
            exp(((factorial[donji] * factorial[gornji - donji]) % red),
                cnt - 1l, red);
      m1 /= red;
      i1 /= red;
    }
  }
  long long sum = 0l;
  for (int i = 0; i < n; i++) {
    if (i <= m) sum += binomial[i];
    sum %= red;
    answer[n - i - 1l] = order[sum];
  }
  for (int i = 0; i < n; i++) printf("%I64d ", answer[i]);
}
