Robo marciano

Uma empresa de turismo aeroespacial está se preparando para a exploração comercial de Marte. Ela implantou uma base de operações no planeta, onde conduz experimentos que visam garantir a segurança de futuros turistas.

A base em Marte é composta por um conjunto de áreas retangulares cobertas por um teto protetor contra a radiação solar. As áreas retangulares têm lados paralelos aos eixos Norte-Sul e Leste-Oeste. Vários robôs, controlados por comandos enviados desde o Centro de Operações da empresa, na Terra, deslocam-se constantemente pela base para acessar materiais e equipamentos.

Os robôs podem deslocar-se apenas nas quatro direções cardeais (norte, sul, leste e oeste), mas podem transitar tanto em áreas cobertas como não cobertas. Em particular, um robô pode entrar e sair de uma área coberta por qualquer ponto da borda dessa área. Para preservar a vida útil dos robôs, é importante que eles se mantenham o máximo possível protegidos da intensa radiação solar, ou seja, que eles transitem preferencialmente nas áreas cobertas da base.

Dadas as descrições das áreas cobertas, a posição atual de um robô e a posição para a qual este robô deve se deslocar, sua tarefa é determinar a menor distância que o robô deve percorrer fora das áreas cobertas para chegar à posição de destino.

Entrada

A primeira linha da entrada contém quatro inteiros X_i, Y_i, X_f e Y_f indicando, respectivamente, a posição inicial do robô, (X_i, Y_i) e a posição final do robô, (X_f,Y_f).

A segunda linha contém um único inteiro N, indicando o número de áreas cobertas. Cada uma das N linhas seguintes contém quatro inteiros X₁, Y₁, X₂ e Y₂ indicando uma região retangular coberta, tal que (X₁, Y₁) e (X₂,Y₂) são vértices opostos do retângulo de lados paralelos aos eixos. Duas áreas cobertas podem ter regiões comuns.

Saída

Restrições

• 0 ≤ N ≤ 1000
• 0 ≤ X_i, Y_i, X_f , Y_f ≤ 10⁶
• 0 ≤ X₁ ≤ X₂ ≤ 10⁶ e 0 ≤ Y₁ ≤ Y₂ ≤ 10⁶

Informações sobre a pontuação

• Para um conjunto de casos de testes valendo 30 pontos, X₁,Y₁,X₂,Y₂,X_i,X_f,Y_i,Y_f ≤ 10 e N ≤ 5.
• Para um conjunto de casos de testes valendo outros 50 pontos, X₁,Y₁,X₂,Y₂,X_i,X_f,Y_i,Y_f ≤ 1000 e N ≤ 100.

Exemplos

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

2
	

2 5 5 0
1
0 0 1 5

5
	

4 5 5 0
2
0 0 1 5
0 0 3 2

5