class GameOfLife:
    def __init__(self, sizex, sizey):
        assert sizex > 0
        assert sizey > 0

        self.sizex = sizex
        self.sizey = sizey
        self.cells = [[NoUnit(i, j) for j in range(sizey)] for i in range(sizex)]

    def parse_field(self, field):
        assert len(field) == self.sizex

        x = 0
        for line in field:
            y = 0
            assert len(line) == self.sizey
            for char in line:
                if char == 'f':
                    self.cells[x][y] = FishUnit(x, y)
                if char == 's':
                    self.cells[x][y] = ShrimpUnit(x, y)
                if char == 'r':
                    self.cells[x][y] = RockUnit(x, y)
                y += 1
            x += 1

    def print_field(self):
        dict = {
            'NoUnit': 'n',
            'RockUnit': 'r',
            'ShrimpUnit': 's',
            'FishUnit': 'f'
        }
        for x in range(self.sizex):
            for y in range(self.sizey):
                print(dict[self.cells[x][y].type], sep='', end='')
            print()

    def correct_coors(self, x, y):
        return 0 <= x < self.sizex and 0 <= y < self.sizey

    def iterate(self):
        new_cells = [[NoUnit(i, j) for j in range(self.sizey)] for i in range(self.sizex)]

        neighbour_diffs = [
            [-1, -1],
            [0, -1],
            [1, -1],
            [-1, 0],
            [1, 0],
            [-1, 1],
            [0, 1],
            [1, 1]
        ]

        for x in range(self.sizex):
            for y in range(self.sizey):
                neighbours = [self.cells[x - d[0]][y - d[1]]
                              if self.correct_coors(x - d[0], y - d[1]) else
                              NoUnit(0, 0)
                              for d in neighbour_diffs]
                # print(x, y, neighbours)
                if not self.cells[x][y].should_be_killed(neighbours):
                    new_cells[x][y] = self.cells[x][y]

                if self.cells[x][y].can_spawn_fish(neighbours):
                    new_cells[x][y] = FishUnit(x, y)
                elif self.cells[x][y].can_spawn_shrimp(neighbours):
                    new_cells[x][y] = ShrimpUnit(x, y)

        self.cells = new_cells

class Unit:
    def __init__(self, posx, posy):
        self.posx = posx
        self.posy = posy
        self.type = 'Unit'

    def should_be_killed(self, neighbours):
        return False

    def can_spawn_shrimp(self, neighbours):
        return False

    def can_spawn_fish(self, neighbours):
        return False

    def __str__(self):
        return self.type + '(' + str(self.posx) + ', ' + str(self.posy) + ')'

    def __repr__(self):
        return self.type + '(' + str(self.posx) + ', ' + str(self.posy) + ')'

    def __eq__(self, other):
        return self.type == other.type and self.posx == other.posx and self.posy == other.posy


class NoUnit(Unit):
    def __init__(self, posx, posy):
        super().__init__(posx, posy)
        self.type = 'NoUnit'

    def can_spawn_shrimp(self, neighbours):
        ns_num = sum(1 if neighbour.type == 'ShrimpUnit' else 0 for neighbour in neighbours)
        return ns_num == 3

    def can_spawn_fish(self, neighbours):
        ns_num = sum(1 if neighbour.type == 'FishUnit' else 0 for neighbour in neighbours)
        return ns_num == 3


class FishUnit(Unit):
    def __init__(self, posx, posy):
        super().__init__(posx, posy)
        self.type = 'FishUnit'

    def should_be_killed(self, neighbours):
        ns_num = sum(1 if neighbour.type == 'FishUnit' else 0 for neighbour in neighbours)
        return ns_num < 2 or ns_num >= 4


class ShrimpUnit(Unit):
    def __init__(self, posx, posy):
        super().__init__(posx, posy)
        self.type = 'ShrimpUnit'

    def should_be_killed(self, neighbours):
        ns_num = sum(1 if neighbour.type == 'ShrimpUnit' else 0 for neighbour in neighbours)
        return ns_num < 2 or ns_num >= 4


class RockUnit(Unit):
    def __init__(self, posx, posy):
        super().__init__(posx, posy)
        self.type = 'RockUnit'

    def should_be_killed(self, neighbours):
        return False