Mobile Gaming

Time limit1sMemory limit256 MB

Summary

Two rectangles move at constant speed from time 0 to 1; report the first moment they touch or overlap, or report no collision.

Level: Medium5 of 10
Topics: Geometry, Intervals, Math
Solved: No attempts yet

Problem

Online gaming on mobile phones has become popular, so you are building a cops and robbers game. Some players control the cops, and the others control the robbers. A cop wants to catch a robber, and a robber tries to escape.

During development you ran into a problem. The phones update slowly, and you sometimes get a player position only once per second. Scoring depends on the moment a cop caught a robber, so you have to compute that moment exactly.

Cops and robbers are rectangles in the game world, and a cop has caught a robber when their rectangles overlap. You are given the size of each rectangle and its position at time 0 and at time 1. Decide whether the two rectangles overlap at some moment between time 0 and time 1, and if they do, find the first such moment.

Input

The first line contains the number of test cases $T$ . Each test case consists of two lines with six integers each.

The first line contains $W_1$ , $H_1$ , $Xstart_1$ , $Ystart_1$ , $Xend_1$ , $Yend_1$ . $W_1$ and $H_1$ are the width and the height of the cop rectangle. $(Xstart_1, Ystart_1)$ is its upper left corner at time 0, and $(Xend_1, Yend_1)$ is its upper left corner at time 1.

The second line contains the same six values for the robber: $W_2$ , $H_2$ , $Xstart_2$ , $Ystart_2$ , $Xend_2$ , $Yend_2$ .

$0 < T \le 100$
$0 < W_i, H_i \le 100$
$0 \le Xstart_i, Ystart_i, Xend_i, Yend_i \le 10000$
Every value in the input is an integer.
In the coordinate system $x$ grows from left to right and $y$ grows from top to bottom.
A collision happens when the two rectangles overlap, and also when only their sides or corners touch.
The cop and the robber each move along a straight line at constant speed from the position at time 0 to the position at time 1.

Output

For each test case, print the first moment at which a collision happens, one moment per line. The value lies between 0 and 1, inclusive.

Round at the seventh digit after the decimal point and always print exactly six digits, so write 0.000000 or 1.000000 with the trailing zeros. A value that falls exactly halfway rounds up.

If there is no collision, print No Collision instead.

Examples6

Example 1

Input

3
2 2 0 0 0 8
2 2 2 10 2 2
5 5 10 10 0 0
1 4 0 0 10 0
4 4 3 9 10 18
3 3 8 14 15 23

Expected output

0.500000
0.600000
No Collision

Example 2

Input

2
3 3 0 0 100 100
2 2 1 1 200 200
5 5 7 7 7 7
5 5 7 7 7 7

Expected output

0.000000
0.000000

Example 3
Input
```
1
1 1 0 0 0 0
1 1 10 0 1 0
```
Expected output
```
1.000000
```
Example 4
Input
```
1
2 2 0 0 0 0
2 2 10 2 0 2
```
Expected output
```
0.800000
```

Example 5

Input

1
1 1 0 0 0 0
1 1 0 10 10 0

Expected output

No Collision

Example 6
Input
```
1
1 1 3 0 3 0
1 1 0 0 6 0
```
Expected output
```
0.333333
```