Optimal Warehouse Selection Challenge

You are given data about several warehouses and their corresponding delivery locations. Each warehouse has a unique identifier and coordinates (x, y). For each warehouse, a number of delivery locations is provided. Your task is to determine which warehouse should operate on a given day in order to minimize the total travel distance to all of its assigned deliveries.

The travel distance is measured using the Manhattan distance. The Manhattan distance between two points \((x_1,y_1)\) and \((x_2,y_2)\) is given by: \[ |x_1 - x_2| + |y_1 - y_2| \]

You must compute the total Manhattan distance from each warehouse to all of its delivery locations and choose the warehouse with the lowest total distance. In case of a tie, choose the first warehouse encountered in the input order.

inputFormat

The input is read from standard input (stdin) and has the following format:

n
id1 x1 y1
id2 x2 y2
...
idn xn yn
m
warehouse_id1 k1 lx1 ly1 lx2 ly2 ... lxk1 lyk1
warehouse_id2 k2 lx1 ly1 lx2 ly2 ... lxk2 lyk2
... 
warehouse_idm km lx1 ly1 lx2 ly2 ... lxkm lykm

Here:

• n is the number of warehouses.
• Each of the next n lines contains three integers: the warehouse id, and its x and y coordinates.
• m is the number of warehouses that have delivery assignments.
• Each of the next m lines starts with a warehouse id, followed by an integer k denoting the number of delivery locations for that warehouse, and then k pairs of integers (each pair representing the x and y coordinates of a delivery location).

outputFormat

The output, printed to standard output (stdout), is a single line in the following format:

The optimal warehouse is number {id} with the coordinates x = {x} and y = {y}

Where {id}, {x} and {y} are replaced by the identifier and coordinates of the warehouse with the minimal total Manhattan distance to its delivery locations.

## sample

1
1 3 2
1
1 3 5 5 3 6 7 8

The optimal warehouse is number 1 with the coordinates x = 3 and y = 2