391. Rat Chases its cheese

0

Medium

You are given an N*M grid. Each cell (i,j) in the grid is either blocked, or empty. The rat can move from a position towards left, right, up or down on the
grid.

Initially rat is on the position (1,1). It wants to reach position (N,M) where it's cheese is waiting for. If a path exists-it is always unique. Find that path and help the rat reach its cheese.

Initially rat is on the position (1,1). It wants to reach position (N,M) where it's cheese is waiting for. If a path exists-it is always unique. Find that path and help the rat reach its cheese.

Input Format

First line contains 2 integers N and M denoting the rows and columns in the grid.

Next N line contains M characters each. An 'X' in position (i,j) denotes that the cell is blocked and ans 'O' denotes that the cell is empty.

Next N line contains M characters each. An 'X' in position (i,j) denotes that the cell is blocked and ans 'O' denotes that the cell is empty.

Output Format

Print N lines, containing M integers each. A 1 at a position (i,j) denotes that the (i,j)

If a path does not exits then print "NO PATH FOUND"

^{th}cell is covered in the path and a 0 denotes that the cell is not covered in the path.If a path does not exits then 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