题目描述

给定一个彩票转盘，它有 n 个扇区，按顺时针或逆时针的某个方向依次编号为 1..n（具体是顺时针还是逆时针并不重要）。转盘上有一根指针；当转盘不转动时，指针总是恰好指向其中一个扇区。初始时，指针指向扇区 1。

这个转盘可以被反复旋转，且旋转方向与扇区编号方向一致。对于一次旋转，给定 p0, p1, ..., p(n-1)，其中 pi 表示：旋转结束后，指针将指向相对于起始所指扇区向前第 i 个扇区的概率。

请编写程序 lotary，计算在连续进行 k 次旋转之后，指针指向每一个扇区的概率。

输入格式

第一行两个整数 n 和 k，表示扇区数量和连续旋转次数。
第二行 n 个实数 p0, p1, ..., p(n-1)，表示上面定义的概率。

输出格式

输出一行 n 个实数 q1, q2, ..., qn，以空格分隔，其中 qi 表示经过 k 次连续旋转后，指针指向编号为 i 的扇区的概率。

若你输出的每个数与标准答案的误差都不超过 10^-6，则认为答案正确。

数据范围

• 1 ≤ n ≤ 15000
• 1 ≤ k ≤ 1000000000

子任务与评分

• 子任务 1（10 分）：n ≤ 1000, k ≤ 100
• 子任务 2（20 分）：n ≤ 100
• 子任务 3（30 分）：n ≤ 2000
• 子任务 4（40 分）：无额外限制

只有通过某个子任务中的全部测试点，才能获得该子任务的分数。

样例输入

3 2
0.1 0.4 0.5

样例输出

0.41 0.33 0.26

样例解释

指针最终停在第 1 个扇区的概率为：

• 两次都转动 0 个扇区：0.1 × 0.1
• 第一次转动 1 个扇区、第二次转动 2 个扇区：0.4 × 0.5
• 第一次转动 2 个扇区、第二次转动 1 个扇区：0.5 × 0.4

所以该概率为：

0.1 × 0.1 + 0.4 × 0.5 + 0.5 × 0.4 = 0.41