Devido à dificuldade dos problemas, alguns participantes decidem fugir desta competição. Porém, para impedir que isso aconteça, os autores MALVADOS construíram um labirinto à saída do estádio. O labirinto é uma grelha de $n \times m$, onde se encontram a entrada, a saída e $k$ buracos negros. Os participantes que pisarem acidentalmente um buraco negro cairão nele e nunca mais conseguirão escapar da competição.

Para piorar, os autores também podem alterar as coordenadas da entrada e da saída. Você, um pobre participante que parte da entrada e pretende chegar à saída sem pisar nenhum buraco negro, só pode deslocar-se para uma das quatro células adjacentes a cada passo. Quer saber, após cada alteração das coordenadas da entrada e da saída pelos autores, qual é o número mínimo de passos necessário para chegar à saída a partir da entrada.

Entrada

A primeira linha da entrada contém quatro inteiros $n, m, k, q$ ($1 \le n, m \le 200\,000$, $nm \le 200\,000$, $0 \le k \le 42$, $1 \le q \le 100\,000$), que indicam, respetivamente, o número de linhas, o número de colunas, o número de buracos negros no labirinto e o número de consultas.

As $k$ linhas seguintes descrevem os buracos negros. Cada uma dessas linhas contém dois inteiros $x, y$ ($1 \le x \le n$, $1 \le y \le m$), que indicam as coordenadas de um buraco negro. Não há dois buracos negros na mesma posição.

As últimas $q$ linhas descrevem as consultas. Cada uma das $q$ linhas contém quatro inteiros $x_s, y_s, x_t, y_t$ ($1 \le x_s, x_t \le n$, $1 \le y_s, y_t \le m$), em que $(x_s, y_s)$ são as coordenadas da entrada e $(x_t, y_t)$ são as da saída.

Saída

Para cada consulta, imprima um número numa linha, indicando o número mínimo de passos necessário para chegar à saída a partir da entrada. Se for impossível chegar à saída, imprima $-1$. Deve considerar-se impossível quando a entrada ou a saída coincidir com um buraco negro.

Exemplos

Entrada 1

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

Saída 1

6
0
-1
4
-1
5
-1

Entrada 2

2 3 2 1
1 2
2 1
1 1 2 3

Saída 2

-1

Nota

As figuras do labirinto e da primeira consulta do primeiro exemplo são apresentadas abaixo.

(a) O labirinto. (b) Um possível caminho mínimo para a primeira consulta.

entrada; saída; buraco negro; um passo.

Figura 1: Figuras dos dados de exemplo.