Problem Description

If we believe the Guinness World Records, on the forest-covered moon of Endor there is the longest stick in the entire galaxy. On this stick of length $L$ meters, there are $n$ cheerful chameleons. Each chameleon moves along the stick 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.

As everyone knows, the chameleons on Endor worship the ancient ant rule, which says that a chameleon must keep walking along the stick until it reaches an end of the stick, and when it collides with another chameleon, it must turn $180$ degrees and continue walking in the opposite direction. In addition, after a collision between a left-moving chameleon with color $a$ and a right-moving chameleon with color $b$, the chameleon that was moving left before the collision takes the color $b$ of the chameleon that was moving right before the collision, while the chameleon that was moving right before the collision takes the new color $(a+b)\bmod k$.

Given the initial position, color, and moving direction of every chameleon, for each color, determine the total distance traveled by chameleons of that color before they leave the stick.

Input Format

The first line contains three integers $n,k,L$, representing the number of chameleons, the number of colors, and the length of the stick.
Then follow $n$ lines. Each line contains two integers $d_i,b_i$ and a character L or D, where $d_i,b_i$ are the distance of the $i$-th chameleon from the left end of the stick and its color, respectively. If the character is L, it means the $i$-th chameleon initially faces left; otherwise, it initially faces right. It is guaranteed that all $d_i$ are distinct and are given in increasing order.

Output Format

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

2 3 10
0 0 D
10 1 L

10.0
10.0
0.0

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

10.0
4.0
1.0

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

2.5
4.0
2.5
4.0

Hint

[Sample 1 Explanation]

The two chameleons collide after walking $5$ meters. After that, chameleon $1$ changes its color to $0$, and chameleon $2$ changes its color to $1$. Then each of them continues walking another $5$ meters and leaves the stick. Therefore, chameleons of color $0$ and color $1$ each travel a total of $10$ meters, and there are no chameleons of color $2$ during this process.

[Constraints]

For $50\%$ of the testdata, $1\leqslant n\leqslant 3000$.
For all testdata, $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$.

[Source]

This problem is from COCI 2015-2016 CONTEST 4 T6 ENDOR, using the original testdata configuration, with a full score of $160$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5