409489: GYM103584 B White Goosefoot

The White Goosefoot is a very peculiar plant. While it is not very well known among humans, geese know about it very well. In fact, several species of very intelligent geese visit a White Goosefoot every day, as a part of a geese ritual, per say.

There are several geese flocks scattered around the world, which is represented here as a 2D-plane. Furthermore, there are also lots of White Goosefoot plants scattered about as well. Given the locations of both, determine for every single flock, the location of the closest White Goosefoot. In the case that multiple White Goosefoot plants are equidistant from a flock, output the one with the smallest $$$x$$$ value, and in the case that the $$$x$$$ values are the same, output the one with the smallest $$$y$$$ value.

The first line of the input contains two integers $$$n (1 \le n \le 100)$$$ and $$$m (1 \le m \le 100)$$$, the number of flocks and the number of plants, respectively.

The next $$$n$$$ lines each contain two space separated integers $$$n_x (0 \le n_x \le 10^4), n_y (0 \le m_y \le 10^4)$$$, a location of a single flock. It is guaranteed that flock locations are unique.

The next $$$m$$$ lines each contain two space separated integers $$$m_x (0 \le n_x \le 10^4), m_y (0 \le m_y \le 10^4)$$$, a location of a single plant. It is guaranteed that plant locations are unique.

$$$n$$$ lines of output, each as two space separated integers, where the $$$i^{th}$$$ line is the nearest White Goosefoot plant for the $$$i^{th}$$$ flock.

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

0 2
0 2
5 5