Bessie está presa num labirinto triangular com $N$ linhas, $1 \le N \le 1,000,000$. Abaixo um com três linhas.

Linha $i$ tem $2*i-1$ triângulos, da esquerda $(i,1)$, $(i,2)$, etc.

Pode passar aos que compartilham lado, geralmente três. De $(3,3)$ a $(3,2)$, $(3,4)$, $(4,4)$. Cada passagem leva um minuto.

FJ sabe que está presa e rastreia seu iPhone para saber o início da busca de saída ($Si,Sj$). Seu amor não tem limites, quer o retorno mais rápido.

Há $M$ saídas dispersas, $1 \le M \le 10,000$, qualquer uma serve. Após entrar no triângulo de saída, basta mais um minuto para sair.

Ache o menor tempo $T$ minutos e saída ótima $(OUTi, OUTj)$. Se várias levam $T$, escolha menor linha; se linhas iguais, menor coluna.

Entrada

• Linha $1$: inteiros $N$, $M$ separados por espaço.

• Linha $2$: inteiros $Si$, $Sj$ separados por espaço.

• Linhas $3..M+2$: linha $i+2$, dois inteiros separados por espaço $Ei$, $Ej$, triângulo de saída $i$.

Saída

• Linha $1$: inteiros $OUTi$, $OUTj$ separados por espaço.

• Linha $2$: um inteiro $T$.

Exemplos

Entrada 1

4 2
2 1
3 5
4 4

Saída 1

4 4
4

Autor do problema: Ye Wang, 2009