class Constraint:
    def __init__(self, cells, total):
        self.cells = cells
        self.total = total
        
    def __repr__(self):
        return f"cells : {self.cells}\ntotal: {self.total}"
    
    def length(self):
        return len(self.cells)
    
    def is_subset_of(self, constraint):
        return every(constraint.index_of(*cell) != -1 for cell in self.cells)

    def index_of(self, row, col):
        for i in range(len(self.cells)):
            if self.cells[i] == (row, col):
                return i
        return -1

    def remove(self, row, col, flag=False):
        idx = self.index_of(row, col)
        if idx != -1:
            self.cells.pop(idx)

            if flag:
                self.total -= 1
                
    def remove_cells(self, cells):
        for cell in self.cells:
            self.remove(*cell)

class Constraints:
    def __init__(self, grid, total_mines):
        self.constraints = []
        covered = []
        print("grid :", grid)
        def fct(row, col):
            if grid.is_opened(row, col):
                self.add_from_cell(grid, row, col)
            if grid.is_covered(row, col):
                covered.append((row, col))
                
        grid.for_each(fct)

        self.add(covered, total_mines)
        self.reduce()
        
    def __repr__(self):
        return '\n'.join(str(c) for c in self.constraints)

    def length(self):
        return len(self.constraints)

    def add(self, cells, value):
        if len(cells) > 0:
            self.constraints.append(Constraint(cells, value))

    def add_from_cell(grid, row, col):
        value = grid.value_at(row, col)
        cells = []
        def fct(i, j):
            if grid.is_covered(i, j):
                cells.append((i, j))
            if grid.is_flagged(i, j):
                value -= 1
                
        grid.for_each_neighbor(row, col, fct)

        self.add(cells, value)
        
    def reduce(self):
        for i in range(len(self.constraints)):
            for j in range(len(self.constraints)):
                if i == j:
                    continue
                a, b = self.constraints[i], self.constraints[j]
                if all(x in b for x in a):
                    b.remove_cells(a.cells)
                    b.total -= a.total

        self.constraints = [c for c in self.constraints if c.length() > 0]
        
    def remove_cell(self, row, col, flag=False):
        self.for_each(lambda c: c.remove(row, col, flag))

    def flag_cell(self, row, col):
        self.remove_cell(row, col, True)

    def for_each(self, fct):
        for c in self.constraints:
            fct(c)

class Grid:
    FLAGGED = 9
    COVERED = -1
    def __init__(self, grid):
        self.grid = [[Grid.COVERED if x == '?' else int(x) for x in row.split()] for row in grid.split('\n')]
        
    def __str__(self):
        return '\n'.join(' '.join('x' if self.is_flagged(i, j) else '?' if self.is_covered(i, j) else str(self.grid[i][j]) for j in range(len(self.grid[0]))) for i in range(len(self.grid)))
    
    def _open(self, row, col):
        self.grid[row][col] = int(open(row, col))

    def flag(self, row, col):
        self.grid[row][col] = Grid.FLAGGED
        
    def value_at(self, row, col):
        return self.grid[row][col]

    def for_each(self, fct):
        for i, row in enumerate(self.grid):
            for j, value in enumerate(row):
                fct(i, j)
                
    def in_grid(self, i, j):
        return 0 <= i < len(self.grid) and 0 <= j < len(self.grid[0])
        
    def for_each_neighbor(self, row, col, fct):
        for i, j in ((-1, -1), (-1, 1), (1, -1), (1, 1), (0, 1), (0, -1), (1, 0), (-1, 0)):
            if self.in_grid(row + i, col + j):
                fct(row + i, col + j)
        
    def is_flagged(self, row, col):
        return self.value_at(row, col) == Grid.FLAGGED

    def is_covered(self, row, col):
        return self.value_at(row, col) == Grid.COVERED

    def is_opened(self, row, col):
        return not self.is_flagged and not self.is_covered(row, col)

    def is_fringe(self, row, col):
        if not self.is_covered(row, col):
            return False
        _is_fringe = False
        def fct(i, j):
            nonlocal _is_fringe
            _is_fringe = _is_fringe or self.is_opened(i, j)
        self.for_each_neighbor(row, col, fct )
        return _is_fringe


