Biologist

Time limit1sMemory limit128 MB

Summary
Simulate N bacteria moving in fixed grid directions and find the earliest time when the maximum overlap count occurs at one cell.
Level

Medium6 of 10

Topics
Math, Simulation, Geometry
Solved
No attempts yet

Problem

Kangsan, who dreams of becoming a biologist, received a microscope as a New Year gift.

One day, while observing bacteria in water, Kangsan noticed that their movement follows a fixed rule.

Model the water drop as an infinite square grid. Each bacterium is in one grid cell, and its direction is represented by a number in the table below.

123
8B4
765

All bacteria move simultaneously. Every second, each bacterium moves one cell in its own fixed direction. Multiple bacteria may occupy the same cell.

Given every bacterium's starting position and direction, find the maximum number of bacteria that ever occupy one cell at the same time, and the first time when that maximum occurs. If the same maximum occurs at several times, output the earliest time.

Input

The first line contains the number of bacteria N. 1 ≤ N ≤ 5,000

Each of the next N lines contains three integers X, Y, and D. -1,000,000 ≤ X, Y ≤ 1,000,000, 1 ≤ D ≤ 8

X and Y are the starting coordinates of a bacterium, and D is its direction. The value of X increases from left to right, and the value of Y increases upward.

No two bacteria start at the same position. At least once, two or more bacteria occupy the same cell.

Output

On the first line, output the maximum number of bacteria that occupied one cell at the same time.

On the second line, output the first time when that maximum occurred.

Examples2

  1. Example 1

    Input
    4
2 2 2
2 3 6
5 1 2
5 9 6
    Expected output
    2
4

  2. Example 2

    Input
    5 
1 1 1 
-6 0 3 
-2 0 2 
1 7 7 
-6 4 4
    Expected output
    3 
4