G - Moving Points
Editorial
/

You are given

Your task is to calculate the distance to the furthest point in Manhattan distance from the origin at time

The first line of the input file contains the integers

The next

The next

For each query, output the maximal Manhattan distance in one line.

The value which is accurate to within a relative or absolute value of 1E-9 will be accepted.

Time Limit: 1.5 sec / Memory Limit: 93 MB

### Description

`N`points in the

`xy`-plane. Each point is in a state of linear uniform motion.

Your task is to calculate the distance to the furthest point in Manhattan distance from the origin at time

`t`.

### Input

`N`and

`M`(

`1 \leq N, M \leq 10^5`), separated by a space.

The next

`N`lines describe the points. Each contains four real numbers

`x`,

`y`,

`vx`and

`vy`(

`|x|,|y|,|vx|,|vy| \leq 10^6`). This shows the initial coordinates

`(x, y)`and velocity

`(vx, vy)`.

The next

`M`lines describe the queries. Each line contains one real number

`t`(

`0 \leq t \leq 10^6`).

### Output

The value which is accurate to within a relative or absolute value of 1E-9 will be accepted.

### Sample Input

2 2 0 0 1 0 1 0 -1 0 0 1

### Sample Output

1.0000000000 1.0000000000

### Sample Input

3 3 0 0 1 1 0 1 1 0 3 3 -2 -1 0 1 2

### Sample Output

6.0000000000 3.0000000000 4.0000000000

### Sample Input

3 3 1 1 0.5 0 0 2 1.5 -1 1.5 0 0 1 0 1 2

### Sample Output

2.0000000000 2.5000000000 3.5000000000