题目描述

Cruise control is a system that allows a car to go at a constant speed, while the driver controls only the steering wheel. The driver can, of course, turn off the cruise control to avoid collisions.

In this problem, we will consider a one-way road with two lanes, and $N$ cars using cruise control on the road. Each car is 5 meters long and goes at some constant speed. A car can change lanes at any time if it would not cause the car to collide with some other car (touching does not count as collision). Assume that changing lanes is instantaneous and simply causes the car to switch to the other lane. We are interested in whether any driver will have to turn off cruise control eventually to avoid a collision, or is it possible for all of them to drive (possibly switching lanes, but at constant speed) without collisions indefinitely. Note that even though changing lanes is instantaneous, two cars driving side by side cannot exchange places by changing lanes at the same time.

输入格式

The first line of the input file gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with the number $N$. $N$ lines follow, each describing a single car. Each line contains a character $C_i$ (denoting whether the car is initially in the left or the right lane), two integers describing the speed $S_i$ of the car (in meters per second), and the initial position $P_i$ of the car (in meters), denoting the distance between the rear end of the car and some fixed line across the road. All the cars are moving away from this line, and no car is behind the line.

输出格式

For each test case output one line containing "Case #x: y", where $x$ is the case number (starting from 1) and $y$ is either the word "Possible" (quotes for clarity only), if the cars can drive at the given constant speeds indefinitely, or the maximum number of seconds they can drive before somebody has to change speed to avoid a collision. Answers accurate to within $10^{-5}$ absolute or relative error will be accepted.

4
2
L 5 10
L 100 0
3
L 100 0
R 100 0
L 50 505
6
L 30 0
R 30 2
L 10 39
R 10 42
L 25 13
L 15 29
4
L 4 0
L 2 29
L 1 35
L 1 44

Case #1: Possible
Case #2: 10.0
Case #3: 1.4
Case #4: 12.0

提示

Sample Explanation

In the first case, the faster car can shift over to the right lane and easily overtake the slower one. In the second case, the two cars driving side-by-side at 100 m/s will reach the car going 50 m/s in 10 seconds, and somebody will have to change speed, as both lanes will be blocked.

Limits

• $1 \leq T \leq 30$.
• $1 \leq S_i \leq 1000$.
• $0 \leq P_i \leq 10000$.
• Each of the $C_i$ characters will be either $L$, denoting the left lane, or $R$, denoting the right lane.
• Initially the cars' positions are such that they do not collide, that is, if two cars $i$ and $j$ have the same initial starting lane (that is, $C_i = C_j$), then $|P_i - P_j| \geq 5$.

Test set 1 (17 Pts, Visible Verdict)

• $1 \leq N \leq 6$.

Test set 2 (30 Pts, Hidden Verdict)

• $1 \leq N \leq 50$.