M. Rejection Sampling
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Bobo wants to use a rejection sampling algorithm to construct a random set $$$T\subset \{1,2,\dots,n\}$$$ of size $$$k$$$. For parameters $$$p_1,p_2,...,p_n$$$ $$$(0\leq p_i\leq 1)$$$ and integer $$$k$$$, the rejection sampler is defined as follows:

  1. Initialize $$$T \gets \emptyset$$$;
  2. For each $$$i$$$ $$$(1\leq i\leq n)$$$, add $$$i$$$ into $$$T$$$ with probability $$$p_i$$$;
  3. Output $$$T$$$ if the size of $$$T$$$ is exactly $$$k$$$; otherwise, repeat the process.

Now you are given integers $$$a_1,a_2,...,a_n$$$ and $$$k$$$. Bobo needs to set the parameters $$$p_1,p_2,\ldots,p_n$$$ satisfying

  • $$$\sum_{i=1}^n p_i=k$$$;
  • for all $$$S\subseteq \{1,2,\cdots, n\}$$$ such that $$$|S|=k$$$, the probability that the rejection sampler outputs $$$S$$$ is proportional to $$$\prod_{i \in S} a_i$$$.

Your task is to find out the parameters $$$p_1,p_2,\dots,p_n$$$ for Bobo. It is guaranteed that such parameters exist and are unique. Your answer will be considered correct if the absolute error of each $$$p_i$$$ doesn't exceed $$$10^{-6}$$$ compared to the unique answer.

Input

The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le n-1$$$).

The second line of the input contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Output

Output $$$n$$$ lines. The $$$i$$$-th line contains a single real number $$$p_i$$$.

Your answer is considered correct if the absolute error of each parameter does not exceed $$$10^{-6}$$$. Namely, if your answer is $$$a$$$, and the jury's answer is $$$b$$$, then your answer is accepted if $$$|b-a| \le 10^{-6}$$$ for all parameters.

Examples
Input
3 2
5 5 5
Output
0.666666666667
0.666666666667
0.666666666667
Input
2 1
1 4
Output
0.333333333333
0.666666666667
Input
4 2
1 2 3 4
Output
0.310035697652
0.473324044845
0.574114878920
0.642525378583