소 구출

베시가 $N$개의 행으로 이루어진 삼각형 미로에 갇혔다 ($1 \le N \le 1{,}000{,}000$). 미로의 $i$번째 행에는 $2i-1$개의 삼각형이 있다. 왼쪽부터 번호를 매겨 $i$번째 행의 삼각형을 $(i,1), (i,2), \dots, (i, 2i-1)$로 부른다.

각 삼각형은 변을 공유하는 (보통 세 개의) 이웃 삼각형을 가지며, 베시는 현재 삼각형과 변을 공유하는 삼각형으로 이동할 수 있다. 예를 들어 삼각형 $(3,3)$에서는 $(3,2)$, $(3,4)$, $(4,4)$로 이동할 수 있다. 한 번 이동하는 데 정확히 $1$분이 걸린다.

(열 번호가 홀수인 삼각형은 위를 향하고, 짝수인 삼각형은 아래를 향한다. 위를 향하는 삼각형 $(i,j)$는 $(i,j-1)$, $(i,j+1)$, $(i+1,j+1)$과 인접하고, 아래를 향하는 삼각형 $(i,j)$는 $(i,j-1)$, $(i,j+1)$, $(i-1,j-1)$과 인접한다. 미로 밖의 이웃은 존재하지 않는다.)

베시는 삼각형 $(S_i, S_j)$에서 출발한다. 미로에는 $M$개의 출구 삼각형이 있다 ($1 \le M \le 10{,}000$). 이 중 어느 하나에 도달하면 탈출할 수 있으며, 출구 삼각형에 들어간 뒤 $1$분이 더 지나면 미로를 빠져나간다.

베시가 탈출하는 데 필요한 최소 시간을 $T$분이라고 하자. 정확히 $T$분 만에 탈출할 수 있는 출구가 여러 개라면, 베시가 사용해야 할 출구 하나를 출력한다. 이때 행 번호가 가장 작은 출구를 고르고, 그래도 같다면 열 번호가 가장 작은 출구를 고른다.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$
• 둘째 줄: 공백으로 구분된 두 정수 $S_i$와 $S_j$ (베시의 시작 삼각형)
• 셋째 줄부터 $M+2$번째 줄까지: $i+2$번째 줄에는 출구 $i$의 위치를 나타내는 두 정수 $E_i$와 $E_j$가 주어진다

• 첫째 줄: 선택한 출구의 위치를 나타내는 두 정수 $OUT_i$와 $OUT_j$
• 둘째 줄: 최소 탈출 시간(분)을 나타내는 정수 $T$