Problema A - Escadas ou Elevador

A sede das Olimpíadas Nacionais de Informática é um prédio muito alto com exatamente N andares, numerados de 1 a N do mais baixo para o mais alto. Para nos movimentarmos entre andares temos a opção de usar um conjunto de escadas e elevadores. Entre cada par de andares consecutivos existem escadas que demoram exatamente 1 unidade de tempo a serem percorridas (em qualquer sentido).

Há ainda um conjunto de K elevadores. O i-ésimo elevador pode ser usado entre os andares a_i e b_i, ou seja, podemos entrar neste elevador num andar qualquer entre a_i e b_i e podemos sair em qualquer andar entre a_i e b_i. Usar um elevador demora exatamente 1 unidade de tempo, independentemente de quantos andares percorrermos. Podemos ainda considerar que mudar de elevador ou trocar de elevador para escadas é instantâneo, ou seja demora 0 unidades de tempo.

Hoje sabe-se que Q pessoas vão precisar de se movimentar entre andares. A i-ésima pessoa encontra-se no andar c_i e quer ir para o andar d_i e quer fazê-lo no mínimo tempo possível. Determina para cada pessoa o mínimo tempo possível para se deslocar entre cada um dos andares.

Exemplo

Se N = 10, K = 2, Q = 3 e tivermos os seguintes elevadores:

• a₁ = 2, b₁ = 5
• a₂ = 4, b₂ = 9

Ou seja, o primeiro elevador desloca-se entre os andares 2 e 5 e o segundo elevador entre os andares 4 e 9, como ilustra a figura seguinte:

Então se tivermos os seguintes pares de andares:

• c₁ = 1, d₁ = 2
• c₂ = 5, d₂ = 3
• c₃ = 1, d₃ = 10

Então os tempos mínimos para cada par são os seguintes:

• 1, o que corresponde a usar as escadas do andar 1 para o andar 2.
• 1, o que corresponde a usar o primeiro elevador do andar 3 ao andar 5.
• 4, o que corresponde a usar as escadas do andar 1 para o andar 2, seguido do primeiro elevador do andar 2 ao andar 5, seguido do segundo elevador do andar 5 ao andar 9 e finalmente das escadas do andar 9 ao andar 10.

Restrições:

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

Os casos de teste desta parte do problema estão organizados em 5 grupos com restrições adicionais diferentes:

Input

A primeira linha contém três inteiros separados por espaços, primeiro N, representando o número de andares, seguido de K o número de elevadores, seguido de Q o número de pessoas.

Seguem-se K linhas, cada uma contendo dois inteiros separados por espaços, a i-ésima contendo a_i e b_i, representando os andares entre os quais o i-ésimo elevador se consegue movimentar.

Seguem-se Q linhas, cada uma contendo dois inteiros separados por espaços, a i-ésima contendo c_i e d_i, representando os andares entre os quais a i-ésima pessoa se quer movimentar.

É garantido que todos os a_i, b_i, c_i e d_i são inteiros entre 1 e N.

Output

O output deve conter Q linhas, cada uma com um inteiro onde a i-ésima deve conter o mínimo tempo possível para a i-ésima pessoa se deslocar entre os seus andares.

Input do Exemplo 1

10 2 3
2 5
4 9
1 2
5 3
1 10

Output do Exemplo 1

1
1
4

Explicação do Exemplo 1

Este exemplo corresponde ao exemplo mencionado no enunciado.

Input do Exemplo 2

13 4 5
1 4
6 2
9 12
13 13
1 13
2 7
10 1
5 6
8 8

Output do Exemplo 2

7
2
6
1
0