This problem is revised from example 6.26 of the textbook.
We place a number of two-sided mirrors at a −45° angle ("\" orientation) inside a rectangular room of width W and depth D.
The room boundary contains 2 × (W + D) windows, numbered in counterclockwise order starting from 0 at the top edge.
When a light ray enters the room from one window, it travels straight through the grid.
If the ray passes through an empty cell (0), it continues in the same direction.
If the ray encounters a mirror (1), it is reflected according to the −45° mirror rule:
Down → Left
Left → Down
Up → Right
Right → Up
The ray will eventually leave the room through another boundary window.
Your task is to simulate the ray’s path and determine, for each entry window, the corresponding exit window.
The first line contains two integers W and D — the width and depth of the room.
The next D lines each contain W integers (0 or 1).
1 means the cell contains a −45° mirror ("\").
0 means the cell is empty.
The room coordinates are arranged so that the top-left corner is (0,0).
Input rows are given from top to bottom.
Constraint
1 ≤ W, D ≤ 500
Print 2 × (W + D) lines.
The i-th line contains the window number where a ray entering from window i will exit.