Jaemin hat eine Rätselspiel-App entwickelt.

Auf einem Feld eines Gitters liegt eine Kugel. Du kannst die Kugel nach oben, unten, links oder rechts rollen lassen. Die Kugel rollt in dieser Richtung, bis sie gegen eine Wand oder die Begrenzung stößt. Auf manchen Feldern befinden sich Sterne. Der Spieler erhält einen Stern, wenn die Kugel auf dessen Feld anhält oder darüberrollt. Das Ziel des Spiels ist es, alle Sterne im Gitter einzusammeln.

Diese App hat einen Leveleditor, mit dem Spieler eigene Level erstellen und teilen können. Eines Tages schlug jemand vor: „Bitte füge eine Funktion hinzu, die prüft, ob mein Level lösbar ist!“ Leichter gesagt als getan, oder?

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen, $H$ (Höhe) und $W$ (Breite). ($1 \leq H, W \leq 50$) Jede der folgenden $H$ Zeilen enthält eine Zeichenkette der Länge $W$, die eine Zeile des Gitters beschreibt. „#“ steht für eine Wand, „.“ für ein leeres Feld, „O“ für eine Kugel und „*“ für einen Stern. Im Gitter gibt es genau eine Kugel und mindestens einen Stern.

Ausgabe

Gib „YES“ aus, wenn es möglich ist, alle Sterne einzusammeln, andernfalls „NO“.

Beispiele

Eingabe 1

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

Ausgabe 1

NO

Eingabe 2

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

Ausgabe 2

YES