8. Svinstvo na koberci

Krtko si na oslavu svojho novo zrekonštruovaného bytu pozval všetkých vedúcich. Kubíkovi sa byt tak páčil, že sa rozhodol kúpiť nový nábytok do Klubovne Spokojných Programátorov. Zohnal nové staré stoly, kolieskové stoličky bez koliesok aj pekné preplnené skrine. Nákup zavŕšil novým viacdielnym kobercom. Ten sa skladá z viacerých kúskov uložených tak, že na podlahe tvoria mapu.

Netrvalo dlho a na čistučkom koberci sa začali každý deň objavovať zablatené stopy, zadupaná čokoláda či škrny od kofoly. Tie treba rýchlo odstrániť, inak sa do koberca zažerú nastálo.

Kubík dostal briliantný nápad. Na strop pripevnil kameru namierenú na koberec, takže vie presnú polohu každej škvrny v momente, keď sa objaví. Od vás chce program, ktorý mu povie veľkosť zašpineného kusu koberca, aby mohol objednať správne množstvo čistiacich prostriedkov.

Úloha

Na vstupe dostanete zadanú mapu koberca v podobe súvislého planárneho grafu (vrcholy so súradnicami a hrany medzi nimi) a niekoľko bodov. Vašou úlohou je pre každý bod nájsť veľkosť uzavretej oblasti, v ktorej leží (tj. jej obsah). Ak sa bod nenachádza v žiadnej uzavretej oblasti, vypíšte \(-1\). Body ležiace na niektorej hrane grafu (vrátane jej okrajov) považujeme, že nie sú vo vnútri žiadnej uzavretej oblasti.

Pozor! Túto úlohu je treba riešiť online, čiže testovač vášmu programu posiela otázky postupne. Každú nasledujúcu otázku dostanete až po tom, čo zodpoviete aktuálnu. Nezabudnite flushovat, aby sa vaša odpoveď skutočne testovaču odoslala a netrávila prázdniny v nejakom buffri. (C++ cout.flush(), Python sys.stdout.flush(), pre iné jazyky si vyhľadajte.)

Formát vstupu

Na prvom riadku vstupu je číslo \(n\)—počet vrcholov, \(m\)—počet hrán a \(q\)—počet otázok.

Potom prázdny riadok, a nasleduje \(n\) riadkov (\(n \geq 1\)) obsahujúcich \(2\) čísla—súradnice daného vrchola. Môžete predpokladať, že žiadne dve vrcholy nie sú ten istý bod v rovine. Všetky súradnice sú celé čísla, ktoré v absolútnej hodnote neprevýšia \(10^9\).

Potom prázdny riadok, a na ďalších \(m\) riadkoch (\(m \geq 0\)) sú vždy \(2\) čísla—čísla vrcholov, medzi ktorými vedú hrany. Vrcholy číslujeme \(1, 2, \ldots, n\). Môžete predpokladať, že ak niektoré tri vrcholy \(a, b, c\) ležia na jednej priamke v tomto poradí, tak na vstupe nebude hrana \(ac\). Takisto sa žiadna hrana na vstupe nevyskytne viackrát, a žiadne dve hrany sa nekrižujú. Koncové vrcholy každej hrany sú rôzne. Zadaný graf je súvislý.

Potom prázdny riadok, a na každom z posledných \(q\) riadkov (\(q \geq 0\)) sú \(2\) čísla—súradnice bodu z otázky.

Súradnice všetkých bodov sú nezáporné a neprevyšujú \(10^9\).

Formát výstupu

Pre každý bod vypíšte riadok obsahujúci jedno číslo—veľkosť oblasti, v ktorej sa nachádza. Ak bod neleží v žiadnej uzavretej oblasti, vypíšte \(-1\). Pokiaľ je výsledok celočíselný, nevypisujte žiadne desatinné miesta, v opačnom prípade vypíšte jedno desatinné miesto. (Rozmyslite si, že obsah každej z oblastí je nutne celočíselným násobkom \(\frac{1}{2}\).)

Hodnotenie

Obmedzenia v jednotlivých sadách sú nasledovné:

Príklady

Input:

5 7 5

10 6
7 10
9 1
0 6
2 0

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

8 6
0 3
2 5
7 0
8 1

Output:

-1
-1
25
-1
22

Obrázok prvého vstupu:

Input:

7 10 5

7 3
0 4
0 8
3 2
10 0
7 6
0 10

6 2
6 7
5 4
3 7
5 1
6 5
6 4
2 4
3 2
6 3

5 4
5 2
8 1
2 5
4 4

Output:

-1
18
18
14
10

Obrázok druhého vstupu:

Input:

9 12 5

3 1
4 5
7 0
10 5
8 0
0 6
1 10
5 5
6 5

9 7
8 7
8 2
2 6
4 5
7 2
6 7
3 1
8 9
3 5
3 4
1 8

7 1
3 2
3 7
5 2
9 4

Output:

-1
-1
2.5
-1
-1

Obrázok tretieho vstupu:

Input:

5 5 5

0 0
0 4
4 4
4 0
1 1

1 2
2 3
3 4
4 1
4 5

1 1
0 4
3 3
0 2
2 4

Output:

-1
-1
16
-1
-1

Obrázok štvrtého vstupu: