Problem Description

Takahashi and his friends are planning to stay in $ K $ rooms during a camp with $ N $ participants.

They prepared a lottery with numbers from $ 1 $ to $ N $ and decided to assign rooms in order from the smallest number.

There are two types of people in Takahashi's group: those who like quiet rooms and those who like lively rooms.

People who like quiet rooms prefer rooms with the least number of people so far. They will stay in the room with the smallest number of occupants.

People who like lively rooms prefer rooms with the most number of people so far. They will stay in the room with the largest number of occupants.

If there are multiple rooms satisfying the condition for either type, they will choose one of those rooms with equal probability.

Takahashi wants to predict how many people each participant will share a room with before actually assigning the rooms.

For each participant, calculate the expected number of people sharing the same room, including themselves.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ S $

• The first line contains the number of participants $N\ (1\ ≦\ N\ ≦\ 200,000)$ and the number of rooms $K\ (1\ ≦\ K\ ≦\ 200,000)$, separated by a space.
• The second line contains a string $ S $ of length $ N $ that represents the type of each participant.
• $ S $ consists only of characters 0 and 1. If $ S_i $ is 0, the $ i $th participant likes quiet rooms. If $ S_i $ is 1, the $ i $th participant likes lively rooms.

Output Format

For each participant, output the expected number of people sharing the same room in $ N $ lines.

The $ i $th line should contain the expected number of people sharing the same room with the participant drawn $ i $th.

The error is allowed up to a relative or absolute error of $ 10^{-6} $.

Sample Input and Output

Sample Input #1

7 3
1000011

Sample Output #1

2.33333333333333
2.33333333333333
2.33333333333333
3
3
4
4

Sample Input #2

12 5
000000101101

Sample Output #2

2.4
2.4
2.4
2.4
2.4
6
6
2
6
6
2
6

Notes/Hints

Sample Explanation 1

The first three people will stay in rooms with 1, 2, or 4 people with equal probability, so the expected value is $ 7/3 $. The fourth and fifth people will stay in rooms with 2 or 4 people with equal probability, so the expected value is $ 3 $. The sixth and seventh people will stay in a room with 4 people, so the expected value is $ 4 $.

见题面 Input 部分

见题面 Output 部分