시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 51 2 2 16.667%

문제

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

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

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

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+XHJcblx0XHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWM2YzBcdWM5YzFcdWM3NzRcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NCBcdWM1ZWNcdWI3ZWMgXHViOWM4XHViOWFjXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWNlNzhcdWM1ZDAgXHVjODFjXHVjNzdjIFx1YjljZVx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjXHVhYzAwIFx1YzViOFx1YzgxY1x1Yzc3OFx1YzljMCwgXHVhZGY4XHViOWFjXHVhY2UwIFx1YWRmOCBcdWI1NGMgXHViYTg3IFx1YjljOFx1YjlhY1x1YWMwMCBcdWFjMTlcdWM3NDAgXHVjZTc4XHVjNWQwIFx1Yzc4OFx1YzVjOFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViOWNjXHVjNTdkIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWNkNWNcdWIzMDBcdWFjMTJcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzFjXHViNzdjXHViYTc0LCBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWM3NTggXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyA1LDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0Llx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBYLCBZLCBEICgtMSwwMDAsMDAwICZsZTsgWCxZICZsZTsgMSwwMDAsMDAwKSwgKDEgJmxlOyBEICZsZTsgOCkgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHJcblx0WFx1YzY0MCBZXHViMjk0IFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjODhjXHVkNDVjXHVjNzc0XHViYTcwLCBEXHViMjk0IFx1YmMyOVx1ZDVhNVx1Yzc3NFx1YjJlNC4gWFx1YWMxMlx1Yzc0MCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YWMwOCBcdWMyMThcdWI4NWQgXHVjOTlkXHVhYzAwXHVkNTU4XHViYTcwLCBZXHVhYzEyXHVjNzQwIFx1YzcwNFx1Yjg1YyBcdWFjMDhcdWMyMThcdWI4NWQgXHVjOTlkXHVhYzAwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWM3NTggXHVjMmRjXHVjNzkxIFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWFjYjlcdWNlNThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YzczY1x1YmE3MCwgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1YyBcdWJjODhcdWM3NDAgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVhYzAwIFx1YjljY1x1YjA5Y1x1YjJlNC48XC9wPlxyXG5cclxuXHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWNlNzhcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc3NCBcdWM3ODhcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWJhODcgXHViOWM4XHViOWFjXHViMDk4IFx1Yzc4OFx1YzVjOFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1YjU0Y1x1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTE2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTUlLUk8iLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBuYXRpb25hbCBiaW9sb2d5IGNvbXBldGl0aW9uLCBNaXJrbyB3b24gYSBicmFuZCBuZXcgbWljcm9zY29wZSBhbmQgbm93IHNwZW5kcyBoaXMgZnJlZSB0aW1lIGV4cGxvcmluZyB0aGUgbWljcm8td29ybGQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIG9uZSBvZiBoaXMgZXhwZXJpbWVudHMsIE1pcmtvIGlzIHN0dWR5aW5nIHRoZSBtb3ZlbWVudCBvZiBiYWN0ZXJpYSBpbiBhIHNhbXBsZSBvZiB3YXRlciBmcm9tIHRoZSBzdHJlYW0gbmVhciBoaXMgYnVpbGRpbmcuIEhlIG5vdGljZWQgdGhhdCBiYWN0ZXJpYSBtb3ZlIGluIGEgdmVyeSBzcGVjaWZpYyB3YXkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgZHJvcCBvZiB3YXRlciBjYW4gYmUgbW9kZWxsZWQgYnkgYW4gaW5maW5pdGUgc3F1YXJlIGdyaWQuIEZvciBlYWNoIGJhY3Rlcml1bSwgd2Uga25vdyB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIHVuaXQgc3F1YXJlIGl0IGlzIGluIGFuZCB0aGUgZGlyZWN0aW9uIGl0IGlzIG1vdmluZyBpbi4gVGhlIGRpcmVjdGlvbiBpcyBhIG51bWJlciBiZXR3ZWVuIDEgYW5kIDggYXMgaW4gdGhlIGZpZ3VyZSBiZWxvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9taWtyby5wbmdcIiBzdHlsZT1cImhlaWdodDoxMDJweDsgd2lkdGg6MTQ4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QWxsIGJhY3RlcmlhIG1vdmUgYXQgdGhlIHNhbWUgdGltZSwgYXQgZGlzY3JldGUgdGltZSBwb2ludHMsIGVhY2ggaW4gaXRzIG93biBkaXJlY3Rpb24uIFNvbWV0aW1lcyBtdWx0aXBsZSBiYWN0ZXJpYSBmaW5kIHRoZW1zZWx2ZXMgaW4gdGhlIHNhbWUgc3F1YXJlLiBXZSBzYXkgdGhhdCBhIG1lZXRpbmcgb2YgcmFuayBLIHRvb2sgcGxhY2UgYXQgdGltZSBUIGlmIHNvbWUgSyBiYWN0ZXJpYSBmb3VuZCB0aGVtc2VsdmVzIGluIHRoZSBzYW1lIHNxdWFyZSBleGFjdGx5IFQgbW92ZXMgYWZ0ZXIgdGhlIGJlZ2lubmluZyBvZiB0aGUgZXhwZXJpbWVudC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gaXMgaW50cmlndWVkIGJ5IG1lZXRpbmdzIG9mIGhpZ2ggcmFuayBzbyBoZSB3YW50cyB0byBwcmVkaWN0IHdoaWNoIG1lZXRpbmcgd2lsbCBoYXZlIHRoZSBoaWdoZXN0IHJhbmsgYW5kIHdoZW4gaXQgd2lsbCBoYXBwZW4uIElmIHRoZXJlIHdpbGwgYmUgbXVsdGlwbGUgc3VjaCBtZWV0aW5ncyBvZiB0aGUgaGlnaGVzdCByYW5rLCBoZSBpcyBpbnRlcmVzdGVkIG9ubHkgaW4gdGhlIHRpbWUgb2YgdGhlIGZpcnN0IG1lZXRpbmcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgNTAwMCksIHRoZSBudW1iZXIgb2YgYmFjdGVyaWEuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIFgsIFkgYW5kIEQgKC0xIDAwMCAwMDAgJmxlOyBYLCBZICZsZTsgMSAwMDAgMDAwKSwgKDEgJmxlOyBEICZsZTsgOCksIHRoZSBzdGFydGluZyBjb29yZGluYXRlcyBhbmQgZGlyZWN0aW9uIG9mIG9uZSBiYWN0ZXJpYS4gWC1jb29yZGluYXRlcyBpbmNyZWFzZSBmcm9tIGxlZnQgdG8gcmlnaHQsIHktY29vcmRpbmF0ZXMgaW5jcmVhc2UgdXB3YXJkcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm8gdHdvIGJhY3RlcmlhIHdpbGwgaW5pdGlhbGx5IHNoYXJlIHRoZSBzYW1lIGNvb3JkaW5hdGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgaW5wdXQgd2lsbCBndWFyYW50ZWUgdGhhdCBhdCBsZWFzdCBvbmUgbWVldGluZyB3aWxsIG9jY3VyLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lLCBvdXRwdXQgdGhlIGhpZ2hlc3QgcmFuayBvZiBhbGwgbWVldGluZ3MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk9uIHRoZSBzZWNvbmQgbGluZSwgb3V0cHV0IHRoZSB0aW1lIG9mIHRoZSBmaXJzdCBtZWV0aW5nIG9mIHRoaXMgaGlnaGVzdCByYW5rLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==