SPOJ Brasil

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 ≤ 10⁵) e o número de consultas que serão realizadas (1 ≤ C ≤ 10⁵). Cada uma das N linhas seguintes contém quatro números inteiros X₁, Y₁, X₂, Y₂ representando os dois extremos de uma bactéria, sendo (X₁, Y₁) as coordenadas de um extremo e (X₂, Y₂) as coordenadas do outro extremo (−10⁹ ≤ X₁, Y₁, X₂, Y₂ ≤ 10⁹ e X₁ ≠ X₂).

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

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