This page is still under construction.

Parts of this page are still being built. What you see may change.

Trampoline

Time limit2sMemory limit512 MB

Summary
On a huge grid where only listed cells allow downward moves, answer for each of T queries whether a monotone path exists from one cell to another.
Level

Medium7 of 10

Topics
Sorting, Binary search, Prefix sum, Implementation
Solved
No attempts yet

Problem

Little Square has started jumping on trampolines in his school's gym. The gym has R × C trampolines arranged in a rectangular grid with R rows and C columns. Each trampoline is either green or blue. There are exactly N green trampolines. Let (i, j) denote the trampoline in the ith row and jth column. Rows are indexed from 1 to R and columns from 1 to C.

Little Square's teacher has asked him to practice T gymnastics routines. The ith routine has the following rules:

  • The routine starts at trampoline (xistart, yistart).
  • The routine ends at trampoline (xistop, yistop).
  • If Little Square jumps on a green trampoline at position (i, j), then he may go to trampolines (i + 1, j) or (i, j + 1), as long as these are not outside the grid.
  • If Little Square jumps on a blue trampoline at position (i, j), then he may go to trampoline (i, j+1), as long as it is not outside the grid.

Little Square wants to know, for each routine, whether it is possible to accomplish his teacher's request.

Input

The first line of the input contains R, C and N. The next N lines contain the positions of the green trampolines. If a line contains integers a b, then there is a green trampoline at position (a, b). The next line contains T. The next T lines contain the descriptions of the gymnastics routines. The ith of these lines contains xistart, yistart, xistop, yistop.

Output

Output T lines. The ith line should contain Yes if it is possible to accomplish the ith routine, and No if it is not.

Constraints

  • 1 ≤ R, C ≤ 1,000,000,000
  • 1 ≤ N, T ≤ 200,000
  • 1 ≤ xistart, xistop ≤ R
  • 1 ≤ yistart, yistop ≤ C
  • The coordinates of the green trampolines are pairwise distinct.

Hint

The trampolines are placed like so:

In the first routine Little Square can take the following route: (2, 1) → (2, 2) → (3, 2) → (3, 3) → (3, 4) → (4, 4) → (4, 5).

In the second routine Little Square can take the following route: (1, 2) → (1, 3) → (1, 4).

The third routine cannot be accomplished. No route exists from (2, 3) to (4, 4) that respects Little Square's teacher's rules.

Examples1

  1. Example 1

    Input
    4 5 2
2 2
3 4
3
2 1 4 5
1 2 1 4
2 3 4 4
    Expected output
    Yes
Yes
No