Description

Bessie is trapped in a triangular maze with $N$ rows ($1 \le N \le 1{,}000{,}000$). For example, a maze with $3$ rows is shown below.

The $i$-th row of the maze contains $2i - 1$ triangles. Numbering from the left, the triangles are named $(i, 1)$, $(i, 2)$, and so on.

Bessie can move to any triangles that share an edge with her current triangle (often three neighbors). For example, if she is at $(3, 3)$, she can move to $(3, 2)$, $(3, 4)$, and $(4, 4)$. Each move to a neighboring triangle takes one minute.

Farmer John has learned that Bessie is trapped and, by tracking her iPhone, knows she starts at triangle $(S_i, S_j)$. His love for Bessie knows no bounds, so he wants her back in the minimum possible time.

There are $M$ exits ($1 \le M \le 10{,}000$) located at various triangles in the maze. Entering any exit triangle allows Bessie to escape, and it takes one additional minute after entering an exit triangle to leave the maze.

Find the minimum time in minutes, $T$, required for Bessie to exit the maze, and report the exit she uses, $(\text{OUT}_i, \text{OUT}_j)$. If more than one exit requires only $T$ minutes, output the one with the smallest row. If there is still a tie, output the one with the smaller column.

Input Format

• Line 1: Two space-separated integers: $N$ and $M$.
• Line 2: Two space-separated integers: $S_i$ and $S_j$.
• Lines $3 \ldots M+2$: Line $i+2$ contains two space-separated integers giving the location of exit $i$: $E_i$ and $E_j$.

Output Format

• Line 1: Two space-separated integers: $\text{OUT}_i$ and $\text{OUT}_j$.
• Line 2: A single integer: $T$.

4 2 
2 1 
3 5 
4 4 

4 4 
4 

Hint

Translated by ChatGPT 5