Japan Alumni Group Summer Camp 2013 Warming Up

G - Moving Points


Time limit時間制限 : 1.5sec / Memory limitメモリ制限 : 96MB

Description

You are given 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

The first line of the input file contains the integers 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

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.

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

Source name

The First KMCMonthly Contest

Submit提出する