Problem Description

E869120, who wants to make new friends in his new class, came up with the following card game:

• There are $ N $ cards numbered $ 1, 2, 3, ..., N $.
• The cards are painted in one of $ D $ colors, represented by numbers $ 0, 1, 2, ..., D-1 $.
• Card $ i $ is painted in color $S_i\ (0 \leq S_i < D)$ and has the number $ i $ written on it.

Using these cards, $ D $ players will play a card game. The rules are as follows:

1. First, stack the cards numbered $ 1, 2, 3, ..., k $ into a pile. The card numbered $ i $ should be the $ i $th card from the top.
2. Repeat the following operation $ L $ times.
3. Choose a random integer $ i $ between $ 1 $ and $ k $ (inclusive), and swap the $ i $th card from the top with the $ (i+1)th $ card from the top.
4. Finally, distribute the cards from the top of the pile to the players in the order $ 1, 2, 3, ..., D, 1, 2, 3, ..., D, 1, 2, ... $.
5. The score of player $ i $ is the sum of the numbers written on the cards painted in color $ (i-1) $ that the player has.

Note that in step 3, the "top $ (k+1)th $ card" refers to the "top 1st card".

The game is played over $N \div D$ rounds. In the $ i $th round, the game is played with $k = i \times D$.
For each round, calculate the expected score for each player.

Please read the "Output Format" section carefully due to the unusual output format.

Input Format

The input is given from the standard input in the following format.
Note that $ S_1, S_2, ..., S_N $ are given as a concatenated string of digits.

$ N $ $ D $ $ L $ $S_{1}S_{2}S_{3}S_{4}\ ...\ S_{N}$

Output Format

Output $ D $ lines.
The $ i $th line should contain the total expected score of player $ i $ over the $N \div D$ games.
The answer will be considered correct if the absolute or relative error is less than $ 10^{-5} $.

Sample Input and Output

Sample Input #1

3 3 1
012

Sample Output #1

0.333333333333
0.666666666667
1.000000000000

Sample Input #2

8 4 1
01123310

Sample Output #2

2.250000000000
4.500000000000
1.500000000000
0.625000000000

Sample Input #3

20 4 15
10232310010022312313

Sample Output #3

34.068777543023
27.854472795592
22.354635768263
28.066210471955

Notes/Hints

Constraints

• $ D $ is an integer between $ 3 $ and $ 10 $ (inclusive).
• $ N $ is a multiple of $ D $ and is between $ 3 $ and $ 3,000,000 $ (inclusive).
• $ L $ is an integer between $ 1 $ and $ 1,000,000,000 $ (inclusive).
• $S_i\ (1 \leq i \leq N)$ is one of $ 0, 1, 2, ..., D-1 $.

Partial Points

This problem is divided into several sub-tasks. Your score will be the sum of the points for the sub-tasks you solve correctly.

1. (50 points): $N \leq 10, D \leq 4, L = 1$
2. (70 points): $N \leq 10, D \leq 4, L \leq 5$
3. (80 points): $N \leq 50, D \leq 4, L \leq 300$
4. (100 points): $N \leq 3,000, D \leq 4, L \leq 300$
5. (210 points): $N \leq 3,000, D \leq 4$
6. (130 points): $N \leq 50,000, D \leq 4$
7. (40 points): $N \leq 150,000, D \leq 6$
8. (40 points): $N \leq 300,000, D \leq 8$
9. (40 points): $N \leq 500,000, D \leq 10$
10. (40 points): $N \leq 800,000, D \leq 10$
11. (200 points): $N \leq 3,000,000, D \leq 10$

Sample Explanation 1

Starting with the card arrangement $ (1, 2, 3) $ and performing the operation in the problem statement $ L=1 $ time, the possible arrangements are $ (1, 3, 2), (2, 1, 3), (3, 2, 1) $ each with equal probability of $ 1/3 $. The scores for each player are as follows:
- $ (1, 3, 2) $: Scores are $ 1, 0, 0 $
- $ (2, 1, 3) $: Scores are $ 0, 0, 3 $
- $ (3, 2, 1) $: Scores are $ 0, 2, 0 $
Thus, the expected scores for each player are $ 1/3, 2/3, 1 $.

Sample Explanation 2

In the first round, the following $ 4 $ arrangements occur with equal probability:
- $ (1, 2, 4, 3) $: Scores are $ 1, 2, 4, 0 $
- $ (1, 3, 2, 4) $: Scores are $ 1, 3, 0, 0 $
- $ (2, 1, 3, 4) $: Scores are $ 0, 0, 0, 0 $
- $ (4, 2, 3, 1) $: Scores are $ 0, 2, 0, 0 $
Therefore, the expected scores for each player in the first round are $ 1/2, 7/4, 1, 0 $. In the second round, the following $ 8 $ arrangements occur with equal probability:
- $ (1, 2, 3, 4, 5, 6, 8, 7) $: Scores are $ 1, 2, 0, 0 $
- $ (1, 2, 3, 4, 5, 7, 6, 8) $: Scores are $ 1, 9, 0, 0 $
- $ (1, 2, 3, 4, 6, 5, 7, 8) $: Scores are $ 1, 2, 0, 0 $
- $ (1, 2, 3, 5, 4, 6, 7, 8) $: Scores are $ 1, 2, 0, 5 $
- $ (1, 2, 4, 3, 5, 6, 7, 8) $: Scores are $ 1, 2, 4, 0 $
- $ (1, 3, 2, 4, 5, 6, 7, 8) $: Scores are $ 1, 3, 0, 0 $
- $ (2, 1, 3, 4, 5, 6, 7, 8) $: Scores are $ 0, 0, 0, 0 $
- $ (8, 2, 3, 4, 5, 6, 7, 1) $: Scores are $ 8, 2, 0, 0 $
Therefore, the expected scores for each player in the second round are $ 7/4, 11/4, 1/2, 5/8 $.

见题面 Input 部分

见题面 Output 部分