Operation Paratrooper

In order to infiltrate enemy territory, the commander has decided to deploy paratroopers. However, the enemy country is characterized by extremely strong winds that keep the paratrooper circling at the same altitude until he is blown into a calm (no-wind) zone. In this problem, you are given a grid representing the wind conditions at different altitudes. The paratrooper starts at the top row at a specified column. For each row, while the wind in the current cell is not 0, the paratrooper is pushed horizontally according to the wind value. When a calm zone (cell with value 0) is finally reached, he drops to the next row (keeping his current column). Note that the grid is cyclic horizontally; that is, if the paratrooper is pushed off one end, he reappears at the opposite end.

Your task is to determine the final column position where the paratrooper lands after processing all rows.

Movement details:

• Let N be the number of rows and M be the number of columns. The rows are numbered from 1 to N from top to bottom and the columns from 1 to M from left to right.
• If the paratrooper is at row i and column c, and the wind value in that cell is w ≠ 0, then his new column becomes c' = c + w. If c' exceeds M, subtract M until it falls within 1 and M; if c' is less than 1, add M until it falls within the range.
• He repeats the horizontal movement in the same row until he lands in a calm zone (a cell with 0). Then, if there is a next row, he drops down to row i+1, maintaining his column position.
• This process continues until he has processed all N rows. The final column in row N is the answer.

inputFormat

The input begins with a line containing three integers: N, M, and S, where N is the number of rows, M is the number of columns, and S is the starting column (1-indexed) in the first row. The following N lines each contain M integers. Each integer represents the wind value in that cell; a nonzero value means the wind pushes the paratrooper horizontally (positive for right and negative for left), while 0 indicates a calm zone.

outputFormat

Output a single integer: the final column position (1-indexed) where the paratrooper lands after processing all N rows.

sample

3 5 3
1 0 2 -1 0
0 0 0 0 0
0 0 -2 1 0

5