Under construction

Still being built. Things may change

Balloon

Time limit2sMemory limit512 MB

Summary
Given N disjoint ceiling segments, trace each vertically rising balloon as it sticks to horizontal segments or slides to the higher endpoint of tilted ones, and report the final resting point or escape x coordinate.
Level

Hard8 of 10

Topics
Geometry, Sorting, Binary search, Simulation
Solved
No attempts yet

Problem

After a programming contest, the balloons that come loose and float up to the ceiling of the hall have to be collected. The contract with the owner of the hall requires the hall to be cleaned right after the event, and a fine applies otherwise. This year the organizers obtained the design drawing of the ceiling in advance. They want to know, for a balloon released at a given point of the floor, whether the ceiling blocks it and where it stops, or whether it escapes out of the hall.

Seen from the side, the ceiling is NN line segments. No two of these segments have a point in common.

A balloon is a point. It is released on the floor at (X,0)(X, 0) and rises straight up. What happens next depends on the first segment it touches. The endpoints of a segment belong to that segment, so a balloon that rises exactly into an endpoint touches it.

  • If the segment is horizontal, the balloon gets stuck there.
  • If the segment is tilted, the balloon glides along it to the highest endpoint of that segment, is released from that point, and rises straight up again. It can then touch another segment, or it can escape out of the hall.

The figure below shows one ceiling. The four marked points of the floor, a, b, c and d, are at x=2x = 2, x=5x = 5, x=6x = 6 and x=8x = 8.

For that ceiling, the balloons released at a and at b both get stuck at (2,5)(2, 5), the balloon released at c gets stuck at (6,5)(6, 5), and the balloon released at d is not blocked and escapes out of the hall at x=7x = 7.

Read the description of the ceiling and answer CC queries about the final position of balloons released on the floor.

Input

The first line contains two integers NN and CC, the number of segments that describe the ceiling and the number of queries.

Each of the next NN lines contains four integers X1X_1, Y1Y_1, X2X_2, Y2Y_2, describing a ceiling segment whose endpoints are (X1,Y1)(X_1, Y_1) and (X2,Y2)(X_2, Y_2).

Each of the next CC lines contains one integer XX, a query asking what happens to a balloon released at the point (X,0)(X, 0).

Constraints

  • 1≤N≤1051 \le N \le 10^5
  • 1≤C≤1051 \le C \le 10^5
  • 0≤X1,X2≤1060 \le X_1, X_2 \le 10^6
  • 0<Y1,Y2≤1060 < Y_1, Y_2 \le 10^6
  • X1≠X2X_1 \ne X_2
  • No two of the 2N2N endpoint x coordinates are equal, over all segments.
  • No two segments have a point in common.
  • 0≤X≤1060 \le X \le 10^6

Output

Print one line for each query, in the order the queries are given. If the balloon escapes the hall, the line contains one integer, the x coordinate at which the balloon escapes. Otherwise the line contains two integers XX and YY separated by one space, the position (x,y)(x, y) at which the balloon gets stuck on the ceiling.

Examples2

  1. Example 1

    Input
    4 4
0 1 3 3
1 5 6 5
5 3 2 4
7 4 10 2
2
5
8
6
    Expected output
    2 5
2 5
7
6 5

  2. Example 2

    Input
    4 3
1 3 4 2
10 3 7 4
2 3 8 3
3 5 5 4
4
9
8
    Expected output
    1
7
8 3