Fox Ciel has a board with n rows and n columns. So, the board consists of n × n cells. Each cell contains either a symbol '.', or a symbol '#'.

A cross on the board is a connected set of exactly five cells of the board that looks like a cross. The picture below shows how it looks.[Image]

Ciel wants to draw several (may be zero) crosses on the board. Each cross must cover exactly five cells with symbols '#', and any cell with symbol '#' must belong to some cross. No two crosses can share a cell.

Please, tell Ciel if she can draw the crosses in the described way.


-----Input-----

The first line contains an integer n (3 ≤ n ≤ 100) — the size of the board.

Each of the next n lines describes one row of the board. The i-th line describes the i-th row of the board and consists of n characters. Each character is either a symbol '.', or a symbol '#'.


-----Output-----

Output a single line with "YES" if Ciel can draw the crosses in the described way. Otherwise output a single line with "NO".


-----Examples-----
Input
5
.#...
####.
.####
...#.
.....

Output
YES

Input
4
####
####
####
####

Output
NO

Input
6
.#....
####..
.####.
.#.##.
######
.#..#.

Output
YES

Input
6
.#..#.
######
.####.
.####.
######
.#..#.

Output
NO

Input
3
...
...
...

Output
YES



-----Note-----

In example 1, you can draw two crosses. The picture below shows what they look like.[Image]

In example 2, the board contains 16 cells with '#', but each cross contains 5. Since 16 is not a multiple of 5, so it's impossible to cover all.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
arr = []
for i in range(n):
    arr.append(list(input()))
k = 1
for i in range(n):
    for j in range(n):
        if arr[i][j] == '#':
            if i+2<=n-1 and j-1>=0 and j+1<=n-1:
                if arr[i+1][j-1] == '#' and arr[i+1][j] == '#' and arr[i+1][j+1] == '#' and arr[i+2][j] == '#':
                    arr[i+1][j-1] = '.'
                    arr[i+1][j] = '.'
                    arr[i+1][j+1] = '.'
                    arr[i+2][j] = '.'
                    arr[i][j] = '.'
                else:
                    k = 0
                    break
            else:
                k = 0
                break
if k == 1:
    print('YES')
else:
    print('NO')

def deleteCross(m, i, j):
    if i<=0 or j<=0 or i>=len(m)-1 or j>=len(m)-1: return (m,False)
    if m[i][j] == r'#' and m[i+1][j] == r'#' and m[i-1][j] == r'#' and m[i][j+1] == r'#' and m[i][j-1] == r'#':
        m[i][j] = m[i+1][j] = m[i-1][j] = m[i][j+1] = m[i][j-1] = '.'
        return (m, True)
    return (m, False)

def solve(m):
    for i in range(len(m)):
        for j in range(len(m)):
            if m[i][j] == r'#':
                r1 = deleteCross(m, i+1, j)
                if not r1[1]: return False
                m = r1[0]
    return True

n = int(input())
m = []
for i in range(n):
    m.append(list(input()))
print('YES' if solve(m) else 'NO')


n = int(input())
m = [list(input()) for i in range(n)]

def test(m, n):
  for r in range(n):
    for c in range(n):
      if m[r][c] == "#":
        if c == 0 or c == n - 1 or r >= n - 2:
          return False
        elif (m[r+1][c-1] == "#") and (m[r+1][c] == "#") and (m[r+1][c+1] == "#") and (m[r+2][c] == "#") :
             m[r+1][c-1] = "."
             m[r+1][c]   = "."
             m[r+1][c+1] = "."
             m[r+2][c]   = "."
        else:
          return False
  return True
  
print("YES" if test(m, n) else "NO")

n=int(input())
a=[[] for i in range(n)]
for i in range(n):
    s=input().strip()
    for j in s:
        a[i]+=[j]
kr=0
for i in range(n):
    for j in range(n):
        #print(i,j)
        if a[i][j]=='#':
            kr+=1
        if 0<i<n-1 and 0<j<n-1 and a[i][j]=='#':
            if a[i][j-1]==a[i][j+1]==a[i-1][j]==a[i+1][j]=='#':
                kr-=3
                a[i][j-1],a[i][j+1],a[i-1][j],a[i+1][j],a[i][j]='.','.','.','.','.'
