n муравьёв находятся на круге длины m. Каждый муравей может двигаться со скоростью в одну единицу длины в единицу времени. Изначально i-й муравей находится в позиции si и смотрит в направлении di (L или R). Позиции пронумерованы в порядке против часовой стрелки, начиная с некоторой точки. Изначальные положения всех муравьёв различны.
Муравьи двигаются одновременно. Два муравья при столкновении меняют напраление своего движения на противоположное. Обратите внимание, что возможна ситуация, когда половину единицы времени муравей движется в одном направлении, затем сталкивается с другим муравьём и двигается в противоположном направлении в течении оставшейся половины единицы времени.
Определите положения всех муравьёв спустя t единиц времени.
Выходные данные
Выведите n целых чисел xj — положение j-го муравья по прошествии t единиц времени. Муравьи пронумерованы от 1 до n в порядке их появления во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 4 8
1 R
3 L
|
1 3
|
|
2
|
4 8 6
6 R
5 L
1 R
8 L
|
7 4 2 7
|
|
3
|
4 8 2
1 R
5 L
6 L
8 R
|
3 3 4 2
|