class Fringe:
    def __init__(self, cells=[]):
        self.cells = {cell: None for cell in cells}

    @staticmethod
    def create(grid):
        cells = []
        def fct(row, col):
            nonlocal cells
            if grid.is_fringe(row, col):
                cells.append((row, col))
            
        grid.for_each(fct)

        return Fringe(cells)

    def clone(self):
        fringe = Fringe()
        print("clone ,self cells", self.cells)
        for k, v in self.cells:
            fringe.cells[k] = v
#         fringe.cells = dict(self.cells)
        return fringe

    def meets_constraints(self, constraints):
        valid = True
        def fct(c):
            print("constraint :", c)
            nonlocal valid
            valid = valid and self.meets_constraint(c)
        constraints.for_each(fct)
        return valid

    def meets_constraint(self, constraint):
        total, found = 0, 0
        for cell in self.cells:
            print('cell :', cell)
            row, col = cell
            value = self.cells[cell]
            if value is not None and constraint.index_of(row, col) > -1:
                found += 1
                total += value
                if total > constraint.total:
                    return False
        if found == len(constraint) and total != constraint.total:
            return False
        return True

    def _set(self, cell, value):
        self.cells[cell] = None

    def unsolved_cell(self):
        _cell = None
        for cell in self.cells:
            if self.cells[cell] is None:
                _cell = cell
                break
        print("unsolved :", _cell)
        return _cell

class Solutions:
    def __init__(self):
        self.fringes = []
        self.empty = {}
        self.mines = {}

    def length(self):
        return len(self.fringes)

    def known_mines(self):
        mines = []
        for cell in self.mines:
            if self.mines[cell] == 1:
                mines.append(cell)
        return mines
    
    def known_empty(self):
        empty = []
        for key in self.empty:
            cell = map(int, key.split(','))
            if self.empty[key] == 0:
                empty.append(cell)
        return empty


    def push(self, fringe):
        self.fringes.append(fringe)

        if len(self.fringes) == 1:
            for cell in fringe.cells:
                self.empty[cell] = 0
                self.mines[cell] = 1

        for cell in fringe.cells:
            self.empty[cell] |= fringe.cells[cell]
            this.mines[cell] &= fringe.cells[cell]


class Solver:
    def __init__(self, _map, total_mines):
        self.total_mines = total_mines;
        self.grid = Grid(_map);
        self.constraints = Constraints(self.grid, total_mines);

    def solve(self):
        self.solve_basic()

        if self.constraints.length() == 0:
            return str(self.grid)

        solutions = self.find_all_solutions()

        if solutions.length() > 0:
            self.flag(solutions.known_mines())
            self._open(solutions.known_empty())

            if len(solutions.known_mines()) > 0 or len(solutions.known_empty()) > 0:
                return self.solve()
                
        return '?'


    def solve_basic(self):
        changed = False
        def fct(c):
            nonlocal changed
            if c.total == 0:
                self._open(c.cells);
                changed = True

            if c.total == c.length():
                self.flag(c.cells);
                changed = True
            
        self.constraints.for_each(fct)

        if changed:
            self.constraints.reduce()
            self.solve_basic()


    def find_all_solutions(self):
        solutions = Solutions()

        def search(fringe):
            solution = fringe.clone()
            unsolved_cell = fringe.unsolved_cell()

            if not unsolved_cell:
                solutions.push(solution)
                return None


            for i in (0, 1):
                solution._set(unsolved_cell, i)

                if not solution.meets_constraints(self.constraints):
                    continue

                search(solution)

        search(Fringe.create(self.grid))

        return solutions

    def _open(self, cells):
        for cell in cells:
            row, col = cell
            self.grid._open(row, col)
            self.constraints.remove_cell(row, col)
            self.constraints.add_from_cell(self.grid, row, col)

    def flag(self, cells):
        print("flag cells :", cells)
        for cell in cells:
            row, col = cell
            self.grid.flag(row, col)
            self.constraints.flag_cell(row, col)
            
def solve_mine(_map, n):
    solver = Solver(_map, n);
    return solver.solve()