D. Disregard the Light
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Wiwi owns an enormous rectangular watermelon field whose sides are parallel to the axes. In the plane, its lower-left corner is at $$$(-10^{100}, -10^{100})$$$ and its upper-right corner is at $$$(10^{100}, 10^{100})$$$. To protect her crop from thieves, she has installed $$$N$$$ lamps at specified points inside the field. Each lamp shines light in all directions, and any point illuminated by at least one lamp is recorded by a central computer. There are no obstacles on the field, so light rays aren't blocked.

Two days later, Wiwi discovered that some watermelons had been stolen, but the recording showed no trespassers.

"Impossible... how did they manage to disregard all the light?"

Further investigation revealed that the thieves hack into the power grid, cut the electricity for a few seconds, and in that blackout deploy a large mirror. The mirror then casts a shadow behind it, so the thieves can steal watermelons without being seen. Fearing they can't carry too many at once, the thieves choose a target segment $$$\overline{CD}$$$ in advance and only steal melons located on that segment that lie in shadow.

More precisely, the mirror could be represented by a segment $$$\overline{AB}$$$. A watermelon at point $$$P$$$ is stolen if and only if:

  • $$$P$$$ lies on the target segment $$$\overline{CD}$$$.
  • For every lamp $$$L$$$, the segment $$$\overline{PL}$$$ intersects $$$\overline{AB}$$$. Note that endpoints count as intersections.

Because Wiwi was out of funds after installing the lamps, she can't stop the thief's trick even now that she knows it. Still, she wants to estimate her losses. Wiwi runs $$$Q$$$ simulations of possible thefts; for each one, she needs to compute the total length of the portion of segment $$$\overline{CD}$$$ that the thief could actually steal. Can you help her?

Input

The first line contains two integers $$$N$$$ and $$$Q$$$, the number of lamps and the number of theft simulations.

Each of the next $$$N$$$ lines contains two integers $$$x_i, y_i$$$, the coordinates of the $$$i$$$-th lamp.

Each of the following $$$Q$$$ lines contains eight integers $$$x_A, y_A, x_B, y_B, x_C, y_C, x_D, y_D$$$, describing one theft simulation, where points $$$(x_A, y_A)$$$ and $$$(x_B, y_B)$$$ are endpoints of the mirror, and points $$$(x_C, y_C)$$$ and $$$(x_D, y_D)$$$ are endpoints of the target segment.

  • $$$1 \leq N, Q \leq 2 \cdot 10^5$$$
  • The absoulate value of all the coordinates are at most $$$10^9$$$.
  • No two lamps share the same position.
  • No lamp lies exactly on the mirror in any simulation.
  • No lamp lies exactly on the target segment in any simulation.
  • The mirror segment and the target segment do not intersect.
  • For any theft simulation, $$$(x_A, y_A) \neq (x_B, y_B)$$$ and $$$(x_C, y_C) \neq (x_D, y_D)$$$.
Output

Output $$$Q$$$ lines. The $$$i$$$-th line should contain the answer to the $$$i$$$-th theft simulation. Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max(1, |b|)} \leq 10^{-6}$$$.

Example
Input
4 5
-6 1
0 -6
1 -10
10 6
-2 -14 4 -14 2 -16 8 -18
4 -10 10 -2 6 -10 14 -10
2 2 6 2 4 8 4 6
-8 6 -8 -10 -12 -8 -16 4
12 2 20 4 16 -10 26 6
Output
1.341572340677494
4.000000000000000
0.000000000000000
12.64911064067352
0.000000000000000
Note