Задачі
Хрестики-нулики
Хрестики-нулики
Петро і Василько грали у дуже цікаву гру. Гра відбувалась на аркуші паперу розміром \textbf{M}×\textbf{N} клітинок. Гравці по черзі ставили у ще незайняті клітинки або хрестик, або нулик до тих пір, доки весь аркуш не виявився заповненим. Тепер кількість очок, які набрав Петро визначається так: вибирається деяка клітинка з хрестиком, вибирається деякий напрям руху (вверх, вниз, вліво, вправо або вздовж однієї з діагоналей) і рахується скільки клітинок можна пройти у цьому напрямку, рухаючись лише по хрестикам (початкова і кінцева клітинки також враховуються). Отримане число і буде кількістю очок, які набрав Петя. Зрозуміло, він вибирає початкову клітинку і напрям так, щоб пройти якомога більше клітинок. Аналогічно обчисляються очки Василя, але лише по нуликам.
Напишіть програму, яка визначить з яким рахунком завершилась гра.
\InputFile
У першому рядку задано два цілих числа \textbf{M} і \textbf{N}, який визначає розміри листа (\textbf{1} ≤ \textbf{M}, \textbf{N} ≤ \textbf{1000}). У кожному з наступних \textbf{M} рядків записано по \textbf{N} цілих чисел, кожне з яких рівне \textbf{0} або \textbf{1} (\textbf{0} означає, що у відповідні клітинці стоїть нулик, а \textbf{1} - хрестик).
\OutputFile
У єдиний рядок виведіть рахунок гри - два цілих числа, перше з яких визначає кількість очок, набраних Петром, друге - кількість очок у Василя.
Вхідні дані #3
5 5 0 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 0
Вихідні дані #3
5 1