Information Propagation in an m-Dimensional Hypercube

A magical hypercube is given which is an m-dimensional cube with n = 2^m vertices. The vertices are numbered from 0 to n-1. For a vertex i, its coordinate is obtained by writing i in binary with exactly m digits (padding with 0’s in the front if necessary). Two vertices are adjacent if the Euclidean distance between them is 1 (i.e. they are connected by an edge in the hypercube).

Each vertex i initially holds an integer value p_i. In each cycle, every vertex sends its entire current information to each of its adjacent (neighboring) vertices and it resets its own value to 0. In other words, after one cycle, the new value at vertex i will be the sum of the values of its m neighbors from the previous cycle.

Your task is: given the initial values at all vertices, predict the value at each vertex after t cycles. Since the results can be huge, output every result modulo a given integer mod.

Note on the process: Let \(A\) be the \(n\times n\) adjacency matrix of the hypercube. Then the transformation in one cycle is \(f \to A\,f\), so after \(t\) cycles the state is \(A^{t}f\). It turns out that using the Walsh-Hadamard transform one can diagonalize this operation. In fact, for each frequency (represented as a bitmask \(u\) with \(0\le u < 2^m\)), the eigenvalue is

[ \lambda(u)= m- 2\cdot \mathrm{popcount}(u), ]

Thus, if \(F(u)\) is the Walsh-Hadamard transform (WHT) of the initial vector, then after \(t\) cycles each frequency component becomes \(F(u)\cdot \lambda(u)^{t}\). Finally, the inverse WHT (with division by \(n=2^m\)) recovers the answer. Use an efficient implementation since \(m\) can be as large as 20 and \(t\) can be up to \(10^{18}\).

inputFormat

The first line contains three integers: m (the dimension of the hypercube), t (the number of cycles), and mod (the modulus for answers).

The second line contains n = 2m integers, where the i-th integer (pi) represents the initial information at vertex i.

outputFormat

Output a single line with n = 2m integers: the information at vertices 0 through n-1 after t cycles, each taken modulo mod. The numbers should be separated by spaces.

sample

1 1 1000
1 2

2 1