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 MOD[] = {1000000007, 998244353, 998244853};
template <int ITH>
struct modular {
  constexpr modular() : val(0) {}
  constexpr modular(const modular& _m) : val(_m.val) {}
  template <typename U>
  constexpr modular(const U& _r = U()) {
    val = -MOD[ITH] <= _r && _r < MOD[ITH] ? _r : _r % MOD[ITH];
    if (val < 0) {
      val += MOD[ITH];
    }
  }
  const int operator()() { return val; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(val);
  }
  modular& operator+=(const modular& _m) {
    if ((val += _m.val) >= MOD[ITH]) {
      val -= MOD[ITH];
    }
    return *this;
  }
  modular& operator-=(const modular& _m) {
    if ((val -= _m.val) < 0) {
      val += MOD[ITH];
    }
    return *this;
  }
  modular& operator*=(const modular& _m) {
    val = modular(static_cast<int64_t>(val) * static_cast<int64_t>(_m.val)).val;
    return *this;
  }
  modular& operator/=(const modular& _m) {
    int a = _m.val, b = MOD[ITH], u = 0, v = 1;
    while (a != 0) {
      int q = b / a;
      b -= q * a;
      swap(a, b);
      u -= q * v;
      swap(u, v);
    }
    return *this *= u;
  }
  modular& operator=(const modular& _m) {
    val = _m.val;
    return *this;
  }
  template <typename U>
  modular& operator+=(const U& _r) {
    return *this += modular(_r);
  }
  template <typename U>
  modular& operator-=(const U& _r) {
    return *this -= modular(_r);
  }
  template <typename U>
  modular& operator*=(const U& _r) {
    return *this *= modular(_r);
  }
  template <typename U>
  modular& operator/=(const U& _r) {
    return *this /= modular(_r);
  }
  template <typename U>
  modular& operator=(const U& _r) {
    val = modular(_r).val;
    return *this;
  }
  modular operator-() { return modular(-val); }
  template <typename U>
  friend bool operator==(const modular&, const modular&);
  friend std::istream& operator>>(std::istream& os, modular& _m) {
    os >> _m.val;
    _m *= 1;
    return os;
  }
  friend std::ostream& operator<<(std::ostream& os, const modular& _m) {
    return os << _m.val;
  }
  template <typename U>
  modular exp(U e) {
    modular res = 1;
    modular b = val;
    if (e < 0) {
      b = 1 / b;
      e *= -1;
    }
    for (; e; e >>= 1) {
      if (e & 1) {
        res *= b;
      }
      b *= b;
    }
    return res;
  }

