[VI] Stars

def k_up_left(k_x,k_y,b_x,b_y):
    if k_x-1>=0 and k_y+2<8 and (k_x-1!=b_x or k_y+2!=b_y):
        return k_x-1, k_y+2
    return k_x,k_y
def k_up_right(k_x,k_y,b_x,b_y):
    if k_x+1<8 and k_y+2<8 and (k_x+1!=b_x or k_y+2!=b_y):
        return k_x+1, k_y+2
    return k_x,k_y
def k_right_down(k_x,k_y,b_x,b_y):
    if k_x+2<8 and k_y-1>=0 and (k_x+2!=b_x or k_y-1!=b_y):
        return k_x+2, k_y-1
    return k_x,k_y
def k_right_up(k_x,k_y,b_x,b_y):
    if k_x+2<8 and k_y+1<8 and (k_x+2!=b_x or k_y+1!=b_y):
        return k_x+2, k_y+1
    return k_x,k_y
def k_left_down(k_x,k_y,b_x,b_y):
    if k_x-2>=0 and k_y-1>=0 and (k_x-2!=b_x or k_y-1!=b_y):
        return k_x-2, k_y-1
    return k_x,k_y

def k_left_up(k_x,k_y,b_x,b_y):
    if k_x-2>=0 and k_y+1<8 and (k_x-2!=b_x or k_y+1!=b_y):
        return k_x-2, k_y+1
    return k_x,k_y

def k_down_left(k_x,k_y,b_x,b_y):
    if k_x-1>0 and k_y-2>=0 and (k_x-1!=b_x or k_y-2!=b_y):
        return k_x-1, k_y-2
    return k_x,k_y

def k_down_right(k_x,k_y,b_x,b_y):
    if k_x+1<8 and k_y-2>=0 and (k_x+1!=b_x or k_y-2!=b_y):
        return k_x+1, k_y-2
    return k_x,k_y
def b_down_left(k_x,k_y,b_x,b_y):
    if b_x-1>=0 and k_y-1>=0 and (k_x!=b_x-1 or k_y!=b_y-1):
        return b_x-1,b_y-1
    return b_x,b_y

def b_down_right(k_x,k_y,b_x,b_y):
    if b_x+1<8 and k_y-1>=0 and (k_x!=b_x+1 or k_y!=b_y-1):
        return b_x+1,b_y-1
    return b_x,b_y
def b_up_left(k_x,k_y,b_x,b_y):
    if b_x-1>=0 and k_y+1<8 and (k_x!=b_x-1 or k_y!=b_y+1):
        return b_x-1,b_y+1
    return b_x,b_y
def b_up_right(k_x,k_y,b_x,b_y):
    if b_x+1<8 and k_y+1<8 and (k_x!=b_x+1 or k_y!=b_y+1):
        return b_x+1,b_y+1
    return b_x,b_y
