Closest Driver Allocation

You are given a list of customers and a list of drivers, each represented by their coordinates in a 2-dimensional plane. Your task is to assign each customer the nearest driver based on the Euclidean distance. Recall that the Euclidean distance between two points \((x_1,y_1)\) and \((x_2,y_2)\) is given by:

$$ d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2} $$

If there are multiple drivers at the same distance from a customer, choose the driver with the smallest index (starting from 0).

The input will be provided via standard input (stdin) and the output should be written to standard output (stdout) as a list of driver indices for each customer, separated by a space.

inputFormat

The input is given from stdin in the following format:

n
x1 y1
x2 y2
... (n lines for customers)
m
x1 y1
x2 y2
... (m lines for drivers)

where n is the number of customers and m is the number of drivers. Each coordinate is an integer.

outputFormat

The output should be a single line containing n integers. Each integer represents the index of the closest driver for the corresponding customer, separated by a space.

3
0 0
2 3
4 5
3
1 1
3 2
5 5

0 1 2