Nearest Aligned Supply Beacon

A warehouse routing drone hovers at a fixed grid position (x, y) inside a distribution center whose overhead rail network only runs along rows and columns. The ceiling holds a list of n supply beacons, numbered 0 through n-1 in the order they are given; beacon i sits at grid position (a_i, b_i).

The drone's rail carriage can dock directly at beacon i only when the beacon lies exactly on the drone's current row or column, i.e. only when a_i == x or b_i == y. Among every beacon that qualifies this way, the drone must select the one that minimizes travel distance, where distance is the Manhattan distance |x - a_i| + |y - b_i|. If two or more qualifying beacons tie for the smallest distance, the drone always selects the one with the smaller index. If no beacon qualifies at all, the drone reports -1.

Given the drone's position and the beacon list, determine the index of the beacon the drone should dock at (or -1 if none qualifies).

Input format

• Line 1: three integers x y n -- the drone's coordinates and the number of beacons.
• Each of the next n lines contains two integers a_i b_i -- the coordinates of beacon i (beacons are numbered 0 to n-1 in the order given).

Output format

• A single integer: the index of the chosen beacon, or -1 if no beacon shares the drone's row or column.

Constraints

• 1 <= n <= 10^4
• -10^9 <= x, y, a_i, b_i <= 10^9

5 5 3
5 9
2 5
5 5

2

0 0 2
1 2
3 4

-1