Problema B - Obras na Via Férrea

A nova via férrea para os comboios de alta velocidade está quase pronta e liga as duas principais cidades da Algoritmolândia. A via pode ser vista como um segmento de recta de tamanho N com posições entre 0 e N-1. A figura seguinte ilustra uma via férrea para N=10.

Ainda estão a decorrer algumas obras de acabamento que podem ser descritas como um intervalo de entre duas posições [A,B] (inclusive). Por exemplo, a seguinte figura ilustra a vermelho onde estariam as obras num intervalo [1,3] e a verde umas obras num intervalo [8,9]:

O primeiro-ministro da Algoritmolândia está desejoso de mostrar esta nova e maravilhosa via férrea aos seus convidados de honra, mas não quer esperar pelo final das obras. Para poder mostrar quão rápidos os comboios são, ele pretende selecionar o maior segmento livre (posições contínuas na linha sem nenhuma obra) para uma breve demonstração. Por exemplo, se num dado momento as obras são as que estavam descritas na figura anterior, o maior segmento teria tamanho 4, entre as posições 4 e 7 (inclusive):

Tudo isto seria mais simples se fosse ignorado o factor temporal, mas o primeiro ministro não se pode dar a esse luxo. Em particular, cada obra, para além do intervalo espacial [A,B], é também caracterizada por um dado intervalo temporal [C,D] (inclusive), significando que começa na hora C e termina na hora D. Nota que não podem haver duas obras no mesmo ponto à mesma hora, mas podem haver duas obras no mesmo ponto em horas distintas.

O primeiro-ministro quer dedicar uma hora a mostrar a sua linha e para isso tem disponíveis uma série de intervalos temporais [E,F] para mostrar a linha aos convidados, e quer saber, para cada um desses intervalos, qual o maior segmento que está completamente livre de obras em pelo menos uma hora do intervalo. Tens de ajudar o primeiro-ministro!

O Problema

Dado o tamanho N de uma via férrea, um conjunto de K obras, cada uma decorrendo no intervalo espacial [A_i,B_i] e no intervalo temporal [C_i,D_i] e um conjunto de P intervalos de tempo disponíveis [E_i,F_i], a tua tarefa é descobrir, para cada um dos P intervalos, qual o maior segmento completamente livre, durante pelo menos uma hora, entre as horas E_i e F_i.

Input

A primeira linha contém três inteiros: N (tamanho da linha), K (número de obras) e P (número de intervalos disponíveis), separados por um único espaço.

As K linhas seguintes descrevem as obras, cada uma no formato A_i B_i C_i D_i, indicando que há uma obra nas posições [A_i,B_i] a decorrer no intervalo de tempo entre as horas C_i e D_i (inclusive). As obras não vêm por nenhuma ordem em específico e podem existir interseções ao nível do tempo, mas não pode haver duas obras ativas no mesmo ponto da linha ao mesmo tempo (mas pode haver duas obras no mesmo ponto em duas horas distintas).

As P linhas seguintes descrevem os intervalos de tempo disponíveis para a demonstração, cada uma no formato E_i F_i, indicando que o primeiro-ministro quer mostrar a linha numa hora entre E_i e F_i, inclusive. Estes intervalos pode vir por qualquer ordem.

Output

O output é constituído por P linhas, cada um com um único inteiro R_i, a resposta para a pergunta i, ou seja, qual o maior segmento que está livre (sem nenhuma obra) entre as horas E_i e F_i, durante pelos menos uma hora.

Restrições

São garantidos os seguintes limites em todos os casos de teste:

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 35% dos pontos, acontece sempre que N≤20, K≤20 e P≤20, B_i≤20; F_i≤20.

Para um conjunto de casos de teste valendo 70% dos pontos, acontece sempre que K≤1 000 e P≤1 000.

Exemplo de Input 1

10 2 4
1 3 2 5
8 9 3 7
2 4
3 5
4 6
4 10

Exemplo de Output 1

6
4
8
10

Explicação do Input/Output 1

Temos uma obra a decorrer nas posições [1,3] entre as horas 2 e 5 e uma obra nas posições [8,9] entre as horas 3 e 7. A primeira pergunta pede o maior segmento livre entre as horas 2 e 4. Nesse intervalo o maior segmento livre tem tamanho 6 (entre as posições 4 e 9) e ocorre na hora 2, onde a primeira obra está decorrer, mas a segunda ainda não começou.

A segunda pergunta pede o maior segmento livre entre as horas 3 e 5 e nesse intervalo ambas as obras estão sempre ativas, pelo que a resposta é 4 (o segmento entre 4 e 7).

A terceira pergunta indica as horas 4 a 6 e nesse intervalo na hora 6 apenas segunda obra está ativa, pelo que o maior segmento tem tamanho 8 (entre as posições 0 e 7).

Finalmente, a quarta pergunta indica as horas 4 a 10. A partir da hora 8 não há nenhuma obra ativa, logo o maior segmento tem tamanho 10 (entre as posições 0 e 9).

Exemplo de Input 2

6 3 2
0 2 2 10
3 5 4 8
0 5 20 30
2 4
22 25

Exemplo de Output 2

3
0