시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB190342829.167%

문제

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

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

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

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

4
2 2 2
2 3 6
5 1 2
5 9 6

예제 출력 1

2
4

예제 입력 2

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

예제 출력 2

3 
4
W3sicHJvYmxlbV9pZCI6IjMxMTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwZGRcdWJiM2NcdWQ1NTlcdWM3OTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBkZFx1YmIzY1x1ZDU1OVx1Yzc5MFx1Yjk3YyBcdWFmYzhcdWFmYjhcdWIyOTQgXHVhYzE1XHVjMGIwXHVjNzc0XHViMjk0IFx1YzBjOFx1ZDU3NCBcdWMxMjBcdWJiM2NcdWI4NWMgXHVkNjA0XHViYmY4XHVhY2JkXHVjNzQ0IFx1YmMxYlx1YzU1OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViMjkwIFx1YjBhMCwgXHViYjNjIFx1YzE4ZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVjNzU4IFx1YzZjMFx1YzljMVx1Yzc4NFx1Yzc0NCBcdWFkMDBcdWNjMzBcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWFkMDBcdWNjMzBcdWM3NDQgXHVkNTVjIFx1YzJkY1x1YWMwNCBcdWM4MTVcdWIzYzQgXHVkNTU4XHViMmU0XHViY2Y0XHViMmM4LCBcdWM3N2NcdWM4MTVcdWQ1NWMgXHVhZGRjXHVjZTU5XHViMzAwXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzY1x1YmMyOVx1YzZiOFx1Yzc0MCBcdWQwNmNcdWFlMzBcdWFjMDAgXHViYjM0XHVkNTVjXHViMzAwXHVjNzc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFjYTlcdWM3OTBcdWI4NWMgXHViYWE4XHViMzc4XHViOWMxIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWIyOTQgXHVkNTVjIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzVkMCBcdWM3ODhcdWIyZTQuIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YWMwMCBcdWM2YzBcdWM5YzFcdWM3NzRcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjMjJiXHVjNzkwXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6IDEyJTtcIj5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOiA0JTsgdGV4dC1hbGlnbjpjZW50ZXI7XCI+MTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDogNCU7IHRleHQtYWxpZ246Y2VudGVyO1wiPjI8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6IDQlOyB0ZXh0LWFsaWduOmNlbnRlcjtcIj4zPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+ODxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj5CPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPjQ8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj43PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPjY8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7XCI+NTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YjI5NCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVjNmMwXHVjOWMxXHVjNzc0XHVhY2UwLCAxXHVjZDA4IFx1YjJlOFx1YzcwNFx1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWFjZTAsIFx1ZDU1YyBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWNcdWI5Y2MgXHVjNmMwXHVjOWMxXHVjNzc4XHViMmU0LiBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDQgXHVjNWVjXHViN2VjIFx1YjljOFx1YjlhY1x1YWMwMCBcdWFjMTlcdWM3NDAgXHVjZTc4XHVjNWQwIFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWM3NTggXHVjNzA0XHVjZTU4XHVjNjQwIFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0IFx1YzVlY1x1YjdlYyBcdWI5YzhcdWI5YWNcdWFjMDAgXHVhYzE5XHVjNzQwIFx1Y2U3OFx1YzVkMCBcdWM4MWNcdWM3N2MgXHViOWNlXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGNcdWFjMDAgXHVjNWI4XHVjODFjXHVjNzc4XHVjOWMwLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4IFx1YjU0YyBcdWJhODcgXHViOWM4XHViOWFjXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWNlNzhcdWM1ZDAgXHVjNzg4XHVjNWM4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWI5Y2NcdWM1N2QgXHVjNzc0XHViN2VjXHVkNTVjIFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc3NCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWI3N2NcdWJhNzQsIFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVjNzU4IFx1YzIxOCBOKDEgJmxlOyBOICZsZTsgNSwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggWCwgWSwgRCAoLTEsMDAwLDAwMCAmbGU7IFgsWSAmbGU7IDEsMDAwLDAwMCksICgxICZsZTsgRCAmbGU7IDgpIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlhcdWM2NDAgWVx1YjI5NCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWM3NTggXHVjMmRjXHVjNzkxIFx1Yzg4Y1x1ZDQ1Y1x1Yzc3NFx1YmE3MCwgRFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NzRcdWIyZTQuIFhcdWFjMTJcdWM3NDAgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWFjMDggXHVjMjE4XHViODVkIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YmE3MCwgWVx1YWMxMlx1Yzc0MCBcdWM3MDRcdWI4NWMgXHVhYzA4XHVjMjE4XHViODVkIFx1Yzk5ZFx1YWMwMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNThcdWFjMDAgXHVhY2I5XHVjZTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWM3M2NcdWJhNzAsIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHViYzg4XHVjNzQwIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YWMwMCBcdWI5Y2NcdWIwOWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWFjMDAgXHVhYzE5XHVjNzQwIFx1Y2U3OFx1YzVkMCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzc0IFx1Yzc4OFx1YzVjOFx1Yzc0NCBcdWI1NGMsIFx1YmE4NyBcdWI5YzhcdWI5YWNcdWIwOTggXHVjNzg4XHVjNWM4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkZjggXHViNTRjXHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzExNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1JS1JPIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgbmF0aW9uYWwgYmlvbG9neSBjb21wZXRpdGlvbiwgTWlya28gd29uIGEgYnJhbmQgbmV3IG1pY3Jvc2NvcGUgYW5kIG5vdyBzcGVuZHMgaGlzIGZyZWUgdGltZSBleHBsb3JpbmcgdGhlIG1pY3JvLXdvcmxkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBvbmUgb2YgaGlzIGV4cGVyaW1lbnRzLCBNaXJrbyBpcyBzdHVkeWluZyB0aGUgbW92ZW1lbnQgb2YgYmFjdGVyaWEgaW4gYSBzYW1wbGUgb2Ygd2F0ZXIgZnJvbSB0aGUgc3RyZWFtIG5lYXIgaGlzIGJ1aWxkaW5nLiBIZSBub3RpY2VkIHRoYXQgYmFjdGVyaWEgbW92ZSBpbiBhIHZlcnkgc3BlY2lmaWMgd2F5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIGRyb3Agb2Ygd2F0ZXIgY2FuIGJlIG1vZGVsbGVkIGJ5IGFuIGluZmluaXRlIHNxdWFyZSBncmlkLiBGb3IgZWFjaCBiYWN0ZXJpdW0sIHdlIGtub3cgdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSB1bml0IHNxdWFyZSBpdCBpcyBpbiBhbmQgdGhlIGRpcmVjdGlvbiBpdCBpcyBtb3ZpbmcgaW4uIFRoZSBkaXJlY3Rpb24gaXMgYSBudW1iZXIgYmV0d2VlbiAxIGFuZCA4IGFzIGluIHRoZSBmaWd1cmUgYmVsb3cuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbWlrcm8ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTAycHg7IHdpZHRoOjE0OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkFsbCBiYWN0ZXJpYSBtb3ZlIGF0IHRoZSBzYW1lIHRpbWUsIGF0IGRpc2NyZXRlIHRpbWUgcG9pbnRzLCBlYWNoIGluIGl0cyBvd24gZGlyZWN0aW9uLiBTb21ldGltZXMgbXVsdGlwbGUgYmFjdGVyaWEgZmluZCB0aGVtc2VsdmVzIGluIHRoZSBzYW1lIHNxdWFyZS4gV2Ugc2F5IHRoYXQgYSBtZWV0aW5nIG9mIHJhbmsgSyB0b29rIHBsYWNlIGF0IHRpbWUgVCBpZiBzb21lIEsgYmFjdGVyaWEgZm91bmQgdGhlbXNlbHZlcyBpbiB0aGUgc2FtZSBzcXVhcmUgZXhhY3RseSBUIG1vdmVzIGFmdGVyIHRoZSBiZWdpbm5pbmcgb2YgdGhlIGV4cGVyaW1lbnQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvIGlzIGludHJpZ3VlZCBieSBtZWV0aW5ncyBvZiBoaWdoIHJhbmsgc28gaGUgd2FudHMgdG8gcHJlZGljdCB3aGljaCBtZWV0aW5nIHdpbGwgaGF2ZSB0aGUgaGlnaGVzdCByYW5rIGFuZCB3aGVuIGl0IHdpbGwgaGFwcGVuLiBJZiB0aGVyZSB3aWxsIGJlIG11bHRpcGxlIHN1Y2ggbWVldGluZ3Mgb2YgdGhlIGhpZ2hlc3QgcmFuaywgaGUgaXMgaW50ZXJlc3RlZCBvbmx5IGluIHRoZSB0aW1lIG9mIHRoZSBmaXJzdCBtZWV0aW5nLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDUwMDApLCB0aGUgbnVtYmVyIG9mIGJhY3RlcmlhLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBYLCBZIGFuZCBEICgtMSAwMDAgMDAwICZsZTsgWCwgWSAmbGU7IDEgMDAwIDAwMCksICgxICZsZTsgRCAmbGU7IDgpLCB0aGUgc3RhcnRpbmcgY29vcmRpbmF0ZXMgYW5kIGRpcmVjdGlvbiBvZiBvbmUgYmFjdGVyaWEuIFgtY29vcmRpbmF0ZXMgaW5jcmVhc2UgZnJvbSBsZWZ0IHRvIHJpZ2h0LCB5LWNvb3JkaW5hdGVzIGluY3JlYXNlIHVwd2FyZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vIHR3byBiYWN0ZXJpYSB3aWxsIGluaXRpYWxseSBzaGFyZSB0aGUgc2FtZSBjb29yZGluYXRlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IHdpbGwgZ3VhcmFudGVlIHRoYXQgYXQgbGVhc3Qgb25lIG1lZXRpbmcgd2lsbCBvY2N1ci4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSwgb3V0cHV0IHRoZSBoaWdoZXN0IHJhbmsgb2YgYWxsIG1lZXRpbmdzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PbiB0aGUgc2Vjb25kIGxpbmUsIG91dHB1dCB0aGUgdGltZSBvZiB0aGUgZmlyc3QgbWVldGluZyBvZiB0aGlzIGhpZ2hlc3QgcmFuay4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d