시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 139 25 20 30.769%

문제

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

어느 날, 물 속에 있는 박테리아의 움직임을 관찰하고 있었다. 관찰을 한 시간 정도 하다보니, 일정한 규칙대로 움직인다는 것을 알 수 있었다.

물방울은 크기가 무한대인 정사각형 격자로 모델링 할 수 있다. 박테리아는 한 정사각형에 있다. 박테리아가 움직이는 방향은 다음과 같이 숫자로 표현할 수 있다.

1 2 3
8 B 4
7 6 5

모든 박테리아는 동시에 움직이고, 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값은 위로 갈수록 증가한다.

박테리아의 시작 위치가 겹치는 경우는 없으며, 적어도 한 번은 박테리아가 만난다.

출력

첫째 줄에 박테리아가 같은 칸에 가장 많이 있었을 때, 몇 마리나 있었는지 출력한다. 둘째 줄에는 그 때의 시간을 출력한다.

예제 입력 1

5 
1 1 1 
-6 0 3 
-2 0 2 
1 7 7 
-6 4 4

예제 출력 1

3 
4
W3sicHJvYmxlbV9pZCI6IjMxMTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwZGRcdWJiM2NcdWQ1NTlcdWM3OTAiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzBkZFx1YmIzY1x1ZDU1OVx1Yzc5MFx1Yjk3YyBcdWFmYzhcdWFmYjhcdWIyOTQgXHVhYzE1XHVjMGIwXHVjNzc0XHViMjk0IFx1YzBjOFx1ZDU3NCBcdWMxMjBcdWJiM2NcdWI4NWMgXHVkNjA0XHViYmY4XHVhY2JkXHVjNzQ0IFx1YmMxYlx1YzU1OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNWI0XHViMjkwIFx1YjBhMCwgXHViYjNjIFx1YzE4ZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVjNzU4IFx1YzZjMFx1YzljMVx1Yzc4NFx1Yzc0NCBcdWFkMDBcdWNjMzBcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWFkMDBcdWNjMzBcdWM3NDQgXHVkNTVjIFx1YzJkY1x1YWMwNCBcdWM4MTVcdWIzYzQgXHVkNTU4XHViMmU0XHViY2Y0XHViMmM4LCBcdWM3N2NcdWM4MTVcdWQ1NWMgXHVhZGRjXHVjZTU5XHViMzAwXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmIzY1x1YmMyOVx1YzZiOFx1Yzc0MCBcdWQwNmNcdWFlMzBcdWFjMDAgXHViYjM0XHVkNTVjXHViMzAwXHVjNzc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFjYTlcdWM3OTBcdWI4NWMgXHViYWE4XHViMzc4XHViOWMxIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWIyOTQgXHVkNTVjIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzVkMCBcdWM3ODhcdWIyZTQuIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YWMwMCBcdWM2YzBcdWM5YzFcdWM3NzRcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjMjJiXHVjNzkwXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOiAxMiU7XCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDogNCU7IHRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDE8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6IDQlOyB0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHQyPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOiA0JTsgdGV4dC1hbGlnbjpjZW50ZXI7XCI+XHJcblx0XHRcdFx0MzxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDg8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+XHJcblx0XHRcdFx0QjxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHQ0PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+XHJcblx0XHRcdFx0NzxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHQ2PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlxyXG5cdFx1YmFhOFx1YjRlMCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWIyOTQgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YzZjMFx1YzljMVx1Yzc3NFx1YWNlMCwgMVx1Y2QwOCBcdWIyZThcdWM3MDRcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHVhY2UwLCBcdWQ1NWMgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjXHViOWNjIFx1YzZjMFx1YzljMVx1Yzc3OFx1YjJlNC4gXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0IFx1YzVlY1x1YjdlYyBcdWI5YzhcdWI5YWNcdWFjMDAgXHVhYzE5XHVjNzQwIFx1Y2U3OFx1YzVkMCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWM2YzBcdWM5YzFcdWM3NzRcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NCBcdWM1ZWNcdWI3ZWMgXHViOWM4XHViOWFjXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWNlNzhcdWM1ZDAgXHVjODFjXHVjNzdjIFx1YjljZVx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjXHVhYzAwIFx1YzViOFx1YzgxY1x1Yzc3OFx1YzljMCwgXHVhZGY4XHViOWFjXHVhY2UwIFx1YWRmOCBcdWI1NGMgXHViYTg3IFx1YjljOFx1YjlhY1x1YWMwMCBcdWFjMTlcdWM3NDAgXHVjZTc4XHVjNWQwIFx1Yzc4OFx1YzVjOFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViOWNjXHVjNTdkIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzFjXHViNzdjXHViYTc0LCBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWM3NTggXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyA1LDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0Llx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBYLCBZLCBEICgtMSwwMDAsMDAwICZsZTsgWCxZICZsZTsgMSwwMDAsMDAwKSwgKDEgJmxlOyBEICZsZTsgOCkgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHJcblx0WFx1YzY0MCBZXHViMjk0IFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjODhjXHVkNDVjXHVjNzc0XHViYTcwLCBEXHViMjk0IFx1YmMyOVx1ZDVhNVx1Yzc3NFx1YjJlNC4gWFx1YWMxMlx1Yzc0MCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YWMwOCBcdWMyMThcdWI4NWQgXHVjOTlkXHVhYzAwXHVkNTU4XHViYTcwLCBZXHVhYzEyXHVjNzQwIFx1YzcwNFx1Yjg1YyBcdWFjMDhcdWMyMThcdWI4NWQgXHVjOTlkXHVhYzAwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWM3NTggXHVjMmRjXHVjNzkxIFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWFjYjlcdWNlNThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YzczY1x1YmE3MCwgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1YyBcdWJjODhcdWM3NDAgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVhYzAwIFx1YjljY1x1YjA5Y1x1YjJlNC48XC9wPlxyXG5cclxuXHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWNlNzhcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc3NCBcdWM3ODhcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWJhODcgXHViOWM4XHViOWFjXHViMDk4IFx1Yzc4OFx1YzVjOFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1YjU0Y1x1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxMTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNSUtSTyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhlIG5hdGlvbmFsIGJpb2xvZ3kgY29tcGV0aXRpb24sIE1pcmtvIHdvbiBhIGJyYW5kIG5ldyBtaWNyb3Njb3BlIGFuZCBub3cgc3BlbmRzIGhpcyBmcmVlIHRpbWUgZXhwbG9yaW5nIHRoZSBtaWNyby13b3JsZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gb25lIG9mIGhpcyBleHBlcmltZW50cywgTWlya28gaXMgc3R1ZHlpbmcgdGhlIG1vdmVtZW50IG9mIGJhY3RlcmlhIGluIGEgc2FtcGxlIG9mIHdhdGVyIGZyb20gdGhlIHN0cmVhbSBuZWFyIGhpcyBidWlsZGluZy4gSGUgbm90aWNlZCB0aGF0IGJhY3RlcmlhIG1vdmUgaW4gYSB2ZXJ5IHNwZWNpZmljIHdheS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBkcm9wIG9mIHdhdGVyIGNhbiBiZSBtb2RlbGxlZCBieSBhbiBpbmZpbml0ZSBzcXVhcmUgZ3JpZC4gRm9yIGVhY2ggYmFjdGVyaXVtLCB3ZSBrbm93IHRoZSBjb29yZGluYXRlcyBvZiB0aGUgdW5pdCBzcXVhcmUgaXQgaXMgaW4gYW5kIHRoZSBkaXJlY3Rpb24gaXQgaXMgbW92aW5nIGluLiBUaGUgZGlyZWN0aW9uIGlzIGEgbnVtYmVyIGJldHdlZW4gMSBhbmQgOCBhcyBpbiB0aGUgZmlndXJlIGJlbG93LiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21pa3JvLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEwMnB4OyB3aWR0aDoxNDhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BbGwgYmFjdGVyaWEgbW92ZSBhdCB0aGUgc2FtZSB0aW1lLCBhdCBkaXNjcmV0ZSB0aW1lIHBvaW50cywgZWFjaCBpbiBpdHMgb3duIGRpcmVjdGlvbi4gU29tZXRpbWVzIG11bHRpcGxlIGJhY3RlcmlhIGZpbmQgdGhlbXNlbHZlcyBpbiB0aGUgc2FtZSBzcXVhcmUuIFdlIHNheSB0aGF0IGEgbWVldGluZyBvZiByYW5rIEsgdG9vayBwbGFjZSBhdCB0aW1lIFQgaWYgc29tZSBLIGJhY3RlcmlhIGZvdW5kIHRoZW1zZWx2ZXMgaW4gdGhlIHNhbWUgc3F1YXJlIGV4YWN0bHkgVCBtb3ZlcyBhZnRlciB0aGUgYmVnaW5uaW5nIG9mIHRoZSBleHBlcmltZW50LiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyBpcyBpbnRyaWd1ZWQgYnkgbWVldGluZ3Mgb2YgaGlnaCByYW5rIHNvIGhlIHdhbnRzIHRvIHByZWRpY3Qgd2hpY2ggbWVldGluZyB3aWxsIGhhdmUgdGhlIGhpZ2hlc3QgcmFuayBhbmQgd2hlbiBpdCB3aWxsIGhhcHBlbi4gSWYgdGhlcmUgd2lsbCBiZSBtdWx0aXBsZSBzdWNoIG1lZXRpbmdzIG9mIHRoZSBoaWdoZXN0IHJhbmssIGhlIGlzIGludGVyZXN0ZWQgb25seSBpbiB0aGUgdGltZSBvZiB0aGUgZmlyc3QgbWVldGluZy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyA1MDAwKSwgdGhlIG51bWJlciBvZiBiYWN0ZXJpYS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgWCwgWSBhbmQgRCAoLTEgMDAwIDAwMCAmbGU7IFgsIFkgJmxlOyAxIDAwMCAwMDApLCAoMSAmbGU7IEQgJmxlOyA4KSwgdGhlIHN0YXJ0aW5nIGNvb3JkaW5hdGVzIGFuZCBkaXJlY3Rpb24gb2Ygb25lIGJhY3RlcmlhLiBYLWNvb3JkaW5hdGVzIGluY3JlYXNlIGZyb20gbGVmdCB0byByaWdodCwgeS1jb29yZGluYXRlcyBpbmNyZWFzZSB1cHdhcmRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5ObyB0d28gYmFjdGVyaWEgd2lsbCBpbml0aWFsbHkgc2hhcmUgdGhlIHNhbWUgY29vcmRpbmF0ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBpbnB1dCB3aWxsIGd1YXJhbnRlZSB0aGF0IGF0IGxlYXN0IG9uZSBtZWV0aW5nIHdpbGwgb2NjdXIuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUsIG91dHB1dCB0aGUgaGlnaGVzdCByYW5rIG9mIGFsbCBtZWV0aW5ncy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T24gdGhlIHNlY29uZCBsaW5lLCBvdXRwdXQgdGhlIHRpbWUgb2YgdGhlIGZpcnN0IG1lZXRpbmcgb2YgdGhpcyBoaWdoZXN0IHJhbmsuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=