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>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
template <typename T>
void etch(T V) {
  for (auto x : V) cout << x << ' ';
  cout << '\n';
}
vector<string> vec_splitter(string s) {
  s += ',';
  vector<string> res;
  while (!s.empty()) {
    res.push_back(s.substr(0, s.find(',')));
    s = s.substr(s.find(',') + 1);
  }
  return res;
}
void debug_out(vector<string> __attribute__((unused)) args,
               __attribute__((unused)) long long int idx,
               __attribute__((unused)) long long int LINE_NUM) {
  cerr << endl;
}
template <typename Head, typename... Tail>
void debug_out(vector<string> args, long long int idx, long long int LINE_NUM,
               Head H, Tail... T) {
  if (idx > 0)
    cerr << ", ";
  else
    cerr << "Line(" << LINE_NUM << ") ";
  stringstream ss;
  ss << H;
  cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
long long int MOD = 1e9 + 7;
const long long int MOD1 = 998244353;
const long long int N = 1e6 + 125;
const long long int INF = 1000111000111000111LL;
const long double EPS = 1e-12;
const long double PI = 3.141592653589793116;
long long int modular_exp(long long int base, long long int exp,
                          long long int mod) {
  long long int ans = 1;
  while (exp) {
    if (exp % 2) ans = ans % mod * base % mod;
    base = (base % mod * base % mod) % mod;
    exp /= 2;
    ans %= mod;
  }
  return ans;
}
long long int multiplicative_order(long long int a, long long int Q) {
  for (long long int p = 1;; p++) {
    if (modular_exp(a, p, Q) == 1) return p;
  }
}
long long int inv_mod(long long int base, long long int mod) {
  return modular_exp(base, mod - 2, mod);
}
long long int fact[N];
void pre_compute() {
  fact[0] = 1;
  for (long long int i = 1; i < N; i++) {
    fact[i] = i * fact[i - 1];
    fact[i] %= MOD;
  }
}
long long int nCr(long long int n, long long int r) {
  if (r >= n or r == 0) return 1;
  return ((fact[n] % MOD * inv_mod(fact[r], MOD) % MOD) *
          inv_mod(fact[n - r], MOD)) %
         MOD;
}
void add(long long int &a, long long int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
int32_t main() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int n, m, a, Q;
  cin >> n >> m >> a >> Q;
  vector<long long int> v(n);
  MOD = multiplicative_order(a, Q);
  pre_compute();
  v[n - 1] = a % Q;
  long long int r = 1, cum = 1;
  for (long long int i = n - 2; i >= 0; i--) {
    if (n - i <= m) {
      add(cum, nCr(m, r++));
      v[i] = modular_exp(a, cum, Q);
    } else {
      long long int exp = modular_exp(2, m, MOD);
      v[i] = modular_exp(a, exp, Q);
    }
  }
  etch(v);
  return 0;
}
