The Slowest Speed Past the Traps

Fred is escaping from an underground prison. He has already reached the outer corridor, and all that is left is a straight run to the exit door. The trouble is that the corridor is lined with traps. A trap works like a magnet, so Fred is held in place if he is inside the trap area while the trap is active. Standing exactly on the edge of a trap is safe.

Capturing a runner costs a trap a lot of energy, so a trap stays on only briefly. Each trap is active for $A$ seconds, then inactive for $B$ seconds, and repeats that cycle forever. Fred starts at position 0 at time 0, and every trap begins its cycle in the active state at that same moment.

Fred runs at one constant speed $v$. If a trap covers the segment $[S_1, S_2]$, Fred touches its near edge at time $S_1/v$ and leaves its far edge at time $S_2/v$. He passes that trap safely only if some nonnegative integer $k$ satisfies

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

so that he both enters and leaves during a single inactive window of that trap.

Find the slowest speed that carries Fred safely past every trap.

The first line has the number of test cases $T$. ($0 < T \le 10$)

The first line of each test case has the number of traps $N$. ($0 < N \le 30$)

Each of the next $N$ lines describes one trap as $A$ $B$ $S_1$ $S_2$.

• $A$ is how long the trap stays active, in seconds. ($0 < A < 32768$)
• $B$ is how long the trap stays inactive, in seconds. ($0 < B < 32768$)
• $S_1$ is where the trap starts, in meters from the starting point.
• $S_2$ is where the trap ends, in meters from the starting point. ($0 < S_1 < S_2 < 32768$)

All values are integers. Segments of different traps may overlap.

Print one line for each test case.

If a safe speed exists, print the slowest one in meters per second with four digits after the decimal point. Round at the fifth digit, and round up when that digit is exactly 5. If no such speed exists, print IMPOSSIBLE.

Take a corridor with a single trap where $A = 3$, $B = 1$, $S_1 = 2$ and $S_2 = 3$.

The trap is inactive for only 1 second, so Fred has to cover the stretch from 2 meters to 3 meters within 1 second, which means his speed cannot be below 1 meter per second. The trap first turns off at second 3, so reaching the 2 meter mark before second 3 gets him caught, which means his speed cannot be above $2/3$ meter per second. No speed satisfies both conditions, so the answer is IMPOSSIBLE.