Plus Shape in a Picture

Interview

Time limit1sMemory limit1024 MB

Summary

Decide whether a grid of stars and dots contains exactly one plus shape whose four arms each have at least one star.

Level: Easy3 of 10
Topics: Implementation, Matrix
Solved: No attempts yet

Problem

You are given a picture of size $w \times h$ . Determine whether the picture contains a single "+" shape. A "+" shape is defined as follows:

The shape has one center cell that is non-empty.
In each of the four directions (left, right, up, down) from the center, there is a run of at least one consecutive non-empty cell.
All other cells are empty.

Input

The first line contains two integers $h$ and $w$ ( $1 \le h$ , $w \le 500$ ), the height and the width of the picture. The $i$ -th of the next $h$ lines contains a string $s_{i}$ of length $w$ made of "." and "*". "." denotes an empty cell and "*" denotes a non-empty cell.

Output

If the picture satisfies all the conditions, print "YES". Otherwise, print "NO".

Hint

In the first example, the picture contains one "+".

In the second example, the two vertical branches are in different columns.

In the third example, there is a dot outside the shape.

In the fourth example, the two vertical branches are 2 cells wide.

In the fifth example, there are two shapes.

In the sixth example, there is an empty cell inside the shape.

Examples5

Example 1

Input

5 6
......
..*...
.****.
..*...
..*...

Expected output

YES

Example 2
Input
```
3 5
..*..
****.
.*...
```
Expected output
```
NO
```

Example 3

Input

7 7
.......
...*...
..****.
...*...
...*...
.......
.*.....

Expected output

NO

Example 4

Input

5 6
..**..
..**..
******
..**..
..**..

Expected output

NO

Example 5
Input
```
3 7
.*...*.
***.***
.*...*.
```
Expected output
```
NO
```