题目背景

The official time limit of this problem is unknown.

题目描述

In Barareh, a Point-to-Point (P2P) wireless network is used to connect base stations for private data services. In a P2P wireless network, each base station uses some directional antennas to connect with the other base stations. If base stations are modeled as points and communication links are modeled as line segments, the P2P network in Barareh surprisingly has some geometric properties. Specifically, the network is a planar graph whose outer boundary is a convex polygon and all interior faces are triangles.

In the recent world conflicts, an important question has occupied the mind of Khorzukhan, the Minister of Information and Communications Technology (ICT) of Barareh. He wants to know how resilient the network is to electromagnetic attacks. In an electromagnetic attack, noise is created in a certain region (so-called attack region), disrupting all communications passing through that region. The remaining network consists of every base station and every communication link that were strictly outside of the attack region. Specifically, Khorzukhan wants to know if the remaining network remains connected. To achieve this, he has instructed his ministry to simulate multiple electromagnetic attacks separately, testing the network's tolerance to interference and reporting whether the remaining network stays connected after each simulation.

输入格式

The first line of input contains $n$, $m$, and $k$ ($3 \leq n \leq 10^5$, $3 \leq m \leq 3 \cdot 10^5$, $1 \leq k \leq 10^5$), which are the number of base stations, the number of communication links, and the number of attack simulations, respectively.

In the next $n$ lines, the $i^{th}$ line contains the $x$ and $y$ coordinates of the $i^{th}$ base station, both of which are non-negative integers ($0 \leq x, y \leq 10^9$). It is guaranteed that not all base stations are collinear.

Each of the next $m$ lines represents a communication link. Each line contains two integers $i$ and $j$ ($1 \leq i, j \leq n$), representing a communication link as a straight line segment between the $i^{th}$ and $j^{th}$ base station. The $m$ communication links form a planar graph. The outer boundary is a convex polygon and interior faces are all triangles.

At the end, the attack regions come in $k$ lines. Each attack region is a non-empty rectangle, represented by the coordinates $x_1, y_1, x_2, y_2$ of its lower-left and upper-right corners ($0 \leq x_1 < x_2 \leq 10^9$, $0 \leq y_1 < y_2 \leq 10^9$). The sides of all rectangles are parallel to the coordinate axes. Note that if a base station or some part (even one point) of a link lies inside the attack region (including the boundary), it is not usable during the attack.

输出格式

In $k$ lines, for each attack simulation, print Yes if the remaining network resulting from the attack is connected; otherwise print No. If all base stations are within the attack region, the remaining network becomes empty and is still considered connected.

5 8 2
1 1
1 5
5 4
4 2
3 4
1 2
2 3
3 4
4 1
5 1
5 2
5 3
5 4
1 2 4 5
2 3 3 4

No
Yes

提示

In the first attack simulation, the first and third base stations are outside the attack region; however, they are not connected to each other.

:::align{center} :::