题目描述

$N$ 头奶牛（$1 \leq N \leq 5 \times 10^4$）刚刚学习了不少密码学知识，终于，她们创造出了属于奶牛的加密方法，由于她们经验不足，她们的加密方法很简单：

第 $i$ 头奶牛掌握着密码的第 $i$ 个数字，起始的时候是 $C_i$（$0 \leq C_i \lt 9 \times 10^7$）。加密的时候，第 $i$ 头奶牛会计算其他所有奶牛的数字和，并将这个和对 $98\,765\,431$ 取模。在所有奶牛计算完成后，每头奶牛都会用自己算的数字代替原来的数字。即，

这样，她们完成了一次加密。

在十一月，奶牛们把这个加密方法告诉了驼鹿卡门。卡门想了一会后，说：“你们的算法还很原始，为了达到加密效果，你们要重复这个加密过程 $T$ 次（$1 \leq T \leq 1\,414\,213\,562$）”。

奶牛们很懒，于是就把这个任务交给了你。

输入格式

第一行两个整数 $N,T$。

接下来 $N$ 行，第 $i$ 行一个整数 $C_i$。

输出格式

输出 $N$ 行，第 $i$ 行一个整数，代表经过 $T$ 次加密后的 $C_i$。

3 4
1
0
4

26
25
29

提示

每次加密后的 $C_i$ 如下：