Strange Solutions at Jeong Lab

Given a growing set of (A,B) pairs, decide each day whether the new pair is dominated by or lies on the segment between two existing points.

Hard8GeometryBinary searchSortingGreedyNo attempts yetTime limit1sMemory limit512 MB

Problem

Taeyoung is a scientist who runs experiments with strange solutions in his own small lab. The lab holds NN strange solutions of 1L each, and every solution contains component A and component B. Call this set of solutions SS.

One day Taeyoung wants to prepare a new 1L solution for an experiment. He dislikes extra work, so he uses only these two methods.

  1. Take one solution from SS and use it as it is.
  2. Take two solutions from SS and mix them in any ratio he wants, so that the total is 1L.

The two components are spread evenly inside a solution. For example, if you draw 0.3L out of a 1L solution that contains 5 units of component A, the drawn part contains exactly 1.5 units of component A.

By Taeyoung's theory, more of component A and more of component B are both better for an experiment. He does not know which one matters more, so he calls a 1L solution KK a bad solution when it meets the condition below.

Condition: using one of the two methods on the solutions in SS, he can prepare a solution whose amount of component A and amount of component B are both at least those of KK.

While preparing an experiment, Taeyoung decided that his lab has too few solutions, so he went shopping. He shops for MM days, and because shopping is a bother too, he buys at most one solution per day. On day ii he does this.

  1. He looks at a 1L solution KiK_i. If it is a bad solution, he buys nothing that day.
  2. If KiK_i is not a bad solution, he buys it and adds it to his collection SS.

The decision on day ii is made with every solution bought on the earlier days already inside SS.

Checking each solution by hand became a bother, so Taeyoung asked you for help. Decide, for every day, whether he should buy the solution.

Input

The first line contains the number of solutions that the lab holds at the start, NN (1N1051 \leq N \leq 10^5).

Each of the next NN lines contains two integers aia_i, bib_i (0ai,bi1090 \leq a_i, b_i \leq 10^9), the amount of component A and the amount of component B in the ii-th solution.

The next line contains the number of shopping days, MM (1M1051 \leq M \leq 10^5).

Each of the next MM lines contains two integers cic_i, did_i (0ci,di1090 \leq c_i, d_i \leq 10^9), the amount of component A and the amount of component B in the solution KiK_i.

Output

Print exactly MM lines. On the ii-th line print Yes if Taeyoung should buy the ii-th solution, and No if he should not buy it.