Linear Interpolation

You are given a collection of 2D points via the array points, where several points can share the same x-coordinate. Use these points to define a piecewise linear function. For each value in the array queries, compute the interpolated y-value according to these rules:

• When the query's x-value equals an existing x-coordinate, the result is the maximum y among all points with that x.
• When the query lies strictly between two distinct x-coordinates, linearly interpolate using the largest y at the smaller x and the smallest y at the larger x.
• When the query is smaller than the minimum x-coordinate present, extrapolate using the segment formed by the two smallest distinct x-coordinates, each taken with its smallest y.
• When the query is larger than the maximum x-coordinate present, extrapolate using the segment formed by the two largest distinct x-coordinates, each taken with its largest y.

Return the results in the same order as the queries.

Constraints:

• 2 ≤ points.length ≤ 10^5
• 1 ≤ queries.length ≤ 10^5
• There are at least two distinct x-values in points
• Answers within 10^{-3} of the correct value are accepted

Example 1:

Example 2:

Example 3:

Examples

Example 1

Input:
4
0.0 0.0
1.0 1.0
2.0 0.0
3.0 1.0
5
0.5
1.5
2.5
-1.0
4.0
Output:
0.5
0.5
0.5
-1.0
2.0

Example 2

Input:
2
0.0 0.0
10.0 10.0
3
0.0
10.0
5.0
Output:
0.0
10.0
5.0