Xiao T ha planificado el área de exhibición como una cuadrícula bidimensional de tamaño $n \times n$. El perímetro exterior de la cuadrícula está rodeado por una pared de exhibición; es decir, todas las celdas cuyas coordenadas $x$ o $y$ sean iguales a $0$ o $n+1$ son celdas de pared. Además, hay $m$ celdas de pared dispersas dentro del área de exhibición, donde la $i$-ésima celda ($1 \le i \le m$) tiene coordenadas $(x_i, y_i)$. Se garantiza que todas las celdas de pared están conectadas mediante adyacencia lateral (conectividad 4).

Tras realizar pruebas de diseño en el terreno, Xiao T ha determinado las reglas de consumo de tiempo para moverse entre las celdas. Específicamente, existen dos formas de moverse entre celdas:

• Moverse una celda en dirección vertical u horizontal, es decir, desde $(x, y)$ a cualquiera de las celdas adyacentes $(x-1, y), (x+1, y), (x, y-1), (x, y+1)$, consume $2$ unidades de tiempo.
• Moverse una celda en dirección diagonal, es decir, desde $(x, y)$ a cualquiera de las celdas diagonales $(x-1, y-1), (x-1, y+1), (x+1, y-1), (x+1, y+1)$, consume $3$ unidades de tiempo.

Por supuesto, la posición de destino no puede ser una celda de pared. Nota: al moverse en dirección diagonal, es posible pasar directamente a través del espacio entre dos celdas de pared diagonales. Por ejemplo, incluso si $(x, y+1)$ y $(x+1, y)$ son ambas celdas de pared, todavía es posible consumir $3$ unidades de tiempo para moverse directamente desde $(x, y)$ a $(x+1, y+1)$ en diagonal.

Xiao S ha colocado un total de $q$ tesoros en el área de exhibición. Para el $i$-ésimo tesoro ($1 \le i \le q$), ella anuncia su posición $(tx_i, ty_i)$, mientras que tu posición al momento del anuncio es $(sx_i, sy_i)$. Para obtener cada tesoro lo más rápido posible, debes calcular el tiempo mínimo necesario para moverte desde tu posición actual hasta la posición del tesoro.

Entrada

La primera línea de la entrada contiene tres enteros positivos $n, m, q$ ($1 \le n \le 10^5, 1 \le m, q \le 3 \times 10^5$).

Las siguientes $m$ líneas contienen cada una dos enteros positivos $x_i, y_i$ ($1 \le x_i, y_i \le n$), que representan las coordenadas de la $i$-ésima celda de pared. Se garantiza que todas las coordenadas $(x_i, y_i)$ son distintas entre sí.

Las siguientes $q$ líneas contienen cada una cuatro enteros positivos $sx_i, sy_i, tx_i, ty_i$ ($1 \le sx_i, sy_i, tx_i, ty_i \le n$), que representan tu posición y la posición del tesoro al momento del anuncio del $i$-ésimo tesoro. Se garantiza que ni $(sx_i, sy_i)$ ni $(tx_i, ty_i)$ son celdas de pared.

Salida

Imprime $q$ líneas, cada una con un entero que representa la respuesta. En particular, si no es posible llegar a la posición del tesoro, imprime $-1$.

Ejemplos

Entrada 1

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

Salida 1

2
16
11
10
11

Nota 1

Para el segundo tesoro, puedes moverte siguiendo la ruta: $(1, 1) \to (1, 2) \to (2, 3) \to (3, 4) \to (4, 3) \to (4, 2) \to (3, 1)$, con un tiempo total de $2 + 3 + 3 + 3 + 2 + 3 = 16$.