CF698C.LRU

While creating high loaded systems one should pay a special attention to caching. This problem will be about one of the most popular caching algorithms called LRU (Least Recently Used).

Suppose the cache may store no more than k objects. At the beginning of the workflow the cache is empty. When some object is queried we check if it is present in the cache and move it here if it's not. If there are more than k objects in the cache after this, the least recently used one should be removed. In other words, we remove the object that has the smallest time of the last query.

Consider there are n videos being stored on the server, all of the same size. Cache can store no more than k videos and caching algorithm described above is applied. We know that any time a user enters the server he pick the video i with probability p__i. The choice of the video is independent to any events before.

The goal of this problem is to count for each of the videos the probability it will be present in the cache after 10100 queries.

在构建高负载系统时，应特别关注缓存机制。本题将围绕一种最流行的缓存算法——LRU（最近最少使用，Least Recently Used）展开。

假设缓存最多可存储 $k$ 个对象。工作流程开始时，缓存为空。当查询某个对象时，我们首先检查该对象是否已在缓存中；若不在，则将其加入缓存。若此次操作后缓存中对象数量超过 $k$ 个，则需移除其中最近最少使用的对象。换言之，我们移除最后一次被查询时间最早（即距当前时间最久）的那个对象。

现假设有 $n$ 个视频存储于服务器上，所有视频大小相同。缓存最多可存储 $k$ 个视频，并采用上述 LRU 缓存算法。已知：任意时刻用户访问服务器时，独立地以概率 $p_i$ 选择第 $i$ 个视频（$1 \le i \le n$），且各次选择相互独立。

本题目标是：对每个视频 $i$，计算其在经过 $10^{100}$ 次查询后仍存在于缓存中的概率。

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 20) — the number of videos and the size of the cache respectively. Next line contains n real numbers p__i (0 ≤ p__i ≤ 1), each of them is given with no more than two digits after decimal point.

It's guaranteed that the sum of all p__i is equal to 1.

输入的第一行包含两个整数 $n$ 和 $k$（$1 ≤ k ≤ n ≤ 20$），分别表示视频的数量和缓存的大小。下一行包含 $n$ 个实数 $p_i$（$0 ≤ p_i ≤ 1$），每个数最多保留两位小数。

保证所有 $p_i$ 的总和等于 $1$。

Print n real numbers, the i-th of them should be equal to the probability that the i-th video will be present in the cache after 10100 queries. You answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

输出 $n$ 个实数，其中第 $i$ 个数应等于第 $i$ 个视频在经过 $10^{100}$ 次查询后仍存在于缓存中的概率。若你的答案的绝对误差或相对误差均不超过 $10^{-6}$，则视为正确。

具体而言：假设你的答案为 $a$，而裁判组的标准答案为 $b$。当满足 时，校验程序将判定你的答案正确。