MIKRO

문제

In the national biology competition, Mirko won a brand new microscope and now spends his free time exploring the micro-world. 

In one of his experiments, Mirko is studying the movement of bacteria in a sample of water from the stream near his building. He noticed that bacteria move in a very specific way. 

A drop of water can be modelled by an infinite square grid. For each bacterium, we know the coordinates of the unit square it is in and the direction it is moving in. The direction is a number between 1 and 8 as in the figure below. 

[이미지 1]

All bacteria move at the same time, at discrete time points, each in its own direction. Sometimes multiple bacteria find themselves in the same square. We say that a meeting of rank K took place at time T if some K bacteria found themselves in the same square exactly T moves after the beginning of the experiment. 

Mirko is intrigued by meetings of high rank so he wants to predict which meeting will have the highest rank and when it will happen. If there will be multiple such meetings of the highest rank, he is interested only in the time of the first meeting. 

입력

The first line contains an integer N (1 ≤ N ≤ 5000), the number of bacteria. Each of the following N lines contains three integers X, Y and D (-1 000 000 ≤ X, Y ≤ 1 000 000), (1 ≤ D ≤ 8), the starting coordinates and direction of one bacteria. X-coordinates increase from left to right, y-coordinates increase upwards. 

No two bacteria will initially share the same coordinates. 

The input will guarantee that at least one meeting will occur. 

출력

On the first line, output the highest rank of all meetings. 

On the second line, output the time of the first meeting of this highest rank.