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.

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}$.

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.

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

No Yes No

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

No Yes Yes Yes No

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

No Yes No Yes No

Source: ACM-ICPC Japan Alumni Group Summer Camp 2015
, Day 4, Tokyo, Japan, 2015-09-14

http://jag-icpc.org/

http://jag2015summer-day4.contest.atcoder.jp/

http://jag-icpc.org/

http://jag2015summer-day4.contest.atcoder.jp/