Cow Encryption

There are \(N\) cows (\(1 \leq N \leq 5\times10^4\)) and each cow \(i\) initially knows a number \(C_i\) (\(0 \le C_i < 9\times10^7\)). They devised an encryption method as follows: In one encryption operation, each cow \(i\) computes the sum of the numbers known by all the other cows, takes it modulo \(98\,765\,431\), and then replaces its own number with this value. Formally, if the current number on cow \(i\) is \(C_i\) and the sum of all numbers is \(S = \sum_{k=1}^N C_k\), then after one encryption operation the new number becomes

[ C_i' = \Bigl(\Bigl(\sum_{k=1}^{N}C_k - C_i\Bigr)\bmod 98,765,431\Bigr). ]

To enhance the security, the cows will perform this encryption process \(T\) times (\(1 \le T \le 1\,414\,213\,562\)).

Hint: Notice that the transformation is linear and can be diagonalized. In fact, the operation can be written as:

[ a' = (J-I)a, ]

where \(J\) is the all-ones matrix and \(I\) is the identity matrix. The eigenvalues of \(J-I\) are \(N-1\) (with multiplicity one) and \(-1\) (with multiplicity \(N-1\)). Therefore, if you decompose the initial numbers into a component along \((1,1,\ldots,1)\) and an orthogonal component, the answer after \(T\) iterations is given by:

[ C_i^{(T)} = (-1)^T C_i + \left((N-1)^T - (-1)^T\right)\frac{S}{N} \pmod{98,765,431}. ]

Your task is to compute the final numbers of all cows after \(T\) rounds of encryption.

inputFormat

The first line contains two integers \(N\) and \(T\). The second line contains \(N\) integers \(C_1, C_2, \ldots, C_N\), separated by spaces.

\(1 \leq N \leq 5\times10^4\)

\(0 \leq C_i < 9\times10^7\)

\(1 \leq T \leq 1\,414\,213\,562\)

outputFormat

Output a single line containing \(N\) integers representing the final numbers on the cows after \(T\) rounds of encryption, separated by spaces.

sample

3 1
1 2 3

5 4 3

</p>