if kr:
    print('NO')
else:
    print('YES')

import sys

n = int(sys.stdin.readline())
lines = []
for i in range(n):
    lines.append(list(sys.stdin.readline().strip()))
    
def check(lines, x, y, n):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False
    if lines[x][y] != '#':
        return False
    lines[x][y] = '.'
    return True
    
def tryPaint(lines, i, j, n):
    return check(lines, i, j, n) and \
        check(lines, i-1, j+1, n) and \
        check(lines, i, j+1, n) and \
        check(lines, i+1, j+1, n) and \
        check(lines, i, j+2, n)
    
failed = False
    
for j in range(n):
    for i in range(n):
        if lines[i][j] == '#':
            if not tryPaint(lines, i, j, n):
                failed = True
                break
        if failed:
            break

if not failed:
    for i in range(n):
        if "#" in set(lines[i]):
            failed = True
            break

if failed:
    print("NO")
else:
    print("YES")
            
      


n=int(input())
a=[]
for i in range(n):
    a.append(list(input()))
for i in range(1,n-1):
    for j in range(1,n-1):
        if a[i][j]=='#' and a[i+1][j]=='#' and a[i-1][j]=='#' and a[i][j-1]=='#' and a[i][j+1]=='#':
            a[i][j]='.'
            a[i][j+1]='.'
            a[i][j-1]='.'
            a[i+1][j]='.'
            a[i-1][j]='.'
for i in a:
    for j in i:
        if j=='#':
            print('NO')
            return
print('YES')



n = int(input())
a = [list(input()) for i in range(n)]
for i in range(1,n-1):
	for j in range(1,n-1):
		if a[i][j] == a[i-1][j] == a[i+1][j] == a[i][j-1] == a[i][j+1] == '#':
			a[i][j] = a[i-1][j] = a[i+1][j] = a[i][j-1] = a[i][j+1] = '.'
print("NO" if sum(a[i].count('#') for i in range(n)) else "YES")



def f():
    n = int(input())
    t = [list(input()) for i in range(n)]
    for i in range(n - 2):
        if t[i][0] == '#' or t[i][-1] == '#': return 'NO'
        for j in range(1, n - 1):
            if t[i][j] == '#':
                if '#' == t[i + 1][j - 1] == t[i + 1][j] == t[i + 1][j + 1] == t[i + 2][j]:
                    t[i + 1][j - 1] = t[i + 1][j] = t[i + 1][j + 1] = t[i + 2][j] = '.'
                else: return 'NO'
    if '#' in t[-2] or '#' in t[-1]: return 'NO'
    return 'YES'
print(f())


n = int(input())
s = [list(input()) for _ in range(n)]
def TryCross(i, j):
  if 0 <= i < n - 2 and 0 < j < n - 1:
    c = [(i, j), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1), (i + 2, j)]
    if not all(s[x][y] == "#" for x, y in c):
      return False
    for x, y in c:
      s[x][y] = "."
    return True
  return False
for i in range(n):
  for j in range(n):
    if s[i][j] == "#" and not TryCross(i, j):
      print("NO")
      return
print("YES")

n = int(input())
b = [list(input()) for _ in range(n)]

for i in range(1, n - 1):
    for j in range(1, n - 1):
        if b[i][j] == b[i-1][j] == b[i+1][j] == b[i][j-1] == b[i][j+1] == '#':
            b[i][j] = b[i-1][j] = b[i+1][j] = b[i][j-1] = b[i][j+1] = '.'
print('NO' if any(True for r in b if '#' in r) else 'YES')

n = int(input())
a = [[0] * n for i in range(n)]
ans = 'YES'
for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == '#':
            a[i][j] = 1
#print(a)
for i in range(n - 2):
    for j in range(1, n - 1):
        if a[i][j] == 1:
            if a[i + 1][j] == 1 and a[i + 2][j] == 1 and a[i + 1][j - 1] == 1 and a[i + 1][j + 1] == 1:
                a[i][j] = 0
                a[i + 1][j] = 0
                a[i + 2][j] = 0
                a[i + 1][j - 1] = 0
                a[i + 1][j + 1] = 0
            else:
                ans = 'NO'
