Moving Ants

Time limit1sMemory limit128 MB

Summary

Given ants bouncing on a segment that pass through each other when they collide, compute each ant's position after T seconds while preserving left-to-right ordering.

Level: Medium6 of 10
Topics: Simulation, Sorting, Math
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

Example 1
Input
```
3 5
1
1 D
```
Expected output
```
0
```
Example 2
Input
```
5 5
2
2 D
4 L
```
Expected output
```
1 3
```
Example 3
Input
```
8 10
5
1 L
3 L
4 D
6 L
7 D
```
Expected output
```
1 2 4 7 7
```