Mirror Rays

There is a rectangular box with N rows and M columns. Each cell either has no mirror or contains one /-shaped mirror.

There is one hole on the border for each cell touching the border. The holes are numbered from 1 to 2N+2M as follows: first the left side from top to bottom, then the bottom side from left to right, then the right side from bottom to top, and finally the top side from right to left.

When light is shot inward through a hole, it passes straight through empty cells and reflects when it meets a /-shaped mirror. For every hole, determine the hole through which the light leaves the box.

The first line contains two integers N and M (1 <= N, M <= 1,000).

Each of the next N lines contains M integers describing the box. A 1 means that the cell contains a /-shaped mirror, and a 0 means that the cell has no mirror.

For holes 1 through 2N+2M, output in order the number of the hole through which the light exits. Separate the numbers with spaces on one line.