One Complete K-Means Iteration

Wexford Couriers wants the two halves put together and run once, so the planners can see how far their shortlist moves on the first pass. A round works like this: every address is booked to the site it would travel least far to reach, as the crow flies; every site afterwards moves to the centroid -- the balance point -- of the addresses booked to it. One round is all that is wanted. The moved sites are the answer, not the starting point for another pass. On this data no site finishes a round with nothing booked to it.

Task: Print where each site sits after one round.

Input

The first line holds one integer k, the number of starting sites, then k lines each holding a site's two map coordinates separated by a single space. Then one integer n, the number of addresses, then n lines each holding an address's two coordinates.

Output

k lines, one per site, in the order the sites were given. Each holds the moved site's east-west coordinate, a single space, then its north-south coordinate, each rounded to 2 decimal places. Every address is booked before any site moves. An address equidistant from two sites goes to whichever came earlier in the list.

Example:

Input:
2
0 0
10 10
4
1 1
2 2
9 9
8 8

Output:
1.50 1.50
8.50 8.50