Cow Rescue

Bessie is trapped in a triangular maze with $N$ rows ($1 \le N \le 1{,}000{,}000$). Row $i$ of the maze contains $2i-1$ triangles. Numbering from the left, the triangles in row $i$ are named $(i,1), (i,2), \dots, (i, 2i-1)$.

Each triangle shares an edge with (usually three) neighboring triangles, and Bessie can move to any triangle that shares an edge with her current one. For example, from triangle $(3,3)$ she can move to $(3,2)$, $(3,4)$, and $(4,4)$. Each move takes exactly $1$ minute.

(Triangles in odd columns point upward and those in even columns point downward. An upward triangle $(i,j)$ is adjacent to $(i,j-1)$, $(i,j+1)$, and $(i+1,j+1)$; a downward triangle $(i,j)$ is adjacent to $(i,j-1)$, $(i,j+1)$, and $(i-1,j-1)$. Neighbors outside the maze do not exist.)

Bessie starts at triangle $(S_i, S_j)$. The maze has $M$ exit triangles ($1 \le M \le 10{,}000$). Reaching any exit lets Bessie escape: once she enters an exit triangle, she leaves the maze after one more minute.

Let $T$ be the minimum number of minutes Bessie needs to escape. Among all exits that let her escape in exactly $T$ minutes, report the one she should use: choose the exit in the smallest row, and if there is still a tie, the exit with the smallest column.

• Line 1: two space-separated integers $N$ and $M$.
• Line 2: two space-separated integers $S_i$ and $S_j$ — Bessie's starting triangle.
• Lines 3 through $M+2$: line $i+2$ contains two space-separated integers $E_i$ and $E_j$, the location of exit $i$.

• Line 1: two space-separated integers $OUT_i$ and $OUT_j$ — the chosen exit location.
• Line 2: a single integer $T$ — the minimum escape time in minutes.