题目描述

wygz 有 $\sum a_i$ 个 Dimoo。

为了拍出满意的照片，她把它们摆放在一个环上，第 $i$ 个位置上放 $a_i$ 个。位置按照顺时针的顺序从 $1$ 到 $n$ 编号。

接下来的每一秒，wygz 会对所有同时进行操作：

• 若 $i$ 上有至少一个 Dimoo，则拿起一个，放到下一个位置（也就是 $(i+1) \bmod n$）。

现在，wygz 想知道，经过 $k$ 秒以后，每个位置上会有多少个 Dimoo？

输入格式

第一行，两个整数，$n$ 和 $k$。

第二行，$n$ 个非负整数，表示 $a_i$。

输出格式

输出 $\sum_{i=1}^n M^i(a_i+1) \bmod 2^{64}$ 的结果，其中 $M=12345678901$，$a_i$ 为最终的答案序列。

样例

5 3
1 0 0 1 0

979919941747309627

最后的答案是 0 1 0 1 0。

5 3
0 1 2 0 0

16075001298286537116

最后的答案是 1 0 0 1 1。

6 4
0 1 5 5 0 5

15866784849838457306

最后的答案是 1 1 4 5 1 4。

数据范围

由于 [数据删除]的出题人偷偷加 0 输入量比较大，我们下发了 std 所使用的快速输入（即 io.cpp）供大家参考。时空限制均为 std 所耗的两倍以上。

对于全部数据，$1\le n\le 10^7$，$0\le k,a_i\le 10^9$。