Phantom Thief Gangsan

I will drop by tonight.

Gangsan, phantom thief

Taekhee, the museum director, read the notice and panicked. Gangsan is the worst phantom thief in the world, and a place that receives one of his notices is left without a single treasure. Taekhee still refused to give up. He spent his own money on a huge pile of the newest location trackers, and he plans to catch Gangsan with them.

Taekhee's museum is a grid with $N$ rows and $M$ columns. The cell in row $i$ and column $j$ is called $(i, j)$. Jewels lie around the museum, and Taekhee installed trackers on some of the cells that hold no jewel. If Gangsan walks out carrying a tracker, his long career as a thief ends with the police catching him.

Gangsan already found out that Taekhee installed many trackers. To steal every jewel in the museum, he plans to use the strategy below.

• Pick one row or one column. Walk the chosen row from its leftmost cell to its rightmost cell, or the chosen column from its topmost cell to its bottommost cell, passing every cell and handling these two tasks.
  • When he passes a cell that holds a jewel or a tracker, he must take that jewel or tracker.
  • When he is passing a cell that held a tracker at the start but is empty now, and he carries at least one tracker, he must put exactly one tracker down on that cell.
• If he has every jewel in hand and carries 0 trackers, he leaves the museum. Otherwise he picks one more row or column and repeats the tasks above.

Taekhee is no pushover either. He saw through the strategy, so for every jewel that is not a tracker he arranged that a guard can be dispatched to that spot the moment the jewel is stolen. That adds one restriction.

• Once Gangsan steals a jewel that is not a tracker, he can never enter the row or the column that contains that cell again.

Here is one example.

In the picture the museum is a grid with 4 rows and 5 columns. Jewels lie at $(1, 5)$, $(3, 4)$ and $(4, 3)$, and trackers lie at $(1, 1)$, $(2, 2)$, $(2, 5)$ and $(4, 4)$. In this situation Gangsan can steal every jewel in the following order.

1. Walk row 4, taking the jewel at $(4, 3)$ and the tracker at $(4, 4)$.
2. Walk column 4, taking the jewel at $(3, 4)$ and putting the tracker back down on $(4, 4)$.
3. Walk row 1, taking the tracker at $(1, 1)$ and the jewel at $(1, 5)$.
4. Enter column 1 and put the tracker back down on $(1, 1)$. Gangsan has to pass $(1, 1)$, $(2, 1)$, $(3, 1)$ and $(4, 1)$, every one of them. Visiting only $(1, 1)$ and stepping straight back out is impossible.

The trackers at $(2, 2)$ and $(2, 5)$ were never touched, so they cause no trouble. In step 4 he cannot enter row 1 instead of column 1. The jewel at $(1, 5)$ is already stolen, so a guard stands in row 1.

Gangsan does not compromise. He wants to carry away every last jewel in the museum and also avoid a police chase caused by a tracker.

Decide whether Gangsan reaches his goal today.

The first line contains the number of rows $N$ and the number of columns $M$ of the museum. ($1 \le N, M \le 10^3$)

Each of the next $N$ lines contains $M$ characters describing one row of the museum. Each character is ., * or #. A . is a cell with nothing on it, a * is a cell that holds a jewel, and a # is a cell that holds a tracker.

The museum holds at least one jewel.

Print 1 on the first line if Gangsan can reach his goal, and 0 otherwise.