$N$ 頭 $(1 \le N \le 50,000)$ の牛は便宜上 $1..N$ と番号を付けられ、暗号化アルゴリズムを学習中です。例をいくつか見て自作を決めましたが、未熟なので単純です：
牛 $i$ の初期値は $C_i$ $(0 \le C_i < 90,000,000)$、全員が並列に次を行います：
- まず各牛は他の $N-1$ 頭の数の和を計算。
- 全員の計算終了後、自分の数を計算した和に置き換えます。巨大な数を避け $98,765,431$ での剰余を保存します。
十一月にヘラジカ Canmuu に伝えると、とても感心しました。
霧のクリスマスイブに Canmuu が来て言いました：
「簡単に破れる！ $T$ 回 $(1 \le T \le 1,414,213,562)$ 繰り返すべきだ。」
退屈な同じ計算を大量に繰り返すのに牛は落胆。数時間の議論後、Canmuu と牛は妥協しました。あなたが暗号化後の数を計算します！
*この問題の最初の 10 提出には追加のフィードバックがあります。
入力
標準入力から読みます。
- 1 行目：空白区切り二整数 $N$、$T$。
- $2..N+1$ 行目：$i+1$ 行目は一整数 $C_i$。
出力
標準出力に書きます。
- $1..N$ 行目：$i$ 行目は暗号化終了時の牛 $i$ の数、$98,765,431$ を法とする一整数。
入出力例
入力 1
3 4 1 0 4
出力 1
26 25 29
注記
初期値 $1$、$0$、$4$ の三頭、四回繰り返します。
各回の牛の数の表です：
| 回 | 牛 $1$ | 牛 $2$ | 牛 $3$ |
|---|---|---|---|
| $0$ | $1$ | $0$ | $4$ |
| $1$ | $4$ | $5$ | $1$ |
| $2$ | $6$ | $5$ | $9$ |
| $3$ | $14$ | $15$ | $11$ |
| $4$ | $26$ | $25$ | $29$ |
問題の謝辞：Neal Wu、2007