eolymp
bolt
Try our new interface for solving problems
Problems

Optical Optimization

Optical Optimization

Time limit 1 second
Memory limit 64 MiB

The state of a linearly polarized laser beam is represented by a pair of equal and opposite 2D vectors (blue), parametrized by (E, θ), where E0 is the beam's field strength and θ, θ < 180° is the beam's polarization angle. This representation is illustrated on the right:

A polarization filter is represented by a line (red) through the origin, parametrized by its filter angleφ, φ < 180°. When a filter φ is applied to a beam (E_a, θ_a), a new beam (E_b, θ_b) emerges, and is evaluated by

E_b = E_b|cos(θ_a−φ)|, θ_b = φ,

i.e. the new beam loses strength, and takes on the angle of the filter. Geometrically, the opposing vectors represented by (E_a,θ_a) are "orthogonally projected" onto the line represented by φ, forming new opposing vectors represented by (E_b,θ_b), as shown on the left:

Let us begin with a beam (E_0, θ_0) = (1, ). If we apply a filter φ_y = 90°, then we would obtain a beam with (E_y, θ_y) = (cos(90°), 90°) = (0, 90°), i.e. a beam with strength zero.

Suppose we have another filter ξ_x = 45°, and we apply it to (E_0,θ_0) before applying φ_y = 90°. We would obtain (E_x,θ_x) = (cos(45°),45°) first, followed by (E_y,θ_y) = (cos^2(45°),90°) = (0.5,90°). Therefore adding an extra filter can increase the strength of the final beam! This is illustrated by a double-projection:

In this problem, we would like to pass a beam (E_0, θ_0) = (1, 0°) sequentially through m fixed filters φ_1, φ_2, ..., φ_m. The intermediate beam emerging from filter φ_i is (E_i, θ_i) = (E_i, φ_i). We also have n extra filters that can have any angle, and can be placed before any fixed filter. Our objective is to find the maximum possible output field strength E_m.

Suppose each fixed filter φ_i is allotted k_i extra filters that interact with beam (E_i_{−1}, θ_i_{−1}) first (n = k_1 + k_2 + ... + k_m). The k_i extra filters before φ_i will have angles that evenly span between θ_i_{−1} and θ_i = φ_i, along the acute (or right) angle between θ_i_{−1} and φ_i. An example with k_i = 3 is shown on the right:

Using this method, the following formula can be derived:

where f(Δ,k) for Δ < 180° and k0 is defined as:

.

If k_i = 0 (no extra filter inserted) the formula degenerates into E_i = E_{i−1}|cos(θ_i−φ_i_{−1})|.

Since (E_0, θ_0) = (1, 0°), the expression for the final output strength is:

.

Given m, n, and φ_1, φ_2, ..., φ_m, your task is to compute the maximum possible E_m.

Input data

The first input line contains the number of test cases N, 1N100.

Each test case begins with integers m and n, separated by space. m lines follow, each containing an integer φ_i (for 1in).

  • m is the number of fixed filters, and satisfies 1m10.

  • n is the number of extra filters, and satisfies 0n100.

  • φ_i is the filter angle (in degrees) for the i'th fixed filter, and satisfies 0m < 180.

Note: Remember to convert degrees to radians before using cos().

Output data

For each test case, print the maximum possible magnitude for φ_m, to 8 decimal places.

Examples

Input example #1
6
1 0
90
1 1
90
1 100
1
2 2
80
134
6 23
79
131
66
75
11
170
3 100
0
0
0
Output example #1
0.00000000
0.50000000
0.99999849
0.46587532
0.64062165
1.00000000
Source University of Toronto 2010 ACM Tryout: Saturday, October 2, 2010