Bessie заперта в треугольном лабиринте с $N$ рядами, $1 \le N \le 1,000,000$. Ниже пример трёх рядов.

Ряд $i$ имеет $2*i-1$ треугольников, слева направо $(i,1)$, $(i,2)$ и далее.

Можно перейти в треугольник с общей стороной, обычно таких три. Из $(3,3)$ можно в $(3,2)$, $(3,4)$, $(4,4)$. Каждый переход занимает минуту.

FJ узнал о беде и по iPhone отследил начало её пути к выходу ($Si,Sj$). Его любовь безгранична, он хочет скорейшего возвращения.

По лабиринту размещены $M$ выходов, $1 \le M \le 10,000$, любой позволяет сбежать. После входа в выходной треугольник нужна ещё одна минута для выхода из лабиринта.

Найдите минимальное время $T$ минут и оптимальный выход $(OUTi, OUTj)$. При нескольких выходах за $T$ выбирайте меньший ряд; при равных рядах меньший столбец.

Входные данные

• Строка $1$: целые $N$, $M$ через пробел.

• Строка $2$: целые $Si$, $Sj$ через пробел.

• Строки $3..M+2$: строка $i+2$ содержит два целых через пробел $Ei$, $Ej$, положение треугольника выхода $i$.

Выходные данные

• Строка $1$: целые $OUTi$, $OUTj$ через пробел.

• Строка $2$: одно целое $T$.

Примеры

Входные данные 1

4 2
2 1
3 5
4 4

Выходные данные 1

4 4
4

Автор задачи: Ye Wang, 2009