Victor likes trains. Who doesn't?

Victor owns $N$ trains and two rails that are parallel to each other and connected at their ends. The upper rail has trains moving from left to right, the lower rail has trains moving from right to left. When a train reaches an endpoint, it switches to the other rail. Both rails have length $M$, and when the trains are arranged properly, they are equally separated from each other by a distance of $\frac{2M}{N}$.

Roger, Victor's arch-nemesis, has disrupted Victor's trains and arranged them haphazardly. Victor wishes to restore the trains so that they are equally separated from each other. To do this, while the trains are moving, he can force any subset of them to stop running for some amount of time or switch them to the opposite rail. Trains move at a rate of one unit per second when not stopped.

Compute the minimum time in seconds needed for Victor to restore balance to his trains!

Constraints

$1\le N\le {10}^5$

$100\le M\le {10}^8$

$0\le x_i\le M$

Subtask 1 [50%]

$N\le 200$

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line will contain two integers, $M$ and $N$.

Each of the next $N$ lines will contain an integer $x_i$ representing the distance from the left endpoint, followed by a character L or R representing the direction that the train is moving in.

Output Specification

Print, on a single line, the minimum amount of time needed for Victor to restore balance. This amount must have an absolute error of at most ${10}^{-6}$ when compared with the judge output.

Sample Input 1

100 5
5 R
35 L
46 L
75 L
85 R

Sample Output 1

0.5

Sample Input 2

100 8
9 L
15 R
41 L
33 L
81 R
33 R
100 L
97 R

Sample Output 2

15.5