如果我们相信吉尼斯世界纪录的话，在森林密布的恩多（Endor）卫星上，有着整个星系中最长的木棍。在这根长度为 $L$ 米的木棍上，有 $N$ 只快乐的变色龙。每只变色龙都以 $1\text{ m/s}$ 的恒定速度沿着木棍向两个可能方向之一（向左或向右）移动，并且它们被染成了 $K$ 种可能颜色中的一种。

众所周知，恩多的变色龙崇拜古老的蚂蚁法则，该法则规定：必须一直沿着木棍走，直到到达木棍的尽头（这意味着离开木棍）；当与其他变色龙发生碰撞时，必须转身 180 度并继续向相反方向走。此外，当一只颜色为 $a$ 且向左移动的变色龙与一只颜色为 $b$ 且向右移动的变色龙相撞后，碰撞前向左移动的变色龙会变成碰撞前向右移动的变色龙的颜色（即颜色 $b$），而碰撞前向右移动的变色龙会变成新颜色 $(a + b) \bmod K$。

给定所有变色龙的初始位置、颜色和移动方向，对于每种颜色，求出该颜色的变色龙在离开木棍前所走过的总路程。

输入格式

输入第一行包含三个整数 $N$，$K$ 和 $L$（$1 \le N \le 100\,000$，$1 \le K \le 40$，$1 \le L \le 1\,000\,000$）。

接下来的 $N$ 行中，第 $i$ 行包含一个整数 $d_i$（$0 \le d_i \le L$）表示第 $i$ 只变色龙与木棍左端的距离，然后是一个整数 $b_i$（$0 \le b_i \le K - 1$）表示第 $i$ 只变色龙的颜色，以及一个字符 'L'（向左）或 'D'（向右）表示第 $i$ 只变色龙的移动方向。所有整数 $d_i$ 互不相同，且按严格单调递增的顺序给出。

输出格式

输出应包含 $K$ 行，第 $i$ 行包含颜色为 $i$ 的变色龙走过的总路程。

数据范围

对于 $50\%$ 的测试数据，满足 $1 \le N \le 3\,000$。

样例

输入样例 1

2 3 10
0 0 D
10 1 L

输出样例 1

10.0
10.0
0.0

输入样例 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

说明

样例 1 解释：变色龙在木棍正中间（即各自移动了 5 米后）相撞。之后，两只变色龙都改变了移动方向。碰撞后向右移动的变色龙颜色变为 0，而碰撞后向左移动的变色龙颜色变为 1。