Задача №113576. Хамелеоны Эндора
На лесистой луне Эндора находится, если верить Имперской Книге Рекордов, самая длинная ветка в галактике. На этой ветке длиной L метров сидит N дружелюбных хамелеонов. Каждый хамелеон ходит вдоль ветки со скоростью 1 м/с в одном из двух возможных направлений (налево или направо), а также имеет собственный цвет среди одного из K возможных.
Известно, что хамелеоны на Эндоры следуют древним законам, в соответствии с которыми любая прогулка вдоль ветки должна продолжаться до ее конца (после чего хамелеон спрыгивает с ветки), а в случае столкновения двух хамелеонов, они должны развернуться на 180 градусов и продолжить движение в противоположном направлении. Кроме того, при таком столкновении, если хамелеон, двигавшийся налево, имел цвет a , а хамелеон, двигавшийся направо - цвет b , то после разворота первый хамелеон изменит свой цвет на b , а второй хамелеон - на ( a + b ) modK .
Вам даны изначальные цвета, положения и направления движения всех хамелеонов. Определите для каждого цвета, какое расстояние пройдут хамелеоны, находящиеся в этом цвете, до того момента, пока не спрыгнут с ветки.
В первой строке содержится три целых числа числа N , K и L ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 40 , 1 ≤ L ≤ 1000000 ). В последующих N строках дана информация о хамелеонах. В i -й строке содержатся: целое число d i ( 1 ≤ d i ≤ L ) - изначальное положение, целое число b i ( 1 ≤ b i ≤ K - 1 ) - изначальный цвет, и символ "L" (налево) или "D" (направо) - изначальное направление движения. Гарантируется, что все числа d i различны и даны в возрастающем порядке.
Выведите K строк, i -я строка должна содержать одно число - расстояние, пройденное хамелеонами цвета i .
Решения, работающие при 1 ≤ Nle 3000 , будут оцениваться в 50 баллов.
2 3 10 0 0 D 10 1 L
10.0 10.0 0.0
4 3 7 1 0 D 3 0 D 4 1 L 6 2 D
10.0 4.0 1.0
4 4 5 1 1 D 3 3 L 4 2 D 5 0 L
2.5 4.0 2.5 4.0