Balloon

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 $N$ 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)$ 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 = 2$, $x = 5$, $x = 6$ and $x = 8$.

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

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

The first line contains two integers $N$ and $C$, the number of segments that describe the ceiling and the number of queries.

Each of the next $N$ lines contains four integers $X_1$, $Y_1$, $X_2$, $Y_2$, describing a ceiling segment whose endpoints are $(X_1, Y_1)$ and $(X_2, Y_2)$.

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

Constraints

• $1 \le N \le 10^5$
• $1 \le C \le 10^5$
• $0 \le X_1, X_2 \le 10^6$
• $0 < Y_1, Y_2 \le 10^6$
• $X_1 \ne X_2$
• No two of the $2N$ endpoint x coordinates are equal, over all segments.
• No two segments have a point in common.
• $0 \le X \le 10^6$

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 $X$ and $Y$ separated by one space, the position $(x, y)$ at which the balloon gets stuck on the ceiling.