Private interests
On a rectangular table with m rows and n columns, coins are placed on each cell. Two players take turns moving a pawn, either one cell to the right or one cell up. The game begins with the first player starting from the bottom-left corner of the table. The game concludes when the pawn reaches either the top row or the rightmost column. Each player:
cannot communicate with the other player;
knows the distribution of coins before the game starts;
is aware of the pawn's current position at all times;
collects coins from each cell the pawn lands on;
aims to maximize their total coin collection by the end of the game;
will only move right if moving up results in a lower final profit;
understands the opponent's strategies and intentions;
knows that the opponent will also act with the same understanding.
Write a program to predict the outcome of the game and the path of the pawn.
Input
The first line contains the natural numbers m and n. For each j from 1 to m, the (j + 1)-th line provides non-negative integers representing the coin values in the cells of the j-th row, listed from left to right. The total number of these integers does not exceed 12346, and the maximum possible winnings do not exceed 65432 (in gold coins).
Output
The first line should display two non-negative integers, representing the total coins collected by the first and second players, respectively.
The second line should show a sequence of characters indicating the pawn's moves (from start to finish) to achieve this result: u for up, r for right.