Route a request along diagonal server redirects

Servers sit at distinct integer points on an infinite 2D grid. locations[i] = [x, y] is the position of server i. A request starts at server 0, which counts as visited.

You are given a list redirect_records of directions, each from 1 to 4. From the current server at (a, b), a direction picks a diagonal ray:

For each direction in order, move the request to the unvisited server on that ray with the smallest Z, and mark it visited. If the ray has no unvisited server, skip the instruction and stay where you are.

Implement final_server(locations, redirect_records) -> [x, y], which returns the position of the server the request ends on.

Constraints: 1 <= n <= 10^5, 0 <= len(redirect_records) <= 10^5, coordinates in [-10^9, 10^9], all positions distinct. Aim for better than O(n * m).

Example 1

locations = [[0,0],[2,2],[5,5],[3,-3],[1,1],[-2,2]]
redirect_records = [1, 1, 1, 4]

Northeast goes to (1,1), then (2,2), then (5,5). Going southwest from (5,5), every server on that diagonal is visited, so the instruction is skipped. Answer: [5, 5].

Example 2

Same locations, redirect_records = [3, 2]. Northwest from (0,0) reaches (-2,2). Southeast from there passes the visited (0,0) and stops at (3,-3). Answer: [3, -3].