O Miguel prepara-se para mais uma viagem de avião. Visto que é alguém que viaja muito, o Miguel sabe exatamente os aviões que se encontram a voar neste preciso momento, assim como as suas coordenadas. Os aviões movem-se numa grelha bidimensional infinita e ocupam exatamente uma célula da grelha. Cada avião é identificado com uma coordenada X e uma coordenada Y e move-se pelo plano. Por exemplo, se houver um avião na posição (2, 3) e um na posição (1, 2) a grelha será algo como:
.... A... .A.. ....
Onde os . representam espaço vazio e os A aviões, sendo que a
célula no canto inferior esquerdo representa a posição (1, 1). Adicionalmente, existem
nuvens que ocupam também uma célula da grelha cada uma. Assim como os
aviões, cada nuvem é identificada por uma coordenada X e uma
coordenada Y, mas mantém-se sempre na mesma posição. Por exemplo, se
além dos aviões do exemplo anterior tivermos uma nuvem na posição
(2, 2) a grelha será algo como:
.... AN.. .A.. ....
Onde o N representa a nuvem.
O Miguel quer estudar o movimento dos aviões, para tal ele sabe que inicialmente todos os aviões têm um sentido de movimento e movem-se à mesma velocidade de uma célula por unidade de tempo, sendo que o Miguel apenas está interessado nas primeira K unidades de tempo. Inicialmente, os aviões movem-se no sentido este (ou seja, no sentido positivo no eixo dos X). O movimento dos aviões é independente entre si (um avião não afeta o movimento de ninguém), mas as nuvens podem afetar o movimento dos aviões. Se por se mover para uma célula, um avião colidir com uma nuvem (ocupar a mesma posição), em vez de se mover o avião faz uma viragem à direita nessa unidade de tempo, ou seja, se se movia no sentido este passará a mover-se no sentido sul (sentido negativo dos Y), se se movia no sentido sul passará a mover-se no sentido oeste (sentido negativo dos X), se se movia no sentido oeste passará a mover-se no sentido norte (sentido positivo dos Y) e finalmente se se movia no sentido norte passará a mover-se no sentido este.
A título de exemplo, vamos ver o que acontece com o exemplo anterior após uma unidade de tempo:
.... AN.. ..A. ....
O primeiro avião iria colidir com a nuvem, por isso virou à direita e movimentar-se-à agora para o sentido sul. O segundo a avião moveu-se uma unidade para a direita. Após mais uma unidade de tempo a grelha ficará da seguinte forma:
.... .N.. A..A ....
Como foi dito, o movimento dos aviões é independente, por isso pode acontecer que estejam dois aviões na mesma posição. O Miguel quer contar quantos pares distintos de aviões se encontram na mesma posição em algum momento do seu movimento durante as primeiras K unidades de tempo. Nota que pares distintos implica que se dois aviões se cruzarem várias vezes, só devem contar como um único par para a resposta. Consegues ajudar o Miguel?
Dado o número de aviões N e as suas coordenadas, o número de nuvens M e as suas coordenadas e um número de unidades de tempo K, determinar o número de pares distintos de aviões que se cruzam.
A primeira linha contém três inteiros N, M e K, o número de aviões, o número de nuvens e o números de unidades de tempo, respetivamente.
As N linhas seguinte têm cada uma 2 inteiros, as coordenadas X e Y por esta ordem, que definem a posição de cada avião.
As M linhas seguinte têm cada uma 2 inteiros, as coordenadas X e Y por esta ordem, que definem a posição de cada nuvem.
Uma linha com o número pares de aviões que se cruzam.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
| 1 ≤ N ≤ 100 | Número de aviões | |
| 1 ≤ M ≤ 100 | Número de nuvens | |
| 1 ≤ K ≤ 100 | Unidades de tempo | |
| 1 ≤ Xi, Yi ≤ 100 | Coordenadas iniciais |
2 1 4 2 3 1 2 2 2
0
Este exemplo corresponde ao do enunciado.
5 10 15 4 3 4 2 3 3 3 2 3 4 4 4 5 2 1 1 5 4 5 3 3 5 1 3 2 1 2 2 4 5
3
4 8 10 2 2 2 3 3 2 3 3 1 2 1 3 3 1 2 1 4 2 4 3 3 4 2 4
5