Enclose Points

Time Limit : 8 sec, Memory Limit : 262144 KB

Problem E: Enclose Points

There are $N$ points and $M$ segments on the $xy$-plane. Each segment connects two of these points and they don't intersect each other except at the endpoints. You are also given $Q$ points as queries. Your task is to determine for each query point whether you can make a polygon that encloses the query point using some of the given segments. Note that the polygon should not necessarily be convex.

Input

Each input is formatted as follows.

$N$ $M$ $Q$
$x_1$ $y_1$
...
$x_N$ $y_N$
$a_1$ $b_1$
...
$a_M$ $b_M$
$qx_1$ $qy_1$
...
$qx_Q$ $qy_Q$

The first line contains three integers $N$ ($2 \leq N \leq 100,000$), $M$ ($1 \leq M \leq 100,000$), and $Q$ ($1 \leq Q \leq 100,000$), which represent the number of points, the number of segments, and the number of queries, respectively. Each of the following $N$ lines contains two integers $x_i$ and $y_i$ ($-100,000 \leq x_i, y_i \leq 100,000$), the coordinates of the $i$-th point. The points are guaranteed to be distinct, that is, $(x_i, y_i) \ne (x_j, y_j)$ when $i \ne j$. Each of the following $M$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i < b_i \leq N$), which indicate that the $i$-th segment connects the $a_i$-th point and the $b_i$-th point. Assume that those segments do not intersect each other except at the endpoints. Each of the following $Q$ lines contains two integers $qx_i$ and $qy_i$ ($-100,000 \leq qx_i, qy_i \leq 100,000$), the coordinates of the $i$-th query point.

You can assume that, for any pair of query point and segment, the distance between them is at least $10^{-4}$.

Output

The output should contain $Q$ lines. Print "Yes" on the $i$-th line if there is a polygon that contains the $i$-th query point. Otherwise print "No" on the $i$-th line.

Sample Input

4 5 3
-10 -10
10 -10
10 10
-10 10
1 2
1 3
1 4
2 3
3 4
-20 0
1 0
20 0

Output for the Sample Input

No
Yes
No

Sample Input

8 8 5
-20 -20
20 -20
20 20
-20 20
-10 -10
10 -10
10 10
-10 10
1 2
1 4
2 3
3 4
5 6
5 8
6 7
7 8
-25 0
-15 0
0 0
15 0
25 0

Output for the Sample Input

No
Yes
Yes
Yes
No

Sample Input

8 8 5
-20 -10
-10 -10
-10 10
-20 10
10 -10
20 -10
20 10
10 10
1 2
2 3
3 4
1 4
5 6
6 7
7 8
5 8
-30 0
-15 0
0 0
15 0
30 0

Output for the Sample Input

No
Yes
No
Yes
No

Source: ACM-ICPC Japan Alumni Group Summer Camp 2015 , Day 4, Tokyo, Japan, 2015-09-14
http://acm-icpc.aitea.net/
http://jag2015summer-day4.contest.atcoder.jp/