DreamGrid is the keeper of $n$ rabbits. Initially, the $i$-th ($1 <= i <= n$) rabbit has a weight of $w_i$.
Every morning, DreamGrid gives the rabbits a carrot of weight $1$ and the rabbits fight for the only carrot. Only one rabbit wins the fight and eats the carrot. After that, the winner's weight increases by $1$. The whole process of fighting and eating ends before the next morning.
DreamGrid finds that the heavier a rabbit is, the easier it is to win a fight. Formally, if the weights of the rabbits are $w_1 ', w_2 ', \\dots, w_n '$ before a fight, the probability that the $i$-th rabbit wins the fight is $$\frac{w_i'}{\sum\limits_{j=1}^{n}{w_j'}}$$ He wants to know the expected weight of every rabbit after $k$ days ($k$ carrots are given and eaten).
The input contains multiple cases. The first line of the input contains a single integer $T " "(1 <= T <= 10^5)$, the number of cases.
For each case, the first line of the input contains two integers $n$ and $k$ ($1 <= n <= 10^5, 1 <= k <= 10^9$). The second line contains $n$ integers $w_1, w_2, \\dots, w_n$ ($1 <= i <= n, 1 <= w_i <= 10^9$).
It's guaranteed that the sum of $n$ over all cases doesn't exceed $10^6$.
For each case, print a single line containing $n$ space-separated real numbers, where the $i$-th ($1 <= i <= n$) number should be equal to the expected weight of the $i$-th rabbit after $k$ days.
Your answer will be considered correct if the absolute or relative error does not exceed $10^(-4)$.
## Input
The input contains multiple cases. The first line of the input contains a single integer $T " "(1 <= T <= 10^5)$, the number of cases.For each case, the first line of the input contains two integers $n$ and $k$ ($1 <= n <= 10^5, 1 <= k <= 10^9$). The second line contains $n$ integers $w_1, w_2, \\dots, w_n$ ($1 <= i <= n, 1 <= w_i <= 10^9$).It's guaranteed that the sum of $n$ over all cases doesn't exceed $10^6$.
## Output
For each case, print a single line containing $n$ space-separated real numbers, where the $i$-th ($1 <= i <= n$) number should be equal to the expected weight of the $i$-th rabbit after $k$ days.Your answer will be considered correct if the absolute or relative error does not exceed $10^(-4)$.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n \in \mathbb{Z} $ be the number of rabbits.
- Let $ k \in \mathbb{Z} $ be the number of days (carrots given).
- Let $ \mathbf{w} = (w_1, w_2, \dots, w_n) \in \mathbb{R}_{>0}^n $ be the initial weights of the rabbits.
Let $ \mathbf{W}^{(d)} = (W_1^{(d)}, W_2^{(d)}, \dots, W_n^{(d)}) \in \mathbb{R}_{>0}^n $ denote the random vector of weights after $ d $ days, with $ \mathbf{W}^{(0)} = \mathbf{w} $.
**Constraints**
1. $ 1 \le T \le 10^5 $
2. For each test case:
- $ 1 \le n \le 10^5 $, $ 1 \le k \le 10^9 $
- $ 1 \le w_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $
3. $ \sum_{\text{all cases}} n \le 10^6 $
**Transition Rule**
At day $ d+1 $, given current weights $ \mathbf{W}^{(d)} $, the probability that rabbit $ i $ wins the fight is:
$$
\mathbb{P}(\text{rabbit } i \text{ wins} \mid \mathbf{W}^{(d)}) = \frac{W_i^{(d)}}{\sum_{j=1}^n W_j^{(d)}}
$$
If rabbit $ i $ wins, then:
$$
W_i^{(d+1)} = W_i^{(d)} + 1, \quad W_j^{(d+1)} = W_j^{(d)} \text{ for } j \ne i
$$
**Objective**
Compute the expected weight vector after $ k $ days:
$$
\mathbb{E}[\mathbf{W}^{(k)}] = \left( \mathbb{E}[W_1^{(k)}], \mathbb{E}[W_2^{(k)}], \dots, \mathbb{E}[W_n^{(k)}] \right)
$$