题目描述

如果我们相信《吉尼斯世界纪录大全》的话，在布满森林的 Endor 卫星上，有一根全银河系最长的棍子。在那根 $L$ 米长的棍子上有 $n$ 只欢快的变色龙。每只变色龙以 $1$ 米/秒的恒定速度沿着棍子在两个可能的方向（左或右）中的一个方向上移动，并以可能的 $k$ 种颜色之一着色。

众所周知，Endor 卫星上的变色龙崇拜古老的蚂蚁法则，该法则规定变色龙必须沿着棍子行走直到走到棍子的末端，并且当与另一只变色龙发生碰撞时，该变色龙必须转过 $180$ 度，继续朝相反的方向行走。此外，在向左移动着色为 $a$ 的变色龙与向右移动的着色为 $b$ 的变色龙发生碰撞后，碰撞前向左移动的变色龙采用碰撞前向右移动的变色龙的颜色 $b$，而在碰撞前向右移动的变色龙会采用新的颜色 $(a+b)\bmod k$。

如果给你所有变色龙的初始位置、颜色和运动方向，对于每种颜色，确定采用该种颜色的变色龙在离开棍子之前的总行程。

输入格式

第一行输入三个整数 $n,k,L$，分别表示变色龙的只数，颜色的种数和棍子的长度。
随后 $n$ 行，每行两个整数 $d_i,b_i$ 和一个字符 L 或 D，其中 $d_i,b_i$ 分别表示第 $i$ 只变色龙到棍子左端的距离和第 $i$ 只变色龙的颜色，字符如果是 L，则表示第 $i$ 只变色龙初始时面朝左边，否则表示第 $i$ 只变色龙初始时面朝右边。保证 $d_i$ 两两不同且按升序给出。

输出格式

输出 $k$ 行，第 $i$ 行输出一个实数，表示采用第 $i-1$ 种颜色的变色龙离开棍子之前的总行程，保留一位小数。可以证明，答案要么是整数，要么是形如 $\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

提示

【样例 1 解释】

两只变色龙在行走了 $5$ 米之后发生碰撞。在此之后，$1$ 号变色龙的颜色变为 $0$，$2$ 号变色龙的颜色变为 $1$，然后它们各又继续走了 $5$ 米然后离开棍子。因此，采用第 $0$ 种颜色和第 $1$ 种颜色的变色龙各走了 $10$ 米，在此过程中不存在采用第 $2$ 种颜色的变色龙。

【数据范围】

对于 $50\%$ 的数据，保证 $1\leqslant n\leqslant 3000$。
对于所有数据，$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$。

【题目来源】

本题来源自 COCI 2015-2016 CONTEST 4 T6 ENDOR，按照原题数据配置，满分 $160$ 分。

由 Eason_AC 翻译整理提供。