Deserto Kalimari

Bowser e seus lacaios estavam havia dias e dias sem receber visitas em seu castelo, então decidiram sair de férias para o Deserto Kalimari para competir em corridas de carros. Como era de se esperar em um deserto, não tinham onde competir, então decidiram levar eles mesmos os materiais necessários para construir sua própria pista de corrida.

Infelizmente, minutos antes de começarem a montar a pista, perceberam que as caixas com os materiais não estavam lá: Bowser Jr. as havia esquecido em um dos planaltos mais ventosos da região!

O topo do planalto pode ser representado como um polígono convexo $P$ de $n$ vértices, e cada caixa pode ser representada como um ponto dentro de $P$ ou sobre sua fronteira. Por sorte, na estação meteorológica do deserto sabem exatamente como o vento vai soprar.

O vento soprará $t$ vezes. A $i$-ésima rajada é representada por um vetor $w_i \in \mathbb{R}^2$. Se uma caixa está na posição $x$ imediatamente antes da $i$-ésima rajada, ela será deslocada para $x + w_i$.

Se, depois de alguma rajada, uma caixa ficar estritamente fora de $P$, ela cairá do planalto e será perdida. As caixas que caírem deixarão de ser afetadas pelas rajadas posteriores.

Bowser e seus lacaios querem saber se vale a pena voltar para buscar as caixas ou se seria melhor retornar ao castelo para buscar mais materiais (e garantir que nenhum Mario tenha entrado sem permissão).

Determine quantas caixas permanecem sobre o planalto depois das $t$ rajadas de vento.

Entrada

A primeira linha da entrada contém $3$ inteiros positivos $n, q, t$, separados por espaços: $n$, o número de vértices do polígono; $q$, o número de caixas; e $t$, o número de rajadas de vento. $(3 \leq n \leq 10^5, 1 \leq q \leq 10^5, 1 \leq t \leq 10^5)$

As $n$ linhas seguintes contêm $2$ inteiros $x_i, y_i$, separados por espaços: as coordenadas do $i$-ésimo vértice do polígono $P$. Os vértices são dados em ordem anti-horária. $(-10^9 \leq x_i, y_i \leq 10^9)$

As $q$ linhas seguintes contêm $2$ inteiros $x_i, y_i$, separados por espaços: as coordenadas da $i$-ésima caixa. Garante-se que cada caixa está dentro de $P$ ou sobre sua fronteira. $(-10^9 \leq x_i, y_i \leq 10^9)$

As $t$ linhas seguintes contêm $2$ inteiros $a_i, b_i$, separados por espaços, que representam o vetor $w_i = (a_i, b_i)$ da $i$-ésima rajada de vento. $(-10^9 \leq a_i, b_i \leq 10^9)$

Garante-se que $P$ não contém três pontos colineares. Além disso, para qualquer caixa, deslocar sua posição inicial por uma distância de no máximo $10^{-4}$ não altera a resposta.

Saída

Imprima um único inteiro: o número de caixas que permanecem sobre o planalto depois das $t$ rajadas de vento.

Notas

No exemplo, o planalto é o quadrado de vértices $(0, 0)$, $(5, 0)$, $(5, 5)$ e $(0, 5)$. O vento sopra primeiro para a direita, $w_1 = (2, 0)$, e depois para cima, $w_2 = (0, 2)$.

• A caixa em $(1, 1)$ passa por $(3, 1)$ e termina em $(3, 3)$: permanece sobre o planalto.

• A caixa em $(4, 1)$ é levada a $(6, 1)$ pela primeira rajada, fica fora de $P$ e cai.

• A caixa em $(2, 4)$ passa por $(4, 4)$, mas a segunda rajada a leva a $(4, 6)$ e ela cai.

• A caixa em $(2, 2)$ passa por $(4, 2)$ e termina em $(4, 4)$: permanece sobre o planalto.

Portanto, restam $2$ caixas sobre o planalto.

4 4 2
0 0
5 0
5 5
0 5
1 1
4 1
2 4
2 2
2 0
0 2

2