mravi

문제

Ants of negligible dimensions move with constant speed of 1 mm/s along tight and long wire. 

When an ant encounters an obstacle (end of the wire or another ant), it immediately bounces and continues to move in the opposite direction with the same speed. 

Initial positions and directions (left or right) of ants are given. The ants are marked by numbers 1, 2, 3, ..., N from left to right. No two ants have the same initial position. 

Write a program that will determine the positions of all ants after some given time. 

입력

The first line of input file consists of two integers, L and T, 2 ≤ L ≤ 200,000 (the length of wire) and 1≤ T ≤ 1,000,000 (time in seconds), separated by a space character. 

The second line consists of integer N, 1 ≤ N ≤ 70,000 (number of ants), N < L. 

Each of the following N lines consists of initial position (the distance from the left end of the wire) and direction of each ant (from the ant number 1 up to the ant number N). Initial position is given by an integer and initial direction is given by a character 'L' (left) and 'R' (right). 

출력

The only output line should consist the final positions (the distances from the left end of the wire) of all ants, starting with the ant marked with number 1 and ending with the ant number N. 

3 5
1
1 D

0

5 5
2
2 D
4 L

1 3

8 10
5
1 L
3 L
4 D
6 L
7 D

1 2 4 7 7