Grazing Alibi Investigation

Note: The time limit for this problem is 4s, two times the default.

Farmer John's private gardens (numbered by grazing events) have been grazed at precise times. He has determined that a single cow was responsible for all of these grazing incidents. However, each of his N cows has submitted an alibi in the form of a location at a specific time. A cow can be declared innocent if it is impossible for her to have travelled between all of the grazing events and her alibi under the speed constraint.

Cows travel at a maximum speed of 1 unit distance per unit time. That is, for any two events (t₁, x₁) and (t₂, x₂) with t₁ ≤ t₂, it is possible to travel between them if and only if \( |x_2-x_1| \le t_2-t_1 \).

Given the times and locations of the G grazing events and the alibi (time and location) for each of the N cows, determine for each cow whether her alibi forces her to be innocent. In other words, check if it is impossible for a cow to cover all grazing events and her alibi.

Input events are not necessarily given in order; you may sort the grazing events by time. Note that the grazing events themselves are known to be internally consistent (i.e. a single cow could have made them all) and so the only possible inconsistency arises when trying to include the cow's alibi event into the timeline.

A cow is innocent if, when inserting her alibi into the timeline of grazing events, one of the adjacent travel segments fails the condition \( |x_2-x_1| \le t_2-t_1 \). Otherwise, her alibi is not a proof of innocence.

inputFormat

The first line contains two integers G and N (1 ≤ G, N ≤ 10⁵), the number of grazing events and the number of cows with alibis.

The next G lines each contain two integers t and x, representing the time and location of a grazing event. These events may be given in any order, but are guaranteed to be mutually consistent (i.e. there exists a route that visits all grazing events under the travel constraint).

The following N lines each contain two integers t and x, representing the time and location of a cow's alibi.

outputFormat

For each cow (in the order given in the input), output a single line containing YES if the cow is innocent (i.e. it is impossible for her to travel between all grazing events and her alibi) or NO otherwise.

sample

3 3
10 5
20 10
30 15
15 6
25 14
25 20

NO
NO
YES