$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