Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

F. Product transformation

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputConsider an array *A* with *N* elements, all being the same integer *a*.

Define the product transformation as a simultaneous update *A*_{i} = *A*_{i}·*A*_{i + 1}, that is multiplying each element to the element right to it for , with the last number *A*_{N} 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* ≤ 10^{9} + 123, 2 ≤ *a* ≤ 10^{6} + 123, , is prime), where 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* , is the smallest natural number *x* such that *a*^{x} *mod* *Q* = 1. For example, .

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 03:48:49 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|