O-Super Dama
On a big rectangular chess table R by [] stand enemies or own figures. Every figure has life value enumerated with integer Vi. Enemies have positive and own figures have negative values. Zero means that this field is empty.
Super queen make parachute jump from GligBull GT helicopter and land. She can land either on empty field or on field immediately near the table. From landing place, super queen must choose one of 8 directions (up, up-right, right, down-right, down, down-left, left, up-left), take all figures in this direction, take over their life values and increase her own life value. (Now we see why she is "super", because ordinary queen can take only one figure.)
Your task is to choose one field to land queen and one direction in order to maximize life value for super queen.
In next R rows there are C space-separated integers Vi (-10^9 <= Vi <= 10^9) representing life value of figure on this field. Positive Vi describe enemies and negative own figures.
In second row of output write direction in which super queen can raise her life value to maximum. If multiple solutions exist, write any of them. Field coordinates must be between 0 and 1001 inclusively, for both row and column.
NOTICE: If queen take her own figure, as penalty for collateral damage her life value is decreasing. Also, if this is better for her, she can "shot" away of table.
[c]Input:
4 10
1 2 3 4 5 6 7 8 9 10
0 -7 5 4 0 5 -1 0 15 1
1 1 1 1 1 1 1 20 1 1
9 -9 8 7 6 5 11 -6 8 -5
Output:
5 6
up-right
Explanation: maximum increasing her life value is 56. She can realize this on two ways. To land on field (5,6) and take all figures on “up-right” direction or land on (0,11) and take all figures on “down-left” direction.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.