#print(a)
for i in range(n):
    if sum(a[i]) != 0:
        ans = 'NO'
print(ans)


n = int(input())
a = []
for i in range(n):
	a.append(list(1 if c == '#' else 0 for c in input()))
for i in range(n):
	for j in range(n):
		if a[i][j]:
			if i + 2 >= n or j + 1 >= n or j == 0:
				print('NO')
				return
			if a[i + 1][j] + a[i + 2][j] + a[i + 1][j - 1] + a[i + 1][j + 1] != 4:
				print('NO')
				return
			a[i][j] = a[i + 1][j] = a[i + 2][j] = a[i + 1][j - 1] = a[i + 1][j + 1] = 0
print('YES')


def main():
    h = int(input())
    l = [c == '#' for _ in range(h) for c in input()]
    if not (l[0] or l[-1] or sum(l) % 5):
        l[-1] = True
        w, idx = len(l) // h, 0
        lim = (h - 2) * w - 2
        pattern = (0, w - 1, w, w + 1, 2 * w)
        while True:
            idx = l.index(True, idx + 1)
            if idx > lim:
                break
            if all(l[_ + idx] for _ in pattern):
                for _ in pattern:
                    l[_ + idx] = False
            else:
                break
        l[-1] = False
    print(('YES', 'NO')[any(l)])


def __starting_point():
    main()
__starting_point()

h = int(input())
l = [c == '#' for _ in range(h) for c in input()]
w = len(l) // h
pattern = (0, w - 1, w, w + 1, 2 * w)
for idx in range(1, (h - 2) * w - 1):
    if all(l[_ + idx] for _ in pattern):
        for _ in pattern:
            l[_ + idx] = False
print(('YES', 'NO')[any(l)])


h = int(input())
l = [c == '#' for _ in range(h) for c in input()]
w = len(l) // h
cross = (0, w - 1, w, w + 1, 2 * w)
for i in range(1, (h - 2) * w - 1):
    if all(l[_ + i] for _ in cross):
        for _ in cross:
            l[_ + i] = False
print(('YES', 'NO')[any(l)])


c=set()
for i in range(int(input())):
    row=input()
    s=[(i,j) for j in range(len(row)) if row[j]=='#']
    c|=set(s)
    for i,j in s:
        p=set([(i,j),(i-1,j),(i-1,j-1),(i-1,j+1),(i-2,j)])
        if p<=c:c-=p
print('YNEOS'[len(c)!=0::2])

n = int(input())
a = [list(input()) for i in range(n)]
for i in range(n):
    for j in range(n):
        if a[i][j] == '#':
            if (i < n - 2 and j >= 1 and j <= n - 2 and a[i + 1][j - 1] == '#' and a[i + 1][j] == '#' and a[i + 1][j + 1] == '#' and a[i + 2][j] == '#'):
                a[i][j] = '.'
                a[i + 1][j - 1] = '.'
                a[i + 1][j] = '.'
                a[i + 1][j + 1] = '.'
                a[i + 2][j] = '.'
            else:
                print('NO')
                return
print('YES')

n = int(input());

s = [['.'] * n] * n;

for i in range(0, n):
    s[i] = list(input());

flag = 1;

for i in range(0, n - 2):
    for j in range(1, n - 1):
        if (s[i][j] == '#'):
            flag &= s[i + 1][j] == '#';
            flag &= s[i + 1][j - 1] == '#';
            flag &= s[i + 1][j + 1] == '#';
            flag &= s[i + 2][j] == '#';
            flag &= s[i][j] == '#';
            s[i + 1][j] = '.';
            s[i + 1][j - 1] = '.';
            s[i + 1][j + 1] = '.';
            s[i + 2][j] = '.';
            s[i][j] = '.';

for i in range(0, n):
    for j in range(0, n):
        flag &= s[i][j] == '.';



if (flag == 1):
    print("YES");
else:
    print("NO");






