F. Муравьи на круге
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

n муравьёв находятся на круге длины m. Каждый муравей может двигаться со скоростью в одну единицу длины в единицу времени. Изначально i-й муравей находится в позиции si и смотрит в направлении di (L или R). Позиции пронумерованы в порядке против часовой стрелки, начиная с некоторой точки. Изначальные положения всех муравьёв различны.

Муравьи двигаются одновременно. Два муравья при столкновении меняют напраление своего движения на противоположное. Обратите внимание, что возможна ситуация, когда половину единицы времени муравей движется в одном направлении, затем сталкивается с другим муравьём и двигается в противоположном направлении в течении оставшейся половины единицы времени.

Определите положения всех муравьёв спустя t единиц времени.

Входные данные

В первой строке находятся три целых числа n, m и t (2 ≤ n ≤ 3·105, 2 ≤ m ≤ 109, 0 ≤ t ≤ 1018) — количество муравьёв, длина круга и количество единиц времени.

В каждой из следующих n строк находится целое целое число si и символ di (1 ≤ si ≤ m, di равно L либо R) — положение и направление движения i-го муравья в начале. Направления L и R соответствуют направлениям по и против часов стрелки, соответственно.

Гарантируется, что все позиции si различны.

Выходные данные

Выведите n целых чисел xj — положение j-го муравья по прошествии t единиц времени. Муравьи пронумерованы от 1 до n в порядке их появления во входных данных.

Примеры
Входные данные
2 4 8
1 R
3 L
Выходные данные
1 3
Входные данные
4 8 6
6 R
5 L
1 R
8 L
Выходные данные
7 4 2 7
Входные данные
4 8 2
1 R
5 L
6 L
8 R
Выходные данные
3 3 4 2