Dev, Please Add This!

Time limit1sMemory limit256 MB

Summary

Decide whether a ball that rolls until hitting a wall or edge can collect every star on a grid.

Level: Medium7 of 10
Topics: Graph, BFS, Simulation, Bit manipulation
Solved: No attempts yet

Problem

Jaemin wrote a puzzle game app.

A ball sits on a grid. You can roll the ball up, down, left, or right, and once it starts rolling it keeps going in that direction until it hits a wall or reaches the edge of the grid. Some cells hold a star, and the user collects that star when the ball stops on the cell or passes over it. The goal is to collect every star on the grid.

The app has a level editor, so users build their own levels and share them. One day Jaemin got a request: "Please add a feature that checks whether the level I made can be solved!" Well, that is easy to say...

Given a grid, decide whether every star can be collected.

Input

The first line contains the height $H$ and the width $W$ of the grid. ( $1 \leq H, W \leq 50$ )

Each of the next $H$ lines contains a string of length $W$ describing one row of the grid, in order. # is a wall, . is an empty cell, O is the ball, and * is a star. The grid holds exactly one ball and at least one star.

Output

Print YES if every star can be collected, and NO otherwise.

Examples2

Example 1
Input
```
3 7
#..O..#
#.###.#
*..#..*
```
Expected output
```
NO
```

Example 2

Input

6 6
*..*##
..O...
*..*#.
####*.
......
.....#

Expected output

YES