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