When winter came and there was little to do in Prostokvashino, Sharik and Matroskin spent all their days playing board games. But they quickly got tired of chess, checkers, crosses and dominoes, and they had no other games. So they came up with a new game.
They write out 100 numbers on the stove with charcoal. Then, in turn, each of them selects a number from the right or left edge, adds it to their sum, and erases the number. Starts the game Matroskin. He wins if he can collect an amount no less than Sharik. Based on the given numbers, determine who will win in the optimal game.
Input
A single line contains 100 space-separated numbers a
i (1≤a
i≤1000)
Imprint
In response, print Matroskin if Matroskin wins, otherwise print Sharik. If Matroskin wins, then on the next line print Matroskin's optimal first move: if he must take the leftmost number, then print "left", if he must take the rightmost number — print "right". If it doesn't matter to Matroskin which number to take, print any of the words «left» and «right».
Examples
| # |
Input |
Output |
| 1 |
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
| Matroskin
right |