생물학자

생물학자를 꿈꾸는 강산이는 새해 선물로 현미경을 받았다.

어느 날 강산이는 물속 박테리아의 움직임을 관찰하다가, 박테리아들이 일정한 규칙에 따라 움직인다는 사실을 알아냈다.

물방울은 크기가 무한한 정사각형 격자로 생각할 수 있다. 각 박테리아는 한 격자 칸에 있으며, 움직이는 방향은 다음 표의 숫자로 나타낸다.

모든 박테리아는 동시에 움직인다. 박테리아는 1초마다 자신이 가진 한 방향으로 한 칸씩 이동하며, 여러 박테리아가 같은 칸에 있을 수 있다.

각 박테리아의 시작 위치와 이동 방향이 주어질 때, 한 칸에 동시에 존재한 박테리아 수의 최댓값과 그 최댓값이 처음 나타나는 시간을 구하시오. 최댓값이 여러 시각에 나타난다면 가장 이른 시간을 출력한다.

첫째 줄에 박테리아의 수 N이 주어진다. 1 ≤ N ≤ 5,000

다음 N개의 줄에는 세 정수 X, Y, D가 주어진다. -1,000,000 ≤ X, Y ≤ 1,000,000, 1 ≤ D ≤ 8

X와 Y는 박테리아의 시작 좌표이고, D는 이동 방향이다. X값은 오른쪽으로 갈수록 커지고, Y값은 위로 갈수록 커진다.

서로 다른 박테리아가 같은 시작 위치에 있는 경우는 없다. 또한 적어도 한 번은 두 마리 이상의 박테리아가 같은 칸에 있게 된다.

첫째 줄에 한 칸에 동시에 있었던 박테리아 수의 최댓값을 출력한다.

둘째 줄에 그 최댓값이 처음 나타난 시간을 출력한다.