Moving Ants

There are N ants of negligible size on a line segment of length L. Every ant walks at a constant speed of 1 mm/s.

When an ant meets an obstacle, either an endpoint of the line or another ant, it immediately turns around and keeps walking at the same speed.

Initially, all ants are at distinct integer positions. They are numbered from 1 to N in left-to-right order. Given each ant's initial position and facing direction, determine the position of every ant after T seconds.

The first line contains the length L of the line segment and the time T. (2 ≤ L ≤ 200,000, 1 ≤ T ≤ 1,000,000) The unit of T is seconds.

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

Each of the next N lines gives the initial position and direction of one ant, in order from ant 1 to ant N. The initial position is an integer distance from the left endpoint of the line. The direction is L for left or D for right.

Print the ants' positions after T seconds in order from ant 1 to ant N, separated by spaces on one line.