Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

math

*3200

No tag edit access

The problem statement has recently been changed. View the changes.

×
K. Uniform Chemistry

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn 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.

Input

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.

Output

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}$$$.

Examples

Input

2 3 1 1 1

Output

1.0 1.0 1.0

Input

3 3 1 1 2

Output

0.5 0.5 1.0

Input

3 3 1 1 1

Output

0.625 0.625 0.625

Input

100 7 1 2 4 8 16 32 64

Output

0.178593469 0.179810455 0.182306771 0.187565366 0.199300430 0.229356322 0.348722518

Note

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/23/2024 07:35:16 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|