Problema B - A corrida

O Nuno é um grande maratonista olímpico português, dos melhores do mundo! Dentro de momentos, o Nuno vai participar numa maratona muito importante, mas infelizmente está a chover! Graças à chuva, formaram-se vários charcos pela pista, que dificultam a corrida.

A pista de corrida está coberta por N charcos, cada um representado por um retângulo com coordenadas inteiras e positivas, sendo que nenhum charco se interseta (ou seja, qualquer ponto da pista está coberto por no máximo um charco). O Nuno começa a sua corrida num ponto com coordenada y igual a 1 e corre sempre em frente no sentido sul, ou seja, corre todos os pontos com a mesma coordenada x até terminar a prova, passando por todos os charcos que encontra no caminho.

Por exemplo, para uma pista com N = 3 charcos com as seguintes coordenadas (no formato x₁ y₁ x₂ y₂, em que x₁ y₁ são as coordenadas do ponto superior esquerdo e x₂ y₂ do inferior direito):

1 1 2 2
3 2 6 3
2 4 5 6

O Nuno está a pensar em começar a sua corrida na posição 3 1, seguindo sempre para baixo até chegar à posição 3 7. A imagem seguinte ilustra esta situação, sendo que as posições sublinhadas a amarelo ilustram o percurso do Nuno.

Visto que os charcos influenciam muito a corrida do Nuno, é muito importante para ele saber o comprimento total de charcos que ele vai percorrer para uma possível posição inicial. Para o exemplo acima o Nuno percorreu um total de 3 unidades de comprimento de charcos (uma do segundo retângulo e duas do terceiro).

O Nuno tem Q possíveis posições iniciais para começar a sua corrida, mas antes de escolher qual a que prefere, ele precisa de saber para cada uma delas qual o comprimento total de charcos que teria de percorrer se começar daí.

O Problema

Dado um conjunto de N charcos e Q posições iniciais onde o Nuno pode iniciar a sua corrida, determinar para cada posição inicial o comprimento total dos charcos que o Nuno tem de atravessar se iniciar a sua corrida daí.

Input

Na primeira linha vêm dois inteiros, N que representa o número de charcos e Q que representa o número de posições iniciais possíveis.

Seguem-se N linhas, cada uma com 4 inteiros no formato x₁ y₁ x₂ y₂, em que x₁ y₁ são as coordenadas do ponto superior esquerdo e x₂ y₂ do inferior direito, cada um representando o retângulo de um charco.

Seguem-se Q linhas, cada uma um inteiro, a coordenada x de cada posição inicial possível.

Output

O output contém Q inteiros, o comprimento total para cada posição inicial, pela ordem dada no input.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 4 grupos com restrições adicionais diferentes:

Input do Exemplo 1

3 4
1 1 2 2
3 2 6 3
2 4 5 6
2
3
5
6

Output do Exemplo 1

2
3
1
0

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado.

Input do Exemplo 2

7 7
1 1 11 3
13 3 14 5
2 5 12 7
7 15 15 16
5 16 15 17
11 17 11 18
4 18 11 19
18
17
13
6
14
15
2

Output do Exemplo 2

0
0
4
6
2
0
4