CF1776K Uniform Chemistry

In a parallel universe there are $ n $ chemical elements, numbered from $ 1 $ to $ n $ . The element number $ n $ has not been discovered so far, and its discovery would be a pinnacle of research and would bring the person who does it eternal fame and the so-called SWERC prize. There are $ m $ independent researchers, numbered from $ 1 $ to $ m $ , that are trying to discover it. Currently, the $ i $ -th researcher has a sample of the element $ s_i $ . Every year, each researcher independently does one fusion experiment. In a fusion experiment, if the researcher currently has a sample of element $ a $ , they produce a sample of an element $ b $ that is chosen uniformly at random between $ a+1 $ and $ n $ , and they lose the sample of element $ a $ . The elements discovered by different researchers or in different years are completely independent. The first researcher to discover element $ n $ will get the SWERC prize. If several researchers discover the element in the same year, they all get the prize. For each $ i = 1, \, 2, \, \dots, \, m $ , you need to compute the probability that the $ i $ -th researcher wins the prize.

The first line contains two integers $ n $ and $ m $ ( $ 2 \le n \le 10^{18} $ , $ 1 \le m \le 100 $ ) — the number of elements and the number of researchers. The second line contains $ m $ integers $ s_1, \, s_2, \, \dots, \, s_m $ ( $ 1 \le s_i < n $ ) — the elements that the researchers currently have.

Print $ m $ floating-point numbers. The $ i $ -th number should be the probability that the $ i $ -th researcher wins the SWERC prize. Your answer is accepted if each number differs from the correct number by at most $ 10^{-8} $ .

In the first sample, all researchers will discover element $ 2 $ in the first year and win the SWERC prize. In the second sample, the last researcher will definitely discover element $ 3 $ in the first year and win the SWERC prize. The first two researchers have a $ 50\% $ chance of discovering element $ 2 $ and a $ 50\% $ chance of discovering element $ 3 $ , and only element $ 3 $ will bring them the prize. In the third sample, each researcher has an independent $ 50\% $ chance of discovering element $ 3 $ in the first year, in which case they definitely win the SWERC prize. Additionally, if they all discover element $ 2 $ in the first year, which is a $ 12.5\% $ chance, then they will all discover element $ 3 $ in the second year and all win the prize.