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)$로 갈 수 있습니다. 한 이동은 1분입니다.

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