엔도르의 카멜레온

엔도르의 숲에는 은하계에서 가장 긴 막대가 있다. 길이가 $L$미터인 이 막대 위에 카멜레온 $N$마리가 있다. 카멜레온은 각각 초속 1미터로 왼쪽이나 오른쪽 중 한 방향으로 움직이고, $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$번째 줄에는 세 값이 주어진다. 막대 왼쪽 끝에서 $i$번째 카멜레온까지의 거리 $d_i$ ($0 \le d_i \le L$), $i$번째 카멜레온의 색 $b_i$ ($0 \le b_i \le K - 1$), 그리고 이동 방향을 나타내는 문자 하나이다. 문자는 왼쪽이면 L, 오른쪽이면 D이다.

$d_i$는 모두 다르고 증가하는 순서로 주어진다.

$K$개 줄을 출력한다. 첫째 줄부터 색 $0$, 색 $1$, 차례로 색 $K - 1$까지, 그 색인 채로 카멜레온이 걸은 거리의 합을 한 줄에 하나씩 출력한다.

합은 언제나 $0.5$의 배수이므로 소수점 아래 한 자리까지 출력한다. 합이 $4$면 4.0, $2.5$면 2.5로 출력한다.

길이가 $10$인 막대의 왼쪽 끝에서 색 $0$인 카멜레온이 오른쪽으로 출발하고, 오른쪽 끝에서 색 $1$인 카멜레온이 왼쪽으로 출발했다고 하자. 두 카멜레온은 각각 $5$미터를 걸은 뒤 막대 한가운데에서 부딪힌다. 부딪힌 뒤 오른쪽으로 방향을 바꾼 카멜레온의 색은 $0$이고, 왼쪽으로 방향을 바꾼 카멜레온의 색은 $1$이다.