Banana. Hide!

One day, a banana is being chased by a group of potatoes.

The banana is in an infinite two-dimensional plane. There are $n$ stationary potatoes and $m$ walls in the plane. Each wall is a line segment in the two-dimensional plane. The banana needs to choose a point in the plane to hide and will not move afterward.

Let $s_i$ be the line segment connecting the $i$-th potato and the banana. If no wall intersects $s_i$, we say the $i$-th potato can see the banana. Specifically, if two line segments lie on the same line, they are not considered to intersect. If two line segments intersect only at their endpoints, they are not considered to intersect.

Once the banana chooses a location, all potatoes that can see the banana will attack it, and each such potato will attack exactly once. When facing the attack from the $i$-th potato, the banana has a probability $p_i$ of not being hit. If the banana is hit by any potato that attacks it, it will die.

Please help the banana find the hiding location with the highest survival probability. You only need to output the survival probability; you do not need to output the hiding location. Note that the banana should not hide inside a wall, nor should it coincide with any potato.

Input

The input contains several test cases.

The first line contains an integer $T$ ($1 \le T \le 15$), representing the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n \le 10, 1 \le m \le 8$), representing the number of potatoes and the number of walls.

The second line contains $n$ floating-point numbers $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 1$). It is guaranteed that the decimal part has at most three digits.

The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th potato.

The next $m$ lines each contain four integers $x_1, y_1, x_2, y_2$, representing the two endpoints of the $i$-th wall. It is guaranteed that the two endpoints of a wall are not the same.

It is guaranteed that for all data, $n \le 100$ and $m \le 60$.

It is guaranteed that $|x_i|, |y_i|, |x_1|, |x_2|, |y_1|, |y_2| \le 100$.

Output

For each test case, output a single floating-point number representing the maximum survival probability of the banana.

If the absolute or relative error of your answer does not exceed $10^{-6}$, it will be considered correct. More formally, if your output is $a$ and the standard answer is $b$, your output will be accepted if and only if $\frac{|a-b|}{\max(1, |b|)} \le 10^{-6}$.

Examples

Input 1

4
2 2
0.500 0.500
0 5
0 -5
-2 -1 0 -1
0 1 2 1
2 2
1 1
0 5
0 -5
-2 -1 0 -1
0 1 2 1
2 2
0.300 0.300
0 5
0 -5
-2 -1 1 -1
-1 1 2 1
1 1
0.892
-9 0
0 0 1 0

Output 1

0.500000000000000
1.000000000000000
1.000000000000000
0.892000000000000