Summing Sums

Time limit1sMemory limit128 MB

Summary

Each round every cow replaces her number with the sum of the other cows' numbers mod 98765431; report the values after exactly T rounds.

Level: Medium7 of 10
Topics: Math, Matrix, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

$N$ cows, numbered $1$ through $N$ , each start with an integer $C_i$ . Every round, all cows act simultaneously:

Each cow computes the sum of the numbers held by the other $N-1$ cows.
Once every cow has finished, each cow replaces her own number with the sum she just computed.

To keep the numbers from growing too large, every number is always kept modulo 98,765,431. After the round has been repeated exactly $T$ times, report the number held by each cow.

Constraints:

$1 \le N \le 50{,}000$
$0 \le C_i < 90{,}000{,}000$
$1 \le T \le 1{,}414{,}213{,}562$

Input

Line 1: two space-separated integers $N$ and $T$ .
Lines 2 through $N+1$ : line $i+1$ contains the starting number $C_i$ of cow $i$ .

Output

Print $N$ lines; line $i$ contains the number held by cow $i$ after the repetitions finish, taken modulo 98,765,431.

Hint

The table below shows the cows' numbers after each round for the example.

          Cows' numbers
Round   Cow1  Cow2  Cow3
 0        1     0     4
 1        4     5     1
 2        6     5     9
 3       14    15    11
 4       26    25    29

Examples3

Example 1
Input
```
3 4
1
0
4
```
Expected output
```
26
25
29
```
Example 2
Input
```
3 1
1
0
4
```
Expected output
```
4
5
1
```
Example 3
Input
```
3 2
1
0
4
```
Expected output
```
6
5
9
```