Ants on a Rope

A rope of length $L$ is hung between two trees located at positions $0$ (east tree) and $L$ (west tree). There are $N$ ants on the rope. Initially, each ant crawls steadily at speed $1$ unit per time in one fixed direction: either towards the east tree (denoted by 'E') or towards the west tree (denoted by 'W'). Because the rope is too narrow, no two ants can crawl side by side or pass each other. Instead, when two ants meet, they immediately turn around and continue crawling.

The ants are numbered from $1$ to $N$ in the order of their initial positions from east to west. All ants will eventually get off the rope. For each ant, determine the time at which it falls off the rope.

Note: Although a collision makes two ants reverse direction, it is well known that this process is equivalent to the ants passing through each other with their identities swapped. You need to compute the final falling time for each ant under these conditions.

inputFormat

The first line contains two integers $L$ and $N$, representing the length of the rope and the number of ants respectively. Each of the following $N$ lines contains an integer $P$ and a character $D$, where $0 < P < L$ is the initial position from the east end and $D$ is the initial direction (either 'E' or 'W'). The ants are given in order from east to west (i.e. in increasing order of $P$).

outputFormat

Output $N$ lines. The $i$-th line should contain a number --- the time at which the ant with label $i$ (as defined by the input order) falls off the rope.

sample

10 2
2 W
6 E

6
8