Problem Description

$N$ cows ($1 \leq N \leq 5 \times 10^4$) have just learned a lot about cryptography. At last, they created a cow-only encryption method. Because they lack experience, their encryption method is very simple.

The $i$-th cow holds the $i$-th digit of the code, which is initially $C_i$ ($0 \leq C_i \lt 9 \times 10^7$). During encryption, the $i$-th cow computes the sum of the numbers of all other cows, and takes this sum modulo $98\,765\,431$. After all cows finish computing, each cow replaces her original number with the number she computed. That is,

In this way, they complete one encryption.

In November, the cows told this encryption method to Carmen the moose. After thinking for a while, Carmen said: "Your algorithm is still very primitive. To achieve an encryption effect, you need to repeat this encryption process $T$ times ($1 \leq T \leq 1\,414\,213\,562$)."

The cows are lazy, so they gave this task to you.

Input Format

The first line contains two integers $N, T$.

The next $N$ lines each contain one integer. The $i$-th line contains $C_i$.

Output Format

Output $N$ lines. The $i$-th line contains one integer, representing $C_i$ after $T$ encryptions.

3 4
1
0
4

26
25
29

Hint

After each encryption, $C_i$ is as follows:

Translated by ChatGPT 5