#python 3
def bomberMan(n, grid):
    if n == 1:
        return grid
    
    allBombs = ['O' * len(grid[0])] * len(grid)
    
    if n % 2 == 0:
        return allBombs
        
    state1 = progress(grid)
    state2 = progress(state1)
    
    return state2 if (n-1) % 4 ==0 else state1
    

def progress(grid):
    h = len(grid)
    w = len(grid[0])
    new = []
    for r in range(h):
        row = ""
        for c in range(w):
            current = grid[r][c]
            bottom = grid[min(r+1,h-1)][c]
            top = grid[max(r-1,0)][c]
            left = grid[r][max(c-1,0)]
            right = grid[r][min(c+1,w-1)]
            
            cross = current + bottom + top + left + right
            
            if cross.count('O') > 0:
                row +='.'
            else:
                row +='O'
        new.append(row)
    return new