import math
import os
import random
import re
import sys
from typing import List


def grid_after_bomb(bomb_grid):
    grid = [["O"] * len(bomb_grid[0]) for _ in range(len(bomb_grid))]
    for i in range(len(bomb_grid)):
        for j in range(len(bomb_grid[0])):
            # print(bomb_grid[i][j])
            if bomb_grid[i][j] == "O":
                grid[i][j] = "."
                if i > 0:
                    grid[i-1][j] = "."
                if i < len(bomb_grid) - 1:
                    grid[i+1][j] = "."
                if j > 0:
                    grid[i][j-1] = "."
                if j < len(bomb_grid[0]) - 1:
                    grid[i][j+1] = "."
    return grid


def bomberMan(n: int, grid: List[List[str]]) -> List[List[str]]:
    if n < 2:
        return grid
    if n % 2 == 0:
        # return [["O"] * len(grid[0]) for _ in range(len(grid))] Runtime Error
        return ["O"*len(grid[0])] * len(grid)

    bomb_grid = grid_after_bomb(grid)
    if n % 4 == 1:
        bomb_grid = grid_after_bomb(bomb_grid)
    return ["".join(row) for row in bomb_grid]