 private:
  int val;
};
template <int ITH>
inline modular<ITH> operator+(const modular<ITH>& _lhs,
                              const modular<ITH>& _rhs) {
  return modular<ITH>(_lhs) += _rhs;
}
template <int ITH, typename U>
inline modular<ITH> operator+(const modular<ITH>& _lhs, const U& _rhs) {
  return modular<ITH>(_lhs) += _rhs;
}
template <int ITH, typename U>
inline modular<ITH> operator+(const U& _lhs, const modular<ITH>& _rhs) {
  return modular<ITH>(_lhs) += _rhs;
}
template <int ITH>
inline modular<ITH> operator-(const modular<ITH>& _lhs,
                              const modular<ITH>& _rhs) {
  return modular<ITH>(_lhs) -= _rhs;
}
template <int ITH, typename U>
inline modular<ITH> operator-(const modular<ITH>& _lhs, const U& _rhs) {
  return modular<ITH>(_lhs) -= _rhs;
}
template <int ITH, typename U>
inline modular<ITH> operator-(const U& _lhs, const modular<ITH>& _rhs) {
  return modular<ITH>(_lhs) -= _rhs;
}
template <int ITH>
inline modular<ITH> operator*(const modular<ITH>& _lhs,
                              const modular<ITH>& _rhs) {
  return modular<ITH>(_lhs) *= _rhs;
}
template <int ITH, typename U>
inline modular<ITH> operator*(const modular<ITH>& _lhs, const U& _rhs) {
  return modular<ITH>(_lhs) *= _rhs;
}
template <int ITH, typename U>
inline modular<ITH> operator*(const U& _lhs, const modular<ITH>& _rhs) {
  return modular<ITH>(_lhs) *= _rhs;
}
template <int ITH>
inline modular<ITH> operator/(const modular<ITH>& _lhs,
                              const modular<ITH>& _rhs) {
  return modular<ITH>(_lhs) /= _rhs;
}
template <int ITH, typename U>
inline modular<ITH> operator/(const modular<ITH>& _lhs, const U& _rhs) {
  return modular<ITH>(_lhs) /= _rhs;
}
template <int ITH, typename U>
inline modular<ITH> operator/(const U& _lhs, const modular<ITH>& _rhs) {
  return modular<ITH>(_lhs) /= _rhs;
}
template <int ITH>
inline bool operator==(const modular<ITH>& _lhs, const modular<ITH>& _rhs) {
  return _lhs.val == _rhs.val;
}
template <int ITH, typename U>
inline bool operator==(const modular<ITH>& _lhs, const U& _rhs) {
  return _lhs == modular<ITH>(_rhs);
}
template <int ITH, typename U>
inline bool operator==(const U& _lhs, const modular<ITH>& _rhs) {
  return modular<ITH>(_lhs) == _rhs;
}
template <int ITH>
inline bool operator!=(const modular<ITH>& _lhs, const modular<ITH>& _rhs) {
  return !(_lhs == _rhs);
}
template <int ITH, typename U>
inline bool operator!=(const modular<ITH>& _lhs, const U& _rhs) {
  return !(_lhs == _rhs);
}
template <int ITH, typename U>
inline bool operator!=(const U& _lhs, const modular<ITH>& _rhs) {
  return !(_lhs == _rhs);
}
const int N = 1e6 + 155;
struct Comb {
  int N;
  vector<modular<1> > fac, ifac, inv;
  Comb(int _n = 1) {
    resize(2);
    fac[0] = fac[1] = ifac[0] = ifac[1] = inv[1] = 1;
    N = 1;
    grow(_n);
  }
  void resize(int _s) {
    fac.resize(_s);
    ifac.resize(_s);
    inv.resize(_s);
  }
  bool grow(int _n) {
    if (_n <= N) return false;
    swap(_n, N);
    resize(N + 1);
    for (int i = _n + 1; i <= N; i++) {
      fac[i] = fac[i - 1] * i;
      inv[i] = (-MOD[1] / i) * inv[MOD[1] % i];
      ifac[i] = ifac[i - 1] * inv[i];
    }
    return true;
  }
  modular<1> a(int n, int k) {
    if (n < k || k < 0) return 0;
    if (n > N) grow(n);
    return fac[n] * ifac[n - k];
  }
  modular<1> c(int n, int k) {
    if (n < k || k < 0) return 0;
    if (n > N) grow(n);
    return fac[n] * ifac[n - k] * ifac[k];
  }
};
void solve() {
  int n, m, _a;
  cin >> n >> m >> _a >> MOD[0];
  int phi = 2;
  modular<0> a = _a;
  modular<0> prod = a;
  for (; phi < N; phi++) {
    prod *= a;
    if ((int)prod == 1) break;
  }
  assert(phi < N);
  assert((int)a.exp(phi) == 1);
  MOD[1] = phi;
  Comb c(max(n, m) + 10);
  vector<modular<1> > es(n);
  modular<1> sum = 0;
  for (int i = 0; i < n; i++) {
    sum += c.c(m, i);
    es[i] = sum;
  }
  for (int i = n - 1; i >= 0; i--) {
    int res = (int)(a.exp((int)es[i]));
    cout << res << ' ';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
  cout << endl;
}
