[VI] Pacman

class Pacman(Problem):
    def __init__(self, initial, house=None):
        super().__init__(initial, house)

    def goal_test(self, state):
        return len(state)==0

    def successor(self, state):
        succ = {}
        pac_x=state[0]
        pac_y=state[1]
        nasoka=state[2]
        foods=state[3]
        new_foods=[]

        if nasoka=='istok' and self.check_valid(pac_x+1,pac_y):
            if (pac_x+1,pac_y) in foods:
                for f in foods:
                    if f[0]==pac_x+1 and f[1]==pac_y:
                        continue
                        new_foods.append(f)

        succ["ProdolzhiPravo"]= [(pac_x+1,pac_y),nasoka,new_foods]

        if nasoka=='zapad' and self.check_valid(pac_x-1,pac_y):
            if (pac_x-1,pac_y) in foods:
                for f in foods:
                    if f[0]==pac_x-1 and f[1]==pac_y:
                        continue
                        new_foods.append(f)

        succ["ProdolzhiPravo"]= [(pac_x-1,pac_y),nasoka,new_foods]

        if nasoka=='sever' and self.check_valid(pac_x,pac_y+1):
            if (pac_x,pac_y+1) in foods:
                for f in foods:
                    if f[0]==pac_x and f[1]==pac_y+1:
                        continue
                        new_foods.append(f)

        succ["ProdolzhiPravo"]= [(pac_x,pac_y+1),nasoka,new_foods]

        if nasoka=='jug' and self.check_valid(pac_x,pac_y-1):
            if (pac_x,pac_y-1) in foods:
                for f in foods:
                    if f[0]==pac_x and f[1]==pac_y-1:
                        continue
                        new_foods.append(f)

        succ["ProdolzhiPravo"]= [(pac_x,pac_y-1),nasoka,new_foods]

        if nasoka=='istok' and self.check_valid(pac_x-1,pac_y):
            if (pac_x-1,pac_y) in foods:
                for f in foods:
                    if f[0] == pac_x-1 and f[1] == pac_y:
                        continue
                        new_foods.append(f)

        succ["ProdolzhiNazad"] = [(pac_x-1, pac_y), 'zapad', new_foods]


        if nasoka=='zapad' and self.check_valid(pac_x+1,pac_y):
            if (pac_x+1,pac_y) in foods:
                for f in foods:
                    if f[0] == pac_x+1 and f[1] == pac_y:
                        continue
                        new_foods.append(f)

        succ["ProdolzhiNazad"] = [(pac_x-1, pac_y), 'istok', new_foods]

        if nasoka=='sever' and self.check_valid(pac_x,pac_y-1):
            if (pac_x,pac_y-1) in foods:
                for f in foods:
                    if f[0] == pac_x and f[1] == pac_y-1:
                        continue
                        new_foods.append(f)

        succ["ProdolzhiNazad"] = [(pac_x, pac_y-1), 'jug', new_foods]

        if nasoka=='jug' and self.check_valid(pac_x,pac_y+1):
            if (pac_x,pac_y+1) in foods:
                for f in foods:
                    if f[0] == pac_x and f[1] == pac_y+1:
                        continue
                        new_foods.append(f)

        succ["ProdolzhiNazad"] = [(pac_x, pac_y+1), 'sever', new_foods]

        if nasoka=='istok' and self.check_valid(pac_x,pac_y+1):
            if (pac_x,pac_y+1) in foods:
                for f in foods:
                    if f[0] == pac_x and f[1] == pac_y+1:
                        continue
                        new_foods.append(f)

            succ["SvrtiLevo"] = [(pac_x, pac_y+1), 'sever', new_foods]

        if nasoka=='zapad' and self.check_valid(pac_x,pac_y-1):
            if (pac_x,pac_y-1) in foods:
                for f in foods:
                    if f[0] == pac_x and f[1] == pac_y-1:
                        continue
                        new_foods.append(f)

            succ["SvrtiLevo"] = [(pac_x, pac_y-1), 'jug', new_foods]

        if nasoka=='sever' and self.check_valid(pac_x-1,pac_y):
            if (pac_x-1,pac_y) in foods:
                for f in foods:
                    if f[0] == pac_x-1 and f[1] == pac_y:
                        continue
                        new_foods.append(f)

            succ["SvrtiLevo"] = [(pac_x-1, pac_y), 'zapad', new_foods]

        if nasoka=='jug' and self.check_valid(pac_x+1,pac_y):
            if (pac_x+1,pac_y) in foods:
                for f in foods:
                    if f[0] == pac_x+1 and f[1] == pac_y:
                        continue
                        new_foods.append(f)

            succ["SvrtiLevo"] = [(pac_x+1, pac_y), 'istok', new_foods]

        if nasoka=='istok' and self.check_valid(pac_x,pac_y-1):
            if (pac_x,pac_y-1) in foods:
                for f in foods:
                    if f[0]== pac_x and f[1] == pac[y]-1:
                        continue
                        new_foods.append(f)

            succ["SvrtiDesno"] = [(pac_x, pac_y-1), 'jug', new_foods]

        if nasoka == 'zapad' and self.check_valid(pac_x, pac_y + 1):
            if (pac_x, pac_y + 1) in foods:
                for f in foods:
                    if f[0] == pac_x and f[1] == pac[y] + 1:
                        continue
                        new_foods.append(f)

            succ["SvrtiDesno"] = [(pac_x, pac_y + 1), 'sever', new_foods]

        if nasoka == 'sever' and self.check_valid(pac_x+1,pac_y):
            if (pac_x+1,pac_y) in foods:
                for f in foods:
                    if f[0] == pac_x+1 and f[1] == pac[y]:
                        continue
                        new_foods.append(f)

            succ["SvrtiDesno"] = [(pac_x+1, pac_y), 'istok', new_foods]

        if nasoka == 'jug' and self.check_valid(pac_x - 1, pac_y):
            if (pac_x - 1, pac_y) in foods:
                for f in foods:
                    if f[0] == pac_x - 1 and f[1] == pac[y]:
                        continue
                        new_foods.append(f)

            succ["SvrtiDesno"] = [(pac_x - 1, pac_y), 'zapad', new_foods]



        return succ

    @staticmethod
    def check_valid(state):
        # print(state)
        if state[0]<0 or state[0]>9 or state[1]<0 or state[1]>9:
                return False
        if state in ((0,9),(1,9),(2,9),(3,9),(6,9),(0,8),(8,8),(9,8),(4,7),(8,7),(9,7),(0,6),(3,6),(4,6),(5,6),(4,5),(1,4),(8,4),(9,4),(1,3),(1,2),(6,2),(4,1),(5,1),(6,1),(8,1),(6,0)):
            return False
        return True
    def actions(self, state):
        return self.successor(state).keys()

    def result(self, state, action):
        return self.successor(state)[action]

if __name__ == "__main__":

    pac_x= int(input())
    pac_y= int(input())
    nasoka= input()
    n= int(input())
    foods= []
    for _ in range(n):
        x, y = map(int, input().split(','))
        foods.append((x, y))

    pacman= Pacman((pac_x,pac_y,nasoka,foods))
    answer=breadth_first_graph_search(pacman)

    if answer is None:
        print("None")
    else:
        print(answer.solution())