Mr. Chopsticks found a lot of ants and ant nests on Mars. The behavior of these ants seems quite different from ants on earth, so Mr. Chopsticks built a laboratory to study them. In the laboratory, there is a flat land and N ant nests, numbered from 1 to N, on it. The ith nest’s location is (xi, yi), and no two nests are at the same location. After a period of observation, Mr. Chopsticks has found some laws which all the moving ants obey:
1. When an ant is at a nest p, it always moves to another nest which is closest to p. If there are multiple nests with minimum distance from p, it moves to the one with smaller x-coordinate value. If there is still a tie, the one with smaller y-coordinate value is chosen. When an ant moves from a nest to another, it always moves along the segment connecting them.
2. An ant never stops, that is, when an ant arrives at a nest, it moves to the next nest immediately. So, of course, an ant may visit a nest infinitely many times.
3. All the ants move at the same speed.
What happens if two ants meet each other? Will they fight? Mr. Chopsticks is curious about these questions. But at first, he should know whether two ants will meet. So he considers the following question: Given two different nests, if two ants start to move from these two nests simultaneously, will they meet at some time during their moving?
Note that all the ants and nests can be considered as points.