정속 주행 장치 (Large)

정속 주행 장치는 운전자가 조향만 하고 속도는 그대로 유지되도록 해 주는 장치다. 물론 운전자는 충돌을 피하려고 장치를 끌 수 있다.

여기서는 차선이 두 개인 일방통행 도로와 그 위에서 정속 주행 장치를 켜고 달리는 자동차 $N$대를 생각한다. 자동차의 길이는 모두 5미터이고, 각자 일정한 속도로 달린다. 자동차는 다른 자동차와 충돌하지 않는 한 아무 때나 차선을 바꿀 수 있다. 두 자동차가 스치듯 맞닿는 것은 충돌로 세지 않는다. 차선 변경은 순간적으로 일어나며, 자동차가 반대편 차선으로 옮겨 가는 것 말고는 아무 일도 일어나지 않는다. 차선 변경이 순간적이더라도 나란히 달리는 두 자동차가 동시에 차선을 바꿔 서로 자리를 맞바꾸는 것은 안 된다.

모든 자동차가 처음에 주어진 속도를 그대로 유지한 채 (차선은 얼마든지 바꿔도 된다) 영원히 충돌 없이 달릴 수 있는지, 아니면 언젠가 누군가는 충돌을 피하려고 정속 주행 장치를 꺼야 하는지 판정한다. 꺼야 한다면 그 순간까지 달릴 수 있는 최대 시간을 구한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 자동차의 수 $N$이 주어진다. 이어지는 $N$개의 줄에는 자동차가 한 대씩 주어지며, 각 줄은 문자 $C_i$와 정수 두 개 $S_i$, $P_i$로 이루어진다. $C_i$는 그 자동차가 처음에 있는 차선으로, 왼쪽 차선이면 L, 오른쪽 차선이면 R이다. $S_i$는 자동차의 속도이고 단위는 초당 미터다. $P_i$는 도로를 가로지르는 고정된 기준선에서 자동차 뒷범퍼까지의 거리이고 단위는 미터다. 모든 자동차는 기준선에서 멀어지는 방향으로 달리며, 기준선 뒤에 있는 자동차는 없다.

• $1 \le T \le 30$
• $1 \le N \le 50$
• $1 \le S_i \le 1000$
• $0 \le P_i \le 10000$
• $C_i$는 L 또는 R이다.
• 처음에 자동차들은 충돌하지 않는다. 즉 같은 차선에서 출발하는 두 자동차 $i$, $j$에 대해 $|P_i - P_j| \ge 5$이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다. 모든 자동차가 주어진 속도를 유지한 채 영원히 달릴 수 있으면 $y$는 Possible이고, 그렇지 않으면 $y$는 누군가 속도를 바꿔야 하기 전까지 달릴 수 있는 최대 시간이며 단위는 초다.

시간은 소수가 아니라 기약분수로 정확히 출력한다. 답이 $p/q$ ($q \ge 1$, $\gcd(p, q) = 1$)일 때 $q$가 2 이상이면 p/q 형태로 쓰고, $q$가 1이면 p만 쓴다. 답이 0이면 0이라고 쓴다.

예제의 첫 번째 케이스에서는 빠른 자동차가 오른쪽 차선으로 옮겨 느린 자동차를 손쉽게 추월한다. 두 번째 케이스에서는 초속 100미터로 나란히 달리는 두 자동차가 10초 뒤에 초속 50미터로 달리는 자동차를 따라잡는다. 그때 두 차선이 모두 막혀 있으므로 누군가는 속도를 바꿔야 한다.