Group Pressure#4023

Group Pressure

3 seconds

64 megabytes

Easy

Ever since the middle of the 20th century, sociologists have been studying the fascinating topic of group decision-making behaviour among students in Delft. One of the great successes has been the development of a highly accurate model that describes the intricate ritual of venue selection, which can be observed in the afternoon after the courses for the day are done.

Students select a venue by casting votes. What makes this interesting from a sociological perspective is the mix of dominant behaviour by some students, and behaviour driven by peer influence combined with randomness by other students.

Specifically, the model used to describe the venue selection ritual is as follows:

The dominant students, who have a strong preference for a particular venue (such as a café, park, or library), will announce their votes. Several dominant students may vote for the same venue.
Next, the remaining students vote one by one. These non-dominant students vote probabilistically and are subject to peer influence: the probability that they vote for a specific venue is equal to the number of votes cast for that venue so far, divided by the total number of votes cast so far.
Finally, when all votes are in, the venue with the highest number of votes is selected. If several venues receive the same highest number of votes, one of those is selected at random, with equal probability.

For example, in one particular instance with seven students, five dominant students start by declaring their votes for three different venues. Three dominant students choose venue number one; the fourth dominant student votes for venue number two; and the last dominant student votes for venue number three. This leaves the initial vote count at $(3, 1, 1)$ (3, 1, 1).

After that, the remaining two non-dominant students start to vote, one after another. The first of them picks either venue number one with probability $3/5$ , venue number two with probability $1/5$ , or venue number three with probability $1/5$ . Suppose he picks venue number three, making the vote count $(3, 1, 2)$ (3, 1, 2).

Finally, the last student will pick either venue number one with probability $1/2$ , venue number two with probability $1/6$ , or venue number three with probability $1/3$ . Suppose she also picks venue number three.

This leaves the final vote count at $(3, 1, 3)$ (3, 1, 3): a tie between venue number one and venue number three. This tie is broken randomly; with probability $1/2$ , venue number one is selected for that afternoon's gathering.

Problem

You are a sociologist observing the ritual described above. After the dominant students are done declaring their votes, you want to determine the probabilities that each venue will be selected to host the students that day.

Input

For each test case, the input consists of two lines:

A line containing two positive integers: $n$ , denoting the number of possible venues in this trial ( $n \leq 5$ n \leq 5); and $k$ , the total number of students, both dominant and non-dominant ( $k \leq 50$ k \leq 50).
A line containing $n$ positive integers ( $α_{1}, α_{2}, \dots, α_{n}$ \alpha_1, \alpha_2, \ldots, \alpha_n), denoting the vote count right after all dominant students have cast their votes.

Furthermore, it is guaranteed that $α_{1} + α_{2} + \dots + α_{n} \leq k$ \alpha_1 + \alpha_2 + \cdots + \alpha_n \leq k.

Output

For each test case, write $n$ lines of output containing the probability that the $i$ -th venue ( $1 \leq i \leq n$ 1 \leq i \leq n) will be selected, in the order of increasing $i$ .

Each line shall be of the form venue i: percentage %, where percentage is a floating-point number rounded to $2$ digits after the decimal point.

There should be a space between the percentage number and the percent sign.

Examples

Example 1