On a chessboard of size $$$N$$$ x $$$N$$$, there are $$$K$$$ bishops. Recall that a bishop is a piece that can move to any number of empty squares diagonally in one of four directions (up-right, up-left, down-right, and down-left) in a single move.
Find an empty square such that it is under attack by the maximum number of bishops (i.e., the maximum number of bishops can reach this square in one move).
The first line of input contains an integer $$$N$$$ ($$$2 \le N \le 10^9$$$).
The second line contains an integer $$$K$$$ ($$$1 \le K \le min(1000, N^2-1)$$$).
The next $$$K$$$ lines contain pairs of integers $$$x_i$$$, $$$y_i$$$ separated by spaces — the coordinates of the bishops ($$$1 \le x_i, y_i \le n$$$). No two pairs of coordinates are the same.
Output two integers — the coordinates of the found square (first the horizontal coordinate, then the vertical coordinate). If there are multiple correct answers, output any.
Subtask 1 (up to 30 points): $$$N \le 100$$$.
Subtask 2 (up to 30 points): $$$K = 2$$$.
Subtask 3 (up to 40 points): no additional constraints.
431 23 24 1
2 3
Below is a illustration for the example. One of the two possible target squares is shaded gray. It is under attack by two bishops (the third bishop cannot reach it because another bishop is blocking the way). Note that the answer "2 1" is also correct.
