Problem Description

If we believe the "Guinness World Records," there is a stick on the forest-covered moon of Endor that is the longest in the entire galaxy. On this stick, which is $L$ meters long, there are $n$ cheerful chameleons. Each chameleon moves at a constant speed of 1 meter per second in one of two possible directions (left or right) and is colored in one of $k$ possible colors.

It is well known that the chameleons on the moon of Endor follow the ancient ant rules, which dictate that a chameleon must walk along the stick until it reaches the end, and when it collides with another chameleon, it must turn $180$ degrees and continue walking in the opposite direction. Furthermore, after a collision between a left-moving chameleon colored $a$ and a right-moving chameleon colored $b$, the left-moving chameleon before the collision adopts the color $b$ of the right-moving chameleon, and the right-moving chameleon before the collision adopts a new color $(a+b)\bmod k$.

Given the initial positions, colors, and movement directions of all chameleons, for each color, determine the total distance traveled by chameleons of that color before they leave the stick.

Input Format

The first line of input contains three integers $n$, $k$, and $L$, representing the number of chameleons, the number of colors, and the length of the stick, respectively.
The following $n$ lines each contain two integers $d_i$ and $b_i$, and a character 'L' or 'D'. Here, $d_i$ and $b_i$ represent the distance of the $i$-th chameleon from the left end of the stick and its color, respectively. The character 'L' indicates that the $i$-th chameleon is initially facing left, otherwise it is facing right. It is guaranteed that $d_i$ are distinct and given in ascending order.

Output Format

Output $k$ lines, where the $i$-th line contains a real number representing the total distance traveled by chameleons of color $i-1$ before they leave the stick, rounded to one decimal place. It can be proven that the answer is either an integer or a number of the form $\texttt{x.5}$.

Sample Input and Output

Sample Input #1

2 3 10
0 0 D
10 1 L

Sample Output #1

10.0
10.0
0.0

Sample Input #2

4 3 7
1 0 D
3 0 D
4 1 L
6 2 D

Sample Output #2

10.0
4.0
1.0

Sample Input #3

4 4 5
1 1 D
3 3 L
4 2 D
5 0 L

Sample Output #3

2.5
4.0
2.5
4.0

Notes/Hints

[Sample 1 Explanation]

The two chameleons collide after walking $5$ meters. After the collision, the first chameleon's color changes to $0$, and the second chameleon's color changes to $1$. They then continue walking $5$ meters each and leave the stick. Therefore, chameleons of color $0$ and color $1$ each travel $10$ meters, and there are no chameleons of color $2$ during this process.

[Data Range]

For $50\%$ of the data, $1 \leqslant n \leqslant 3000$.
For all data, $1 \leqslant n \leqslant 10^5$, $1 \leqslant k \leqslant 40$, $1 \leqslant L \leqslant 10^6$, $0 \leqslant d_i \leqslant L$, $0 \leqslant b_i < k$, $d_{i-1} < d_i$.

[Problem Source]

This problem is from COCI 2015-2016 CONTEST 4 T6 ENDOR, configured according to the original problem data, with a full score of $160$ points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分