Rat's Quest for Cheese

784. Rat's Quest for Cheese

0

Medium

Given a grid of size N*M, where each cell (i,j) is either blocked or empty, a rat starts at position (1,1) and wants to reach position (N,M) where its cheese is waiting. The rat can move left, right, up, or down on the grid. If a path exists, it is always unique. Find that path and help the rat reach its cheese.

Input Format

The first line contains two integers N and M, representing the number of rows and columns in the grid. The next N lines contain M characters each. An 'X' in position (i,j) denotes a blocked cell, while 'O' denotes an empty cell.

Output Format

Print N lines, each containing M integers. A 1 at position (i,j) indicates that the (i,j)th cell is covered in the path, while a 0 indicates that the cell is not covered. If a path does not exist, print "NO PATH FOUND".

Example

Input

5 4 OXOO OOOX XOXO XOOX XXOO

Output

1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1

Constraints

1 <= N , M <= 10

Loading...

View Submissions

Console