On the forest-filled moon of Endor there is, if we are to believe the Guinness Book of Records, the longest stick in the whole galaxy. On that stick of ~L~ meters in length there are ~N~ cheerful chameleons. Each chameleon is moving along the stick with constant speed of 1 m/s in one of two possible directions (left or right) and is colored in one of the possible ~K~ colors.

It is known that the chameleons of Endor worship the ancient ant laws that dictate that the walk along the stick must be continued until the end of the stick is reached (which means getting off it), and when a collision with another chameleon takes place, you must turn 180 degrees and continue the walk in the opposite direction. Additionally, after a chameleon colored in ~a~ moving to the left collides with a chameleon colored in ~b~ moving to the right, the chameleon moving to the left before the collision takes the color of the chameleon moving to the right before the collision (so, color ~b~), while the chameleon moving to the right before the collision takes a new color ~(a+b) \bmod K~.

If you are given the initial positions, colors and directions of movement of all the chameleons, for each color determine the total trip taken by the chameleons in that color before getting off the stick.

Input

The first line of input contains the integers ~N~, ~K~ and ~L~ ~(1 \le N \le 100\,000, 1 \le K \le 40, 1 \le L \le 1\,000\,000)~ from the task. The ~i^{th}~ of the following ~N~ lines contains the integer ~d_i~ ~(0 \le d_i \le L)~ that denotes the distance between the ~i^{th}~ chameleon and the left end of the stick, then the integer ~b_i~ ~(0 \le b_i \le K-1)~ that denotes the color of the ~i^{th}~ chameleon and the character L (left) or D (right) that denote the direction of movement of the ~i^{th}~ chameleon. All integers ~d_i~ will be unique and given in strictly ascending order.

Output

The output must contain ~K~ lines, the ~i^{th}~ line containing the total trip taken by the chameleons in color ~i~.

Scoring

In test cases worth 50% of total points, it will additionally hold ~(1 \le N \le 3\,000)~.

Sample Input 1

2 3 10
0 0 D
10 1 L

Sample Output 1

10.0
10.0
0.0

Explanation for Sample Output 1

The chameleons collide after 5 travelled meters in the middle of the stick. After that, both chameleons change their direction of movement. The chameleon moving to the right after collision is colored in 0, whereas the chameleon moving to the left after collision is colored in 1.

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