#103Easy
Row with balanced signs
Time: 1 s · Memory: 256 MB
- Matrices
Statement
You are given an matrix. Find the number of the first row that has as many positive elements as negative ones (rows are numbered from ). Zeros do not count: a row of zeros only qualifies too (). If there is no such row — .
Input format
The first line contains and (). Each of the next lines contains integers ().
Output format
A single integer — the row number or .
Examples
Input
3 3 -1 -2 3 -4 0 6 7 8 9
Output
2
Input
3 3 1 2 3 4 5 6 7 8 9
Output
0
Note
For each row keep two counters (or one: for a positive, for a negative). Stop at the first match. In the first example row 1 has two negatives and one positive, row 2 has one of each: the answer is .