n = int(input())
al = []
sl = set()
for i in range(n):
    al.append(list(input()))
for i in range(n-2):
    for j in range(1, n-1):
        if al[i][j]==al[i+1][j]==al[i+1][j-1]==al[i+1][j+1]==al[i+2][j]=="#":
            al[i][j]=al[i+1][j]=al[i+1][j-1]=al[i+1][j+1]=al[i+2][j]="."
for i in range(n):
    sl=sl.union(set(al[i]))
if len(sl)==1:
    print("YES")    
else:
    print("NO")

#fdf_2791
n = int(input())
a = [list(input()) for i in range(n)]
for i  in range(1,n-1):
	for j  in range(1,n-1):
			if a[i][j]==a[i-1][j]==a[i][j+1]==a[i+1][j]==a[i][j-1]=='#':
				a[i][j]=a[i-1][j]=a[i][j+1]=a[i+1][j]=a[i][j-1]='.'

print((sum(a[i].count('#')for i in range(n)))==0 and "YES" or "NO")


def fits(x, y):
    nonlocal n
    return x >= 0 and x < n and y >= 0 and y < n

def paint(x, y):
    nonlocal a
    a[x][y] = '.'
    a[x - 1][y] = '.'
    a[x + 1][y] = '.'
    a[x][y - 1] = '.'
    a[x][y + 1] = '.'

def check(x, y):
    nonlocal a
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    cnt = 0
    for i in range(4):
        if (fits(x + dx[i], y + dy[i]) and a[x + dx[i]][y + dy[i]] == '#'):
            cnt += 1
    if (a[x][y] == '#'):
        cnt += 1
    if (cnt == 5):
        paint(x, y)

n = int(input())
a = []
for i in range(n):
    a.append(list(input()))
for i in range(n):
    for j in range(n):
        check(i, j)
cnt = 0
for el in a:
    for el2 in el:
        if el2 == '#':
            cnt += 1

if (cnt == 0):
    print('YES')
else:
    print('NO')


import sys

num_lines = int(input())

lines = []
hash_count = 0

for i in range(num_lines):
    tmp = input()
    lines.append([i for i in tmp])
    hash_count = hash_count + tmp.count("#")

for i in range(len(lines)):
    for j in range(len(lines[i])):
        if lines[i][j] == "#":
                try:
                    if lines[i + 1][j - 1] == "#" and lines[i + 1][j] == "#" and lines[i + 1][j + 1] == "#" and \
                                    lines[i + 2][j] == "#":
                        lines[i + 1][j - 1] = "."
                        lines[i + 1][j] = "."
                        lines[i + 1][j + 1] = "."
                        lines[i + 2][j] = "."
                        hash_count = hash_count - 5
                except:
                    print("NO")
                    return


if hash_count == 0:
    print("YES")
else:
    print("NO")







from typing import List


def cross_neighbors(i: int, j: int):
    return [(i + 1, j - 1), (i + 1, j), (i + 1, j + 1), (i + 2, j)]


def solve(n: int, board: List[List[str]]) -> str:
    for i in range(0, n - 2):
        for j in range(1, n - 1):
            if board[i][j] == '#':
                board[i][j] = '.'
                for x, y in cross_neighbors(i, j):
                    if board[x][y] == '.':
                        return 'NO'
                    if board[x][y] == '#':
                        board[x][y] = '.'
    return ['YES', 'NO'][any(board[i][j] == '#' \
        for i in range(n) for j in range(n))]

n = int(input())
board = [list(input()) for _ in range(n)]

print(solve(n, board))


n=int(input())

board=[""]*n
c=0
for i in range(n):
    board[i]=list(input())
    
    
for i in range(1,n-1):
    for j in range(1,n-1):
        if(board[i][j]=='#' and board[i-1][j]=='#' and board[i+1][j]=='#' and board[i][j-1]=='#' and board[i][j+1]=='#'):
            board[i][j]='.'
            board[i-1][j]='.'
            board[i+1][j]='.'
            board[i][j-1]='.'
            board[i][j+1]='.'
            
            
c= sum(board[i].count('#') for i in range(n))

print ('YES') if c==0 else print('NO')