Circle Cricket Elimination

Little Blue is passionate about cricket fighting. She has n distinct crickets arranged in a circle in clockwise order with labels from 1 to n. The i-th cricket has a fighting power \(a_i\), meaning that when it attacks another cricket it will knock down its opponent with probability \(a_i\) and fail with probability \(1 - a_i\).

The fight goes as follows: starting with cricket 1, while there is more than one cricket alive, the current cricket performs the following steps:

1. It chooses a direction uniformly at random (clockwise or counterclockwise, each with probability \(1/2\)).
2. It attacks the first cricket in the chosen direction that is still alive.
3. Regardless of whether the attack is successful (i.e. the opponent gets knocked down) or not, the next cricket in the clockwise order (from the current cricket, considering the most recent state) begins its turn.

The process ends when only one cricket remains. Little Blue wants to compute the probability that the surviving cricket is the i-th cricket. To avoid precision issues, you are required to output these probabilities modulo a given prime number m.

The probabilities and operations in the process are to be handled in \(\mathbb{Z}/m\mathbb{Z}\). In particular, when a division by 2 is needed, use the modular inverse of 2 modulo m.

inputFormat

The first line contains two integers n and m (\(1 \leq n \leq 16\), m is a prime number), where n is the number of crickets and m is the modulus.

The second line contains n integers: a₁, a₂, \( \dots \), a_n where each a_i represents the probability (in the field \(\mathbb{Z}/m\mathbb{Z}\)) that cricket i can knock down its opponent when it attacks.

outputFormat

Output a single line containing n space‐separated integers. The i-th integer represents the probability (expressed modulo m) that cricket i is the final survivor.

sample

1 17
3

1