Monkeying Around

Interview

Time limit1sMemory limit1024 MB

Summary

Each monkey has one unknown jump that makes its total displacement zero. Find the monkey whose average height over the M jumps is highest.

Level: Easy3 of 10
Topics: Math, Simulation
Solved: No attempts yet

Problem

$N$ baby monkeys are playing in treetops. They all start from the same height, and each of them finishes where it started from. Each monkey makes $M$ jumps, and each jump is an integer showing how many centimeters higher or lower the monkey moved. For each monkey, the height of one jump is unknown and is written as zero in the input. Assuming the jumps take place after equal time intervals, find the monkey who was on the highest level on average.

Input

The first line contains $N$ ( $1 \le N \le 100$ ), the number of monkeys, and $M$ ( $1 \le M \le 100$ ), the number of jumps. Each of the following $N$ lines contains $M$ space-separated integers $A_i$ ( $-200 \le A_i \le 200$ ). $A_i$ is how many centimeters higher the corresponding monkey moved with the corresponding jump, and a negative value means it moved lower. Each line contains exactly one $0$ , which marks the unknown jump.

Output

Output exactly one integer, the index of the monkey who was on the highest level on average. The monkeys are indexed $1, \ldots, N$ in the order their data are given. When computing the average, include the common final height after the last jump, but exclude the initial height before the first jump. If several monkeys have the maximal average level, output the index of any of them.

Examples2

Example 1
Input
```
2 2
1 0
0 3
```
Expected output
```
1
```
Example 2
Input
```
3 4
-2 4 0 6
-3 0 -8 9
4 5 -7 0
```
Expected output
```
3
```