---
# System prepended metadata

title: Untitled

---

**Maze - 1**

There's a 2D map of a maze in the form of a grid. The grid shows the maze is open at the top and the bottom representing the entry and exit points respectively.

Each cell in the grid has a wall in diagonal direction. If the wall is from top-left corner to bottom-right corner of the cell, it is represented as **1**. If the wall is from top-right corner to bottom-left corner of the cell, it is represented as **-1**.

The robot can enter the maze from any cell from the top row. If two adjacent cells have diagonal wall in same direction, the robot will get to pass through the cell, otherwise, it forms a dead-end to reach the bottom.

For example, consider the following `M x N` matrix representing the 2D map of a maze,

4 5
1  1  1  1  1
-1 -1 -1 -1 -1
1  1  1 -1  1
-1 -1 -1 -1 -1

<img src="https://new-assets.ccbp.in/frontend/content/python-idp/maze-v1-description-1.png" widthPercent='60'/>

The robot can enter the maze through any cell numbered from **0** to **4** in the top row.

<img src="https://new-assets.ccbp.in/frontend/content/python-idp/maze-v1-description-2.png" widthPercent='60'/>

In the given image,

- The robots that enter from the cells **0** and **1** in the top row, exit at cells **0** and **1** in the last row respectively.
- The robots that enter from the cells **2** and **3** in the top row will be blocked.
- The robot that enter from cell **4** in the top row will be blocked by the border.

Write a program that reads two numbers **M**, **N** and a **M x N** matrix representing the direction of walls, and prints the list of exit points (cell number in the last row) for each of the **N** entry points in the maze, if an entry point leads to a dead end, print **-1**.

<MultiLineNote>
    Exit points range from cells **0** to **N-1**.
</MultiLineNote>

---

#### Input

The first line of input contains two space-separated integers representing `M` and `N` respectively.
The next `M` lines of input contain `N` space-separated integers.

---

#### Output

The output should be a single line containing a list of integers representing the exit points for each of the **N** entry points in the maze.