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.

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.