Triangular Maze Escape

Bessie is trapped in a triangular maze with N rows. In the ith row there are 2i − 1 triangles, numbered from left to right as (i, 1), (i, 2), …, (i, 2i−1).

Bessie can move from her current triangle to any triangle that shares an edge with it. In this maze the moves are as follows:

• If she is at triangle (i, j), she can always move horizontally to (i, j − 1) (if it exists) and (i, j + 1) (if it exists).
• The maze is composed of alternating upward and downward pointing triangles. In fact, a triangle is upward if j is odd and downward if j is even.
• Vertical moves:
  • If Bessie is in an upward triangle (i.e. j odd) at (i, j) and i < N, she may move downward (to the next row) to (i+1, j+1).
  • If Bessie is in a downward triangle (i.e. j even) at (i, j) and i > 1, she may move upward (to the previous row) to (i−1, j−1).

Bessie starts at triangle (S_i, S_j). There are M exit triangles scattered throughout the maze; stepping into any exit triangle means that, in one more minute, she escapes the maze.

Your task is to determine the minimum time T (in minutes) required for Bessie to escape (including the extra minute to exit) and to report the exit triangle (OUT_i, OUT_j) she should use. If multiple exits yield the same minimum time, choose the one with the smallest row number; if there is still a tie, choose the one with the smallest column number.

Note on movements: Each move (horizontal or vertical) takes 1 minute. The extra minute to exit is added only once after reaching an exit triangle.

Mathematical explanation (in \(\LaTeX\)):

Define a coordinate transformation by setting \(x=j-i\). Then an upward triangle (when \(j\) is odd) can move vertically (downward) by: \((i,x) \to (i+1,x)\), and a downward triangle (when \(j\) is even) can move vertically (upward) by: \((i,x) \to (i-1,x)\). Horizontal moves are: \((i,x) \to (i,x\pm1)\).

If Bessie starts at \((S_i,S_j)\), let \(a=S_j-S_i\). For an exit at \((T_i,T_j)\), let \(b=T_j-T_i\). Notice that horizontal moves do not change the \(x\) coordinate. Thus Bessie must cover a horizontal difference of \(|b-a|\) using horizontal moves, but vertical moves are only possible when the triangle has the correct orientation. In particular, when moving downward (i.e. when \(T_i>S_i\)), a vertical move is allowed only if the current triangle is upward (\(j\) odd), and when moving upward (\(T_i<S_i\)) a vertical move is allowed only if the triangle is downward (\(j\) even). Vertical moves do not change \(x\). A careful interleaving of horizontal moves (which may be forced to flip the orientation) and vertical moves yields a total move cost of:

[ \text{cost} = \begin{cases} |T_j - S_j|, & \text{if } T_i = S_i,\ r + p + \delta, & \text{if } T_i \neq S_i, \end{cases} ]

where \(r = |T_i - S_i|\), \(p\) depends on whether the starting orientation matches the needed orientation for vertical moves, and \(\delta\) is the extra horizontal cost required after using all possible parity-correcting moves. The answer is then \(T = \text{cost} + 1\) (adding 1 minute for the exit move).

inputFormat

The first line of input contains four integers: N, M, S_i and S_j, where N (1 ≤ N ≤ 1,000,000) is the number of rows, M (1 ≤ M ≤ 10,000) is the number of exit triangles, and (S_i, S_j) is the starting triangle.

The following M lines each contain two integers representing an exit triangle's coordinates: OUT_i and OUT_j. It is guaranteed that these coordinates refer to valid triangles in the maze.

outputFormat

Output a single line containing three space‐separated integers: the minimum time T (in minutes) required for Bessie to escape (including the extra minute after reaching an exit) followed by the coordinates of the exit triangle (OUT_i, OUT_j) where she should exit. If multiple exits yield the same minimum time, output the one with the smallest OUT_i and, if needed, the smallest OUT_j.

sample

3 2 3 3
3 2
3 5

2 3 2