class Stars(Problem):
    def __init__(self, initial, house=None):
        super().__init__(initial, house)

    def goal_test(self, state):
        stars= state[4]
        return len(stars)==0

    def successor(self, state):
        succ = {}
        k_x= state[0]
        k_y= state[1]
        b_x= state[2]
        b_y= state[3]
        stars= state[4]

        new_k_x, new_k_y = k_up_right(k_x, k_y, b_x, b_y)
        if new_k_x != k_x:
            succ["Konj Gore Desno"] = (
            new_k_x, new_k_y, b_x, b_y, tuple([s for s in stars if (s[0], s[1]) != (new_k_x, new_k_y)]))

        new_k_x, new_k_y = k_up_left(k_x, k_y, b_x, b_y)
        if new_k_x != k_x:
            succ["Konj Gore Levo"] = (
            new_k_x, new_k_y, b_x, b_y, tuple([s for s in stars if (s[0], s[1]) != (new_k_x, new_k_y)]))

        new_k_x, new_k_y = k_right_up(k_x, k_y, b_x, b_y)
        if new_k_x != k_x:
            succ["Konj Desno Gore"] = (
            new_k_x, new_k_y, b_x, b_y, tuple([s for s in stars if (s[0], s[1]) != (new_k_x, new_k_y)]))

        new_k_x, new_k_y = k_right_down(k_x, k_y, b_x, b_y)
        if new_k_x != k_x:
            succ["Konj Desno Dolu"] = (
            new_k_x, new_k_y, b_x, b_y, tuple([s for s in stars if (s[0], s[1]) != (new_k_x, new_k_y)]))

        new_k_x, new_k_y = k_left_up(k_x, k_y, b_x, b_y)
        if new_k_x != k_x:
            succ["Konj Levo Gore"] = (
            new_k_x, new_k_y, b_x, b_y, tuple([s for s in stars if (s[0], s[1]) != (new_k_x, new_k_y)]))

        new_k_x, new_k_y = k_left_down(k_x, k_y, b_x, b_y)
        if new_k_x != k_x:
            succ["Konj Levo Dolu"] = (
            new_k_x, new_k_y, b_x, b_y, tuple([s for s in stars if (s[0], s[1]) != (new_k_x, new_k_y)]))

        new_k_x, new_k_y = k_down_left(k_x, k_y, b_x, b_y)
        if new_k_x != k_x:
            succ["Konj Dolu Levo"] = (
            new_k_x, new_k_y, b_x, b_y, tuple([s for s in stars if (s[0], s[1]) != (new_k_x, new_k_y)]))

        new_k_x, new_k_y = k_down_right(k_x, k_y, b_x, b_y)
        if new_k_x != k_x:
            succ["Konj Dolu Desno"] = (
            new_k_x, new_k_y, b_x, b_y, tuple([s for s in stars if (s[0], s[1]) != (new_k_x, new_k_y)]))

        new_b_x,new_b_y= b_up_left(k_x,k_y,b_x,b_y)
        if new_b_x!=b_x:
            succ["Lovec Gore Levo"] = (k_x,k_y,new_b_x,new_b_y,tuple([s for s in stars if (s[0],s[1])!=(new_b_x,new_b_y)]))

        new_b_x,new_b_y= b_up_right(k_x,k_y,b_x,b_y)
        if new_b_x!=b_x:
            succ["Lovec Gore Desno"] = (k_x,k_y,new_b_x,new_b_y,tuple([s for s in stars if (s[0],s[1])!=(new_b_x,new_b_y)]))

        new_b_x,new_b_y= b_down_left(k_x,k_y,b_x,b_y)
        if new_b_x!=b_x:
            succ["Lovec Dolu Levo"] = (k_x,k_y,new_b_x,new_b_y,tuple([s for s in stars if (s[0],s[1])!=(new_b_x,new_b_y)]))

        new_b_x, new_b_y = b_down_right(k_x, k_y, b_x, b_y)
        if new_b_x != b_x:
            succ["Lovec Dolu Desno"] = (k_x, k_y,new_b_x,new_b_y, tuple([s for s in stars if (s[0], s[1]) != (new_b_x, new_b_y)]))

        return succ
    def actions(self, state):
        return self.successor(state).keys()

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


if __name__ == '__main__':

    k_x,k_y = input().split(',')
    k_x=int(k_x)
    k_y=int(k_y)
    b_x,b_y = input().split(',')
    b_x=int(b_x)
    b_y=int(b_y)
    stars= []
    n= int(input())
    for i in range(0,n):
        s_x,s_y = input().split(',')
        s_x = int(s_x)
        s_y = int(s_y)
        s = []
        s.append(s_x)
        s.append(s_y)
        stars.append(tuple(s))
    stars=tuple(stars)
    galaxies = ((1,1),(3,3),(5,7))
    stars_problem = Stars((k_x,k_y,b_x,b_y,stars))

    answer= breadth_first_graph_search(stars_problem)

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