It's been a long day, and Max is on the bus headed home. He decides to check his email, and in his starred inbox he finds a puzzle newsletter he is subscribed to. He reads:
Consider a single-file, meter-long hallway. There are students in the hallway currently, each facing either left or right. Each student walks at the same speed of meters per second. Of course, with the hallway being single-file, students are bound to run into each other. In this particular hallway, however, when two students facing opposite directions bump into each other, they both immediately turn around, continuing to walk at the same speed in the opposite direction.
Max pictures a scenario like this, and continues reading,
How long would it take for all the students to exit the hall?
Given students exit the hall when they reach either end of the meter-length hallway, can you help Max solve this strange scenario?
Constraints
All are distinct.
Subtask 1 [50%]
Subtask 2 [50%]
Input Specification
The first line of input contains three integers: , , and .
The next lines each contain an integer , representing how far, in meters, the -th student is from the left-most end of the hallway, and either L
(for left) or R
(for right), the direction they're facing.
Output Specification
Output one number, the time, in seconds, it takes for all students to exit the hall. Answers within seconds will be deemed correct.
Sample Input
10 3 2
3 R
7 L
8 R
Sample Output
3.5
Sample Explanation
The first and second students bump into each other meters from the left-most end of the hallway, after second.
The third student exits the hallway after second.
The first and second students then each exit the hallway seconds after bumping into each other.
Comments