Private interests#7205
On a rectangular table with rows and 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.
The first line contains the natural numbers and . For each from to , the (j + 1)-th line provides non-negative integers representing the coin values in the cells of the -th row, listed from left to right. The total number of these integers does not exceed , and the maximum possible winnings do not exceed (in gold coins).
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.
Example 1