21972번 - Trampoline 서브태스크다국어

Little Square has started jumping on trampolines from his school’s gym. In the gym there are 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 i^th row and j^th column. We index the rows from 1 to R and the columns from 1 to C.

Little Square’s teacher has asked him to practice T gymnastics routines. The i^th routine has the following rules:

• The routine starts at trampoline (x_i^start, y_i^start).
• The routine ends at trampoline (x_i^stop, y_i^stop).
• 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, if it is possible to accomplish his teacher’s request.

On the first line of the input you will find R, C and N. On the next N lines you will find the positions of the green trampolines. If a line contains integers a b then there is a green trampoline at position (a, b). On the next line you will find T. On the next T lines you will find the descriptions of the gymnastics routines. On the i^th of these lines you will find x_i^start, y_i^start, x_i^stop, y_i^stop.

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

• 1 ≤ R, C ≤ 1,000,000,000
• 1 ≤ N, T ≤ 200,000
• 1 ≤ x_i^start, x_i^stop ≤ R
• 1 ≤ y_i^start, y_i^stop ≤ C
• The coordinates of green trampolines are pairwise distinct.

• 1 ≤ R, C, T ≤ 200

• 1 ≤ R, C ≤ 2,500
• 1 ≤ T ≤ 4,000

• x_i^stop - x_i^start = 1

• 1 ≤ T, N ≤ 5,000

• No additional constraints.

The trampolines are placed like so:

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

In the second routine Little Square can go on 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.