Problem Statement

Build a KD-tree from a set of 2D integer points and answer nearest-neighbor queries. For each query point, return the index of the closest training point (ties broken by smallest index).

KD-tree construction:

• Alternate splitting axis: depth 0 uses x-axis, depth 1 uses y-axis, etc.
• At each level, sort the current set by the splitting axis (tie-break: other axis, then index), and place the median (index len//2 after sorting) at the current node.
• Recursively build left (indices before median) and right (indices from median+1) subtrees.

KD-tree search:

• Traverse toward the query's side first, then check if the hypersphere of radius best_dist intersects the splitting hyperplane; if so, also search the far side.
• Ties in distance: prefer the smaller index.

Function signature:

def kd_tree_nn(points: list, queries: list) -> list:
    # returns list of nearest-point indices (one per query)

Input Format

Line 1: n — number of training points
Lines 2..n+1: x y — integer coordinates (0-indexed)
Line n+2: q — number of queries
Lines n+3..n+q+2: x y — query coordinates

Output Format

q lines: one nearest-point index per query

Example

Input:

4
0 0
3 4
1 1
6 8
3
0 1
3 3
5 7

Output:

0
1
3

Notes

• Query (0,1) is closest to point 0 (0,0) with distance 1.
• Query (3,3) is closest to point 1 (3,4) with distance 1.
• Query (5,7) is closest to point 3 (6,8) with distance √2.