Molduras sobrepostas
Há pontos distintos no plano. Cada ponto deve ser pintado de vermelho ou de azul, independentemente dos demais.
Para cada pintura, construa a menor caixa retangular com lados paralelos aos eixos que contém todos os pontos vermelhos. Construa também a caixa correspondente aos pontos azuis. A contribuição da pintura é a área da interseção das duas caixas.
Se uma das cores não aparece, a contribuição é zero. Caixas degeneradas, com largura ou altura zero, também produzem contribuição zero. Tocar apenas pela borda não produz área positiva.
Calcule a soma das contribuições de todas as pinturas, módulo . As cores são distintas: trocar todas as cores produz outra pintura.
Input
A primeira linha contém um inteiro ().
Cada uma das próximas linhas contém dois inteiros e (), as coordenadas de um ponto.
Output
Imprima a soma das áreas das interseções, módulo .
Samples
Sample 1
Input
4 0 0 0 2 3 0 3 2
Output
12
Apenas as duas pinturas nas quais cada diagonal tem uma cor contribuem com área positiva. Em cada uma delas, as duas caixas coincidem e têm área .
Sample 2
Input
3 0 0 1 1 2 2
Output
0
Se ambas as cores aparecem, uma delas aparece em apenas um ponto; sua caixa tem área zero.