SPOJ Brasil

A robótica causou uma grande revolução nos processos industriais no mundo todo; atualmente, vários tipos de robôs são usados na fabricação de carros, equipamentos eletrônicos e até mesmo utensílios domésticos.

Uma fábrica possui um robô de manutenção, que constantemente precisa ser deslocado entre setores diferentes para executar vários serviços. A movimentação do robô é feita por controle remoto: ele pode andar qualquer distância, mas apenas nas quatro direções cardeais (norte, sul, leste e oeste).

Robôs são feitos de metal, e por isso é ideal que eles evitem contato direto com a água. Assim, em dias chuvosos, é ideal que a trajetória do robô passe por dentro de galpões, debaixo de marquises e toldos, etc. para evitar sua exposição à chuva.

A sua tarefa é escrever um programa que, dadas as informações sobre as áreas cobertas e ponto inicial e final do robô, determine uma trajetória para o robô que minimize a porção do trajeto feita sob chuva.

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 da entrada contém quatro inteiros X_i, Y_i, X_f e Y_f (0 ≤ X_i, Y_i, X_f, Y_f ≤ 10⁶), indicando, respectivamente, a posição atual e a posição final do robô — o robô começa na posição (X_i, Y_i) e deve terminar na posição (X_f , Y_f).

A linha seguinte da entrada contém um único inteiro N (0 ≤ N ≤ 1000), indicando o número de áreas cobertas na fábrica. Cada uma das N linhas seguintes contém quatro inteiros X₁, Y₁, X₂ e Y₂ (0 ≤ X₁ < X₂ ≤ 10⁶, 0 ≤ Y₁ < Y₂ ≤ 10⁶), indicando uma região coberta.

Uma região coberta é um retângulo de lados paralelos aos eixos tal que (X₁, Y₁) e (X₂, Y₂) são vértices opostos do retângulo. Duas áreas cobertas podem ter regiões comuns. O robô pode entrar e sair de uma área coberta por qualquer ponto de seu perímetro, e pode trafegar livremente dentro da área coberta.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo um número inteiro indicando a menor distância que o robô precisa percorrer sob chuva.

Exemplos

Entrada:
0 0 4 3
0

Saída:
7

Entrada:
2 5 5 0
1
0 0 1 5

Saída:
5

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

Saída:
5