Jaemin a développé une application de jeu de réflexion.

Une bille est placée sur une case d’une grille. Vous pouvez la faire rouler vers le haut, le bas, la gauche ou la droite. La bille roule dans cette direction jusqu’à heurter un mur ou le bord. Certaines cases contiennent des étoiles, et le joueur obtient une étoile lorsque la bille s’arrête sur sa case ou la traverse. Le but du jeu est d’obtenir toutes les étoiles de la grille.

Cette application possède un éditeur de niveaux qui permet aux joueurs de créer et de partager leurs propres niveaux. Un jour, quelqu’un a suggéré : « Ajoute une fonctionnalité pour vérifier si mon niveau peut être résolu, s’il te plaît ! » Plus facile à dire qu’à faire, n’est-ce pas ?

Entrée

La première ligne de l’entrée contient deux entiers, $H$ (hauteur) et $W$ (largeur). ($1 \leq H, W \leq 50$) Chacune des $H$ lignes suivantes contient une chaîne de longueur $W$ décrivant une ligne de la grille. « # » représente un mur, « . » une case vide, « O » une bille et « * » une étoile. Il y a exactement une bille et au moins une étoile dans la grille.

Sortie

Affichez « YES » s’il est possible d’obtenir toutes les étoiles, et « NO » sinon.

Exemples

Entrée 1

3 7
#..O..#
#.###.#
*..#..*

Sortie 1

NO

Entrée 2

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

Sortie 2

YES