덫을 지나는 가장 느린 속도

Fred는 지하 감옥을 탈출하려 한다. 바깥 통로까지는 이미 빠져나왔고, 이제 출구 문까지 일직선으로 달리기만 하면 된다. 문제는 통로에 덫이 깔려 있다는 점이다. 덫은 자석처럼 작동해서, 덫이 켜져 있는 동안 덫 구간 안에 있으면 Fred는 그 자리에 붙잡힌다. 덫의 경계선 위에 있는 것은 안전하다.

각 덫은 붙잡는 데 힘을 많이 쓰기 때문에 짧게만 켜져 있다. 덫 하나는 $A$초 동안 켜졌다가 $B$초 동안 꺼지기를 끝없이 반복한다. Fred는 시각 0에 위치 0에서 출발하고, 모든 덫도 같은 시각에 켜진 상태로 주기를 시작한다.

Fred는 일정한 속도 $v$로만 달린다. 어떤 덫이 구간 $[S_1, S_2]$를 덮는다면 Fred는 시각 $S_1/v$에 앞쪽 경계에 닿고 시각 $S_2/v$에 뒤쪽 경계를 벗어난다. 이 덫을 안전하게 지나려면 다음을 만족하는 음이 아닌 정수 $k$가 있어야 한다.

$k(A+B) + A \le \frac{S_1}{v}, \qquad \frac{S_2}{v} \le (k+1)(A+B)$

즉 덫이 꺼져 있는 한 구간 안에서 진입과 이탈이 모두 끝나야 한다.

모든 덫을 안전하게 지나는 속도 중 가장 느린 속도를 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($0 < T \le 10$)

각 테스트 케이스의 첫 줄에는 덫의 개수 $N$이 주어진다. ($0 < N \le 30$)

이어지는 $N$개의 줄에 덫 하나의 정보가 $A$ $B$ $S_1$ $S_2$ 순서로 주어진다.

• $A$는 덫이 켜져 있는 시간이고, 단위는 초다. ($0 < A < 32768$)
• $B$는 덫이 꺼져 있는 시간이고, 단위는 초다. ($0 < B < 32768$)
• $S_1$은 출발점에서 덫이 시작하는 위치이고, 단위는 미터다.
• $S_2$는 출발점에서 덫이 끝나는 위치이고, 단위는 미터다. ($0 < S_1 < S_2 < 32768$)

모든 값은 정수다. 서로 다른 덫의 구간이 겹칠 수도 있다.

각 테스트 케이스마다 한 줄씩 답을 출력한다.

안전하게 지날 수 있는 속도가 있으면 그중 가장 느린 속도를 초당 미터 단위로, 소수점 아래 넷째 자리까지 출력한다. 다섯째 자리에서 반올림하고, 정확히 5인 경우에는 올린다. 그런 속도가 없으면 IMPOSSIBLE을 출력한다.

덫이 하나뿐이고 $A = 3$, $B = 1$, $S_1 = 2$, $S_2 = 3$인 경우를 보자.

덫이 꺼져 있는 시간은 1초뿐이므로 Fred는 2미터 지점에서 3미터 지점까지를 1초 안에 지나야 한다. 그래서 속도가 초속 1미터보다 느릴 수 없다. 한편 덫이 처음 꺼지는 시각은 3초이므로, 2미터 지점에 3초보다 일찍 닿으면 붙잡힌다. 그래서 속도가 초속 $2/3$미터보다 빠를 수도 없다. 두 조건을 동시에 만족하는 속도가 없으니 답은 IMPOSSIBLE이다.