#include <bits/stdc++.h>
using namespace std;
bool comp(pair<long long, char> aa, pair<long long, char> bb) {
  if (aa.first != bb.first) return aa.first > bb.first;
  return aa.second < bb.second;
}
bool comp1(pair<long long, char> aa, pair<long long, char> bb) {
  if (aa.first != bb.first) return aa.first < bb.first;
  return aa.second > bb.second;
}
bool comp2(pair<long long, long long> aa, pair<long long, long long> bb) {
  if (aa.first != bb.first) return aa.first > bb.first;
  return aa.second < bb.second;
}
bool comp3(pair<long long, long long> aa, pair<long long, long long> bb) {
  if (aa.first != bb.first) return aa.first < bb.first;
  return aa.second > bb.second;
}
long long sumg(long long i) { return ((i * (i + 1))) + ((i * (i - 1)) / 2); }
bool yo(string str1, string str2, long long m, long long n) {
  if (m == 0) return true;
  if (n == 0) return false;
  if (str1[m - 1] == str2[n - 1]) return yo(str1, str2, m - 1, n - 1);
  return yo(str1, str2, m, n - 1);
}
long long rup(long long ik, long long ikk) {
  if (ik % ikk == 0)
    return ik / ikk;
  else
    return (ik / ikk) + 1;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
long long area(long long p1, long long p2, long long p3, long long q1,
               long long q2, long long q3) {
  long long xx;
  xx = (p1 * q2) - (p2 * q1) + (p2 * q3) - (p3 * q2) + (p3 * q1) - (p1 * q3);
  return abs(xx);
}
pair<long long, long long> kop(long long n1) {
  long long i;
  long long n = n1;
  long long xx = n1;
  set<long long> s1;
  map<long long, long long> m;
  for (i = 2; i <= sqrt(n); i = i + 1) {
    while (n % i == 0) {
      s1.insert(i);
      m[i] += 1;
      n /= i;
    }
  }
  if (n > 1) {
    s1.insert(n);
    m[n] += 1;
  }
  long long fact = 1;
  vector<long long> v;
  long long pp = 1000000000000000007;
  long long h = 0;
  long long xx1 = -1;
  set<long long> s2;
  for (i = 1; i <= sqrt(xx); i = i + 1) {
    if (xx % i == 0) {
      s2.insert(i);
      s2.insert(xx / i);
    }
  }
  for (auto u : s1) {
    fact *= (m[u] + 1);
  }
  for (auto u : s2) {
    if (h > 0) pp = min(pp, u - xx1);
    xx1 = u;
    h++;
    fact *= (m[u] + 1);
  }
  m.clear();
  s1.clear();
  v.clear();
  s2.clear();
  pair<long long, long long> jh = make_pair(fact, pp);
  return jh;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long t = 1;
  while (t--) {
    long long w, h;
    cin >> w >> h;
    long long i, j;
    char numbers[505][505] = {};
    for (i = 1; i <= w; i = i + 1) {
      for (j = 1; j <= h; j = j + 1) {
        cin >> numbers[i][j];
      }
    }
    long long f = 0;
    long long k;
    map<pair<long long, long long>, long long> m;
    long long pp = -1, qq = -1;
    for (i = 1; i <= w; i = i + 1) {
      for (j = 1; j <= h; j = j + 1) {
        if (numbers[i][j] == '*' && (j - 1 >= 1 && numbers[i][j - 1] == '*') &&
            (j + 1 <= h && numbers[i][j + 1] == '*') &&
            (i - 1 >= 1 && numbers[i - 1][j] == '*') &&
            (i + 1 <= w && numbers[i + 1][j] == '*')) {
          pp = i;
          qq = j;
          f++;
        }
        if (f == 1 && i == pp && j == qq) {
          m[make_pair(i, j)] = 1;
          for (k = j - 1; k >= 1; k--) {
            if (numbers[i][k] == '*')
              m[make_pair(i, k)] = 1;
            else
              break;
          }
          for (k = i - 1; k >= 1; k--) {
            if (numbers[k][j] == '*')
              m[make_pair(k, j)] = 1;
            else
              break;
          }
          for (k = j + 1; k <= h; k = k + 1) {
            if (numbers[i][k] == '*')
              m[make_pair(i, k)] = 1;
            else
              break;
          }
          for (k = i + 1; k <= w; k = k + 1) {
            if (numbers[k][j] == '*')
              m[make_pair(k, j)] = 1;
            else
              break;
          }
        }
      }
    }
    long long g = 0;
    for (i = 1; i <= w; i = i + 1) {
      for (j = 1; j <= h; j = j + 1) {
        if (numbers[i][j] == '*' && m[make_pair(i, j)] == 0) {
          g++;
          break;
        }
      }
    }
    if (f == 1 && g == 0)
      cout << "YES"
           << "\n";
    else
      cout << "NO"
           << "\n";
  }
}

### Prompt

Please provide a cpp coded solution to the problem described below:

You have a given picture with size w × h. Determine if the given picture has a single "+" shape or not. A "+" shape is described below:

  * A "+" shape has one center nonempty cell. 
  * There should be some (at least one) consecutive non-empty cells in each direction (left, right, up, down) from the center. In other words, there should be a ray in each direction. 
  * All other cells are empty. 



Find out if the given picture has single "+" shape.

Input

The first line contains two integers h and w (1 ≤ h, w ≤ 500) — the height and width of the picture.

The i-th of the next h lines contains string s_{i} of length w consisting "." and "*" where "." denotes the empty space and "*" denotes the non-empty space.

Output

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

You can output each letter in any case (upper or lower).

Examples

Input


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


Output


YES


Input


3 5
..*..
****.
.*...


Output


NO


Input


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


Output


NO


Input


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


Output


NO


Input


3 7
.*...*.
***.***
.*...*.


Output


NO


Input


5 10
..........
..*.......
.*.******.
..*.......
..........


Output


NO

Note

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

In the second example, two vertical branches are located in a different column.

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

In the fourth example, the width of the two vertical branches is 2.

In the fifth example, there are two shapes.

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
bool comp(pair<long long, char> aa, pair<long long, char> bb) {
  if (aa.first != bb.first) return aa.first > bb.first;
  return aa.second < bb.second;
}
bool comp1(pair<long long, char> aa, pair<long long, char> bb) {
  if (aa.first != bb.first) return aa.first < bb.first;
  return aa.second > bb.second;
}
bool comp2(pair<long long, long long> aa, pair<long long, long long> bb) {
  if (aa.first != bb.first) return aa.first > bb.first;
  return aa.second < bb.second;
}
bool comp3(pair<long long, long long> aa, pair<long long, long long> bb) {
  if (aa.first != bb.first) return aa.first < bb.first;
  return aa.second > bb.second;
}
long long sumg(long long i) { return ((i * (i + 1))) + ((i * (i - 1)) / 2); }
bool yo(string str1, string str2, long long m, long long n) {
  if (m == 0) return true;
  if (n == 0) return false;
  if (str1[m - 1] == str2[n - 1]) return yo(str1, str2, m - 1, n - 1);
  return yo(str1, str2, m, n - 1);
}
long long rup(long long ik, long long ikk) {
  if (ik % ikk == 0)
    return ik / ikk;
  else
    return (ik / ikk) + 1;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
long long area(long long p1, long long p2, long long p3, long long q1,
               long long q2, long long q3) {
  long long xx;
  xx = (p1 * q2) - (p2 * q1) + (p2 * q3) - (p3 * q2) + (p3 * q1) - (p1 * q3);
  return abs(xx);
}
pair<long long, long long> kop(long long n1) {
  long long i;
  long long n = n1;
  long long xx = n1;
  set<long long> s1;
  map<long long, long long> m;
  for (i = 2; i <= sqrt(n); i = i + 1) {
    while (n % i == 0) {
      s1.insert(i);
      m[i] += 1;
      n /= i;
    }
  }
  if (n > 1) {
    s1.insert(n);
    m[n] += 1;
  }
  long long fact = 1;
  vector<long long> v;
  long long pp = 1000000000000000007;
  long long h = 0;
  long long xx1 = -1;
  set<long long> s2;
  for (i = 1; i <= sqrt(xx); i = i + 1) {
    if (xx % i == 0) {
      s2.insert(i);
      s2.insert(xx / i);
    }
  }
  for (auto u : s1) {
    fact *= (m[u] + 1);
  }
  for (auto u : s2) {
    if (h > 0) pp = min(pp, u - xx1);
    xx1 = u;
    h++;
    fact *= (m[u] + 1);
  }
  m.clear();
  s1.clear();
  v.clear();
  s2.clear();
  pair<long long, long long> jh = make_pair(fact, pp);
  return jh;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long t = 1;
  while (t--) {
    long long w, h;
    cin >> w >> h;
    long long i, j;
    char numbers[505][505] = {};
    for (i = 1; i <= w; i = i + 1) {
      for (j = 1; j <= h; j = j + 1) {
        cin >> numbers[i][j];
      }
    }
    long long f = 0;
    long long k;
    map<pair<long long, long long>, long long> m;
    long long pp = -1, qq = -1;
    for (i = 1; i <= w; i = i + 1) {
      for (j = 1; j <= h; j = j + 1) {
        if (numbers[i][j] == '*' && (j - 1 >= 1 && numbers[i][j - 1] == '*') &&
            (j + 1 <= h && numbers[i][j + 1] == '*') &&
            (i - 1 >= 1 && numbers[i - 1][j] == '*') &&
            (i + 1 <= w && numbers[i + 1][j] == '*')) {
          pp = i;
          qq = j;
          f++;
        }
        if (f == 1 && i == pp && j == qq) {
          m[make_pair(i, j)] = 1;
          for (k = j - 1; k >= 1; k--) {
            if (numbers[i][k] == '*')
              m[make_pair(i, k)] = 1;
            else
              break;
          }
          for (k = i - 1; k >= 1; k--) {
            if (numbers[k][j] == '*')
              m[make_pair(k, j)] = 1;
            else
              break;
          }
          for (k = j + 1; k <= h; k = k + 1) {
            if (numbers[i][k] == '*')
              m[make_pair(i, k)] = 1;
            else
              break;
          }
          for (k = i + 1; k <= w; k = k + 1) {
            if (numbers[k][j] == '*')
              m[make_pair(k, j)] = 1;
            else
              break;
          }
        }
      }
    }
    long long g = 0;
    for (i = 1; i <= w; i = i + 1) {
      for (j = 1; j <= h; j = j + 1) {
        if (numbers[i][j] == '*' && m[make_pair(i, j)] == 0) {
          g++;
          break;
        }
      }
    }
    if (f == 1 && g == 0)
      cout << "YES"
           << "\n";
    else
      cout << "NO"
           << "\n";
  }
}

```