정속 주행

정속 주행 장치는 운전자가 운전대만 조작하는 동안 자동차가 일정한 속도로 주행할 수 있게 하는 시스템이다. 물론 운전자는 충돌을 피하기 위해 정속 주행 장치를 끌 수 있다.

이 문제에서는 차선이 두 개인 일방통행 도로와, 그 도로에서 정속 주행 장치를 사용하는 N대의 자동차를 고려한다. 각 자동차의 길이는 5미터이며 일정한 속도로 주행한다. 자동차는 다른 자동차와 충돌하지 않는다면 언제든지 차선을 변경할 수 있다(접촉은 충돌로 간주하지 않는다). 차선 변경은 순간적으로 이루어지며 자동차가 단순히 반대쪽 차선으로 옮겨 간다고 가정한다. 어떤 운전자든 결국 충돌을 피하기 위해 정속 주행 장치를 꺼야 하는지, 아니면 모두가 (차선을 변경할 수도 있지만 일정한 속도로) 충돌 없이 무한히 주행할 수 있는지 알아보고자 한다. 차선 변경이 순간적으로 이루어지더라도 나란히 주행하는 두 자동차가 동시에 차선을 변경하여 서로 자리를 바꿀 수는 없다는 점에 유의한다.

제한

메모리 제한: 1GB. 테스트 세트당 시간 제한: 40초. 1 ≤ T ≤ 30. 1 ≤ $S_{i}$ ≤ 1000. 0 ≤ $P_{i}$ ≤ 10000. $C_{i}$개의 각 문자는 왼쪽 차선을 나타내는 L 또는 오른쪽 차선을 나타내는 R이다. 처음에 자동차들의 위치는 서로 충돌하지 않도록 주어진다. 즉, 두 자동차 i와 j의 초기 출발 차선이 같다면(즉, $C_{i}$ = $C_{j}$라면), |$P_{i}$ - $P_{j}$| ≥ 5이다.

테스트 세트 1 (Visible Verdict)

1 ≤ N ≤ 6.

테스트 세트 2 (Hidden Verdict)

1 ≤ N ≤ 50.

입력 파일의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 수 N으로 시작한다. 이어지는 N개의 줄은 각각 자동차 한 대를 설명한다. 각 줄에는 자동차가 처음에 왼쪽 차선과 오른쪽 차선 중 어느 차선에 있는지를 나타내는 문자 $C_{i}$, 자동차의 초당 미터 단위 속도 $S_{i}$를 나타내는 정수, 그리고 자동차의 미터 단위 초기 위치 $P_{i}$를 나타내는 정수가 주어진다. 초기 위치는 자동차의 뒤쪽 끝과 도로를 가로지르는 어떤 고정된 선 사이의 거리를 나타낸다. 모든 자동차는 이 선에서 멀어지는 방향으로 이동하며, 선 뒤에 있는 자동차는 없다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 (1부터 시작하는) 케이스 번호이고, y는 자동차들이 주어진 일정한 속도로 무한히 주행할 수 있다면 단어 "Possible"(따옴표는 명확성을 위해서만 사용됨)이며, 그렇지 않다면 누군가가 충돌을 피하기 위해 속도를 변경해야 하기 전까지 주행할 수 있는 최대 시간(초)이다. 절대 오차 또는 상대 오차가 10^{-5} 이내인 답은 정답으로 인정된다.

첫 번째 경우에는 더 빠른 자동차가 오른쪽 차선으로 옮겨 가서 더 느린 자동차를 쉽게 추월할 수 있다. 두 번째 경우에는 100 m/s의 속도로 side-by-side 주행하는 두 자동차가 50 m/s의 속도로 가는 자동차에 10초 후에 도달하며, 두 차선이 모두 막히므로 누군가는 속도를 변경해야 한다.