P. Mario
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ruby and Aqua are playing Mario! Unfortunately, Aqua has fallen into one of the pipes. Since Aqua is a liquid, he is now flowing through it. As Ruby and Aqua's personal plumber, you have to rescue him!

The pipe is the infinite vertical strip between the lines $$$x=0$$$ and $$$x=W$$$. It is open at the top and bottom, and water flows from top to bottom.

Ruby installs $$$Q$$$ filters, one after another. Installation $$$i$$$ is described by four integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, and $$$d_i$$$.

  • If $$$d_i=0$$$, Ruby starts at $$$(0,a_i)$$$ and draws toward $$$(W,b_i)$$$.
  • If $$$d_i=1$$$, Ruby starts at $$$(W,a_i)$$$ and draws toward $$$(0,b_i)$$$.

Ruby stops drawing as soon as the new filter reaches the opposite wall or first touches a previously installed filter.

Filters have zero thickness, but a contact forms a sealed junction: water cannot slip between two filters at their common point. A portion of filter $$$i$$$ whose horizontal projection has length $$$\Delta x$$$ lets at most $$$c_i\Delta x$$$ units of water pass. Notice that $$$\Delta x$$$ is horizontal length in the $$$x$$$-direction, not Euclidean length.

More formally, after all installations, split every filter at all contact points. The filters divide the pipe into chambers. Water can move freely inside a chamber, but for a filter of horizontal length $$$\Delta x$$$, only $$$c_i \Delta x$$$ water can pass through the filter.

Find the maximum amount of water that can flow through the pipe per unit of time.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10$$$) — the number of test cases.

The description of each test case begins with two integers $$$W$$$ and $$$Q$$$ ($$$1 \le W \le 10^9$$$, $$$1 \le Q \le 10^5$$$) — the width of the pipe and the number of installations.

Each of the next $$$Q$$$ lines contains four integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, and $$$d_i$$$ ($$$-10^9 \le a_i,b_i \le 10^9$$$, $$$1 \le c_i \le 10^9$$$, $$$d_i\in\{0,1\}$$$), describing one installation.

It is guaranteed that the sum of $$$Q$$$ over all test cases does not exceed $$$10^5$$$.

For the following guarantees, define the intended left and right heights $$$(L_i,R_i)$$$ by $$$$$$ (L_i,R_i)= \begin{cases} (a_i,b_i), & d_i=0,\\ (b_i,a_i), & d_i=1. \end{cases} $$$$$$

Within each test case, the values $$$L_1,\ldots,L_Q$$$ are pairwise distinct, and the values $$$R_1,\ldots,R_Q$$$ are pairwise distinct. Furthermore, no three lines through $$$(0,L_i)$$$ and $$$(W,R_i)$$$ pass through one common point strictly inside the pipe. Consequently, every new filter either reaches the opposite wall or touches the interior of exactly one existing filter piece.

—

Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-2$$$ satisfy that the sum of $$$Q$$$ over all test cases is at most $$$200$$$.

Tests $$$3-4$$$ satisfy that the sum of $$$Q$$$ over all test cases is at most $$$5000$$$.

Tests $$$5-10$$$ satisfy $$$d_i=0$$$ for every installation in every test case.

Tests $$$11-20$$$ satisfy no additional constraints.

Output

For each test case, print one real number — the maximum amount of water that can flow through the pipe per unit of time.

Your answer is accepted if its absolute or relative error does not exceed $$$10^{-6}$$$.

Examples
Input
1
10 2
0 0 3 0
1 -2 1 0
Output
23.333333333333333
Input
1
10 3
0 0 5 0
10 -10 1 0
15 -5 2 1
Output
16.250000000000000
Note

Filter $$$2$$$ reaches filter $$$1$$$ at $$$x=10/3$$$, so its dashed continuation is not installed.

$$$20$$$ units of water can cross the right part of filter $$$1$$$, while another $$$10/3$$$ units can pass through filter $$$2$$$ and then filter $$$1$$$. The answer is $$$20+10/3=70/3$$$.