Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LASER08 - Tratamento a laser

Um novo tratamento a laser está sendo pesquisado, para eliminar as bactérias causadoras de uma doença de pele que tem acometido muitas pessoas ultimamente. Essa doença, denominada Erictea Demasiana, é causada por uma bactéria de forma retilínea, e acomete pessoas que deixam de tomar sol por muito tempo. As bactérias instalam-se em colônias na derme, abaixo da epiderme, e causam uma coceira insuportável no local infectado.

O novo tratamento utiliza um laser de hélio-neônio que destrói completamente qualquer pedaço de bactéria que o laser atinja. No entanto, o laser pode danificar a derme, e por isso seu uso deve ser feito com parcimônia.

Para comprovar a eficácia do tratamento uma pesquisa foi encomendada. Para a pesquisa uma fina lâmina de pele contaminada é fotografada com um microscópio eletrônico de forma a retratar a infestação. Pela fotografia pode-se identificar perfeitamente as bactérias instaladas na lâmina, como ilustra a figura abaixo.

Uma peculiaridade interessante da Eritea Demasiana, que pode ser verificada na figura, é que ela nunca se posiciona verticalmente em relação à epiderme, de forma que o feixe de laser nunca é paralelo a uma bactéria.

Um feixe de laser é então aplicado perpendicularmente à lâmina, como ilustrado na figura. O feixe destrói todos os segmentos de bactéria que atinge. Por exemplo, na figura acima, após a aplicação do laser há 11 bactérias ou segmentos de bactéria remanescentes.

Sua tarefa é escrever um programa que responda a consultas para determinar, para diferentes feixes de laser, quantas bactérias ou segmentos de bactéria ainda permanecem na amostra.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha do conjunto de testes contém dois números inteiros N e C que indicam respectivamente o número de bactérias presentes na amostra (1 ≤ N ≤ 105) e o número de consultas que serão realizadas (1 ≤ C ≤ 105). Cada uma das N linhas seguintes contém quatro números inteiros X1, Y1, X2, Y2 representando os dois extremos de uma bactéria, sendo (X1, Y1) as coordenadas de um extremo e (X2, Y2) as coordenadas do outro extremo (−109 ≤ X1, Y1, X2, Y2 ≤ 109 e X1 ≠ X2).

Cada uma das C linhas seguintes representa uma consulta, e contém dois números inteiros Xi e Xf que indicam respectivamente a coordenada X inicial e final do feixe de laser (−109 ≤ Xi < Xf ≤ 109).

As consultas não são cumulativas: o resultado da consulta independe de consultas anteriores (em outras palavras, as consultas são sempre relativas às bactérias presentes inicialmente na amostra).

Saída

Seu programa deve imprimir, na saída padrão, uma linha para cada uma das C consultas da entrada. Cada linha deve conter um inteiro, o número total de bactérias e segmentos de bactérias remanescentes na amostra após a aplicação do laser.

Exemplo

Entrada:
1 4
1 0 4 0
0 2
3 5
2 3
0 5

Saída:
1
1
2
0

Entrada:
2 6
2 0 4 0
2 0 4 0
0 1
1 2
2 3
3 4
4 5
5 6

Saída:
2
2
2
2
2
2

Entrada:
2 3
0 0 3 5
3 5 0 2
0 3
1 2
2 7

Saída:
0
4
2


Adicionado por:Wanderley Guimarăes
Data:2012-07-18
Tempo limite:0.565s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Seletiva IOI 2008

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.