DreamGrid 饲养了 $n$ 只兔子。最初，第 $i$ 只（$1 \le i \le n$）兔子的体重为 $w_i$。

每天早上，DreamGrid 会给兔子们一个重量为 1 的胡萝卜，兔子们会为这唯一的胡萝卜进行争抢。只有一只兔子会赢得争抢并吃掉胡萝卜。吃掉胡萝卜后，获胜兔子的体重增加 1。整个争抢和进食的过程在第二天早上之前结束。

DreamGrid 发现，兔子越重，就越容易赢得争抢。形式化地，如果争抢前兔子们的体重分别为 $w_1, w_2, \dots, w_n$，那么第 $i$ 只兔子赢得争抢的概率为：

$$\frac{w_i}{\sum_{j=1}^{n} w_j}$$

他想知道 $k$ 天（即 $k$ 个胡萝卜被分发并吃掉）后，每只兔子的期望体重。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$（$1 \le T \le 10^5$），表示测试数据的组数。

对于每组测试数据，第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^5, 1 \le k \le 10^9$）。第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$（$1 \le i \le n, 1 \le w_i \le 10^9$）。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含 $n$ 个用空格分隔的实数，其中第 $i$ 个数表示第 $i$ 只兔子在 $k$ 天后的期望体重。

如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-4}$，则视为正确。

样例

样例输入 1

3
1 1
2
2 2
1 3
3 2
1 1 1

样例输出 1

3.00000000
1.50000000 4.50000000
1.66666667 1.66666667 1.66666667