In the game of chess, the knight is known for being able to maneuver tricky spaces - but only in an 'L' shape. In order to further your understanding of chess and the knight, you are tasked with finding out the optimal move for a knight 1 move ahead. More formally, a knight is able to move 2 spaces in one direction and 1 space in a direction perpendicular to the first. If the space it ultimately lands on contains an enemy piece, the knight can capture it. Your goal is to find, of all pieces it can capture in one move, the one with the highest value.
Input Specification
The first line will contain two integers, and , the x and y coordinates of the knight.
The next line will contain an integer , the number of enemy pieces.
The next lines will contain 3 integers, , , , the x and y coordinates of the enemy piece, and the number of points they are worth. All pieces are guaranteed to be at different positions.
Output Specification
If the knight cannot capture any piece, print out -1
.
Otherwise, print out the and coordinates of the piece that the knight should capture - that is, the one with the highest point value. If multiple pieces have the same highest point value, print out the one that appeared earliest in the input.
Sample Input
3 5
3
1 6 3
5 4 4
1 1 100
Sample Output
5 4
Sample Explanation
The knight can reach (1, 6)
and (5, 4)
, but not (1, 1)
; capturing the piece of (5, 4)
gives the knight 4 points, which is the most that it can get.
Comments