题目描述

不久前，在遥远的星穹中，李华发现了一根全银河系最长的轨道，于是 TA 将之取名为＂星穹铁道＂，谁也不知道那是哪儿来的，而后来在那根 $L$ 千米长的轨道上又出现了 $n$ 只可爱的变色龙！据李华所观察，每只变色龙能以 1 千米／秒的恒定速度沿着轨道在两个可能的方向（左或右）中的一个方向上移动，并且只可能以 $k$ 种颜色之一着色。

最近李华还发现了一个规律：每只变色龙都必须沿着轨道行走直到走到轨道的末端，并且当与另一只变色龙发生碰撞时，该变色龙必须转过 180 度，继续朝相反的方向行走。此外，在向左移动着色为 $a$ 的变色龙与向右移动的着色为 $b$ 的变色龙发生碰撞后，碰撞前向左移动的变色龙采用碰撞前向右移动的变色龙的颜色 $b$ ，而在碰撞前向右移动的变色龙会采用新的颜色 $(a+b) \bmod k$ 。

幸好李华还记得最开始变色龙们的位置、颜色与朝向，现在 TA 想求出对于每种颜色，采用该种颜色的变色龙在离开轨道之前的总行程，如果你是李华，相信你能够漂亮地写出一份代码来解决这个问题。

输入格式

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

输出格式

对输出 $k$ 行，第 $i$ 行输出一个实数，表示采用第 $i-1$ 种颜色的变色龙离开轨道之前的总行程，保留一位小数。可以证明，答案要么是整数，要么是形如 $x.5$ 的一位小数。

样例1输入

2 3 10
0 0 D
10 1 L

样例1输出

10.0
10.0
0.0

样例1解释

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

样例2输入

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

样例2输出

10.0
4.0
1.0

样例3输入

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

样例3输出

2.5
4.0
2.5
4.0

样例4

见下发数据

数据范围

对于所有数据， $1 \le n \le 10^5, 1 \le k \le 40,1 \le L \le 10^6, 0 \le d_i \le L, 0 \le b_i<k$ ，保证每只变色龙的位置各不相同

每个子任务的具体限制见下表：