You are given a matrix $n*m$. The matrix rows are numbered from $1$ to $n$ from top to bottom and the matrix columns are numbered from $1$ to $m$ from left to right. The cells of the field at the intersection of the $x^{th}$ row and the $y^{th}$column has coordinates $(x, y)$.

Every cell is empty or blocked. For every cell $(x, y)$, determine if you change the state of cell $(x, y)$(empty to blocked or blocked to empty), then is it possible to reach cell $(n, m)$ from $(1, 1)$ by going only down and right.

Input format

• The first line contains two space-separated numbers $n, m$  denoting the number of rows and columns.
• Next $n$ lines contain symbols. If the symbol on $(x, y)$ is '#', then the cell is blocked. Otherwise, if the symbol is '.', then the cell is empty.

Output format

Print $n$  lines where every line contains $m$ numbers. Print 0 if it is impossible to reach $(n, m)$. Otherwise, print 1.

Constraints

$1 \le n, m \le 10^3$