Приватні інтереси
На клітинках прямокутної таблиці, що має m рядків та n стовпчиків, розкладено монети. Двоє гравців по черзі рухають пішак або праворуч, або вгору на одне поле за один хід. Гру розпочинає перший гравець з крайнього нижнього лівого поля. Гру припиняють після досягнення пішаком першого (якщо рахувати згори вниз) рядка чи останнього (якщо рахувати зліва направо) стовпчика таблиці. Кожен гравець:
не має можливості спілкуватися з суперником;
знає розподіл монет перед початком гри;
знає розташування пішака у будь-який момент гри;
забирає монети з клітин, на які ставить пішак;
намагається отримати найбільшу суму грошей за всю гру;
ходить праворуч лише тоді, коли хід вгору приносить менший остаточний зиск;
знає і враховує намагання суперника;
знає, що суперник діє аналогічно.
Створіть програму, яка передбачить результат гри та рух пішака.
Вхідні дані
Перший рядок містить у вказаному порядку натуральні числа m та n. Для j в межах від 1 до m включно (j + 1)-ий рядок містить невід'ємні цілі числа - сукупні вартості монет у клітинках j-го рядка таблиці в тому порядку, як вони (клітинки цього рядка) розташовані в таблиці зліва направо. Кількість всіх чисел не перевищує 12346, максимальний виграш не перевищує 65432 (золотих).
Вихідні дані
Перший рядок має містити два невід'ємних цілих числа - виграші (кількості зібраних монет) першого та другого гравців відповідно.
Другий рядок має містити послідовність символів, що описують напрям ходів пішака (від першого до останнього) для досягнення цього результату: u - вгору (від анґлійського up), r - праворуч (від анґлійського right).