Chameleon Journey on the Galactic Stick

On the forest‐covered moon Endor, according to the Guinness World Records, there is the longest stick in the galaxy of length \(L\) meters. On this stick, there are \(n\) joyful chameleons. Each chameleon has one of \(k\) possible colors, and it moves at a constant speed of 1 meter per second in one of two directions (left or right).

According to the ancient "Ant Rule" revered on Endor, a chameleon must continue to walk along the stick until it reaches an end. In addition, when two chameleons collide, both instantly turn 180 degrees and continue along the stick. However, there is a twist: When a left‐moving chameleon with color \(a\) collides with a right–moving chameleon with color \(b\), then immediately after the collision the chameleon that was moving left adopts the color \(b\), while the chameleon that was moving right adopts a new color given by \((a+b) \bmod k\).

Given the initial positions, colors, and directions of all \(n\) chameleons on a stick of length \(L\), compute for each color the total distance that chameleons travel while they have that color (i.e. summing over all segments of their journey before leaving the stick). Note that a chameleon may change its color during its walk because of collisions, and the distance traveled with a particular color is the length of time (since speed is 1 m/s) the chameleon maintained that color.

Note: When a chameleon reaches an endpoint (0 or \(L\)) it immediately leaves the stick and does not participate in further collisions. In case a collision and an exit occur at the same time, the exit is processed first.

inputFormat

The first line contains three numbers: \(L\) \(n\) \(k\) where \(L\) (a positive integer) is the length of the stick, \(n\) is the number of chameleons, and \(k\) is the number of colors (colors are integers in the range 0 to \(k-1\)).

Then \(n\) lines follow. Each of these \(n\) lines contains the initial information of a chameleon in the format:

position color direction

Here, position is a real number (with up to 6 decimals) representing the chameleon’s initial position on the stick \([0, L]\), color is an integer in \([0, k-1]\), and direction is either the character 'L' (for left) or 'R' (for right).

outputFormat

Output a single line containing \(k\) numbers. The \(i\)th number (0-indexed) denotes the total distance traveled by chameleons while having color \(i\) before they leave the stick. Separate the numbers by a single space. The answers may be decimal values.

sample

10 2 5
2 1 R
8 2 L

0 8 3 5 0