from typing import List


class ConwaysGameOfLife:
    """
    Represents a grid of conway's game of life, where each cell is either alive or dead.
    The rules of the game are the following:
    1. Any live cell with fewer than two live neighbors dies, as if by underpopulation.
    2. Any live cell with two or three live neighbors lives on to the next generation.
    3. Any live cell with more than three live neighbors dies, as if by overpopulation.
    4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
    """

    def __init__(self, grid: List[List[int]]):
        """
        Initializes the game with a grid; 0 is dead and 1 is alive.
        """
        self.grid = grid

    def step(self):
        # initialize a fully dead grid
        new_grid = [[0 for _ in row] for row in self.grid]

        for i, row in enumerate(self.grid):
            for j, cell in enumerate(row):
                alive_neighbors = self.compute_alive_nearby_cells(i, j)
                if cell:
                    if alive_neighbors < 2 or alive_neighbors > 3:
                        new_grid[i][j] = 0
                    else:
                        new_grid[i][j] = 1
                else:
                    if alive_neighbors == 3:
                        new_grid[i][j] = 1

        self.grid = new_grid

    def compute_alive_nearby_cells(self, i: int, j: int) -> int:
        count = 0
        for x in range(i - 1, i + 2):
            for y in range(j - 1, j + 2):
                if x == i and y == j:
                    continue
                count += 1 if self.grid[x][y] else 0

        return count

    def show(self) -> str:
        buf = ""
        for row in self.grid:
            for cell in row:
                buf += "X" if cell else " "
            buf += "\n"

        return buf