import Queue
import operator

"""Consist of x and y co-ordinates of a particular location"""


class Node:

    def __init__(self, x, y):
        self.x = x
        self.y = y
        # self.z = z

    def __repr__(self):
        return str(self.x) + "," + str(self.y)

    def __eq__(self, other):
        if other != None:
            return str(self.x) == str(other.x) and str(self.y) == str(other.y)
        return True

    def __ne__(self, other):
        if other != None:
            return str(self.x) != str(other.x) or str(self.y) != str(other.y)
        return True

    def __cmp__(self, other):
        return str(self.x) == str(other.x) and str(self.y) == str(other.y)

    def __hash__(self):
        return (hash(self.x)) + (2 * hash(self.y))

    def is_valid_location(self, i, j, col, row):
        if 0 <= i < int(col) and 0 <= j < int(row):
            return True
        return False

    def get_north(self, col, row):
        if self.is_valid_location(self.x, self.y - 1, col, row):
            return Node(self.x, self.y - 1)
        return None

    def get_north_east(self, col, row):
        if self.is_valid_location(self.x + 1, self.y - 1, col, row):
            return Node(self.x + 1, self.y - 1)
        return None

    def get_north_west(self, col, row):
        if self.is_valid_location(self.x - 1, self.y - 1, col, row):
            return Node(self.x - 1, self.y - 1)
        return None

    def get_west(self, col, row):
        if self.is_valid_location(self.x - 1, self.y, col, row):
            return Node(self.x - 1, self.y)
        return None

    def get_south_west(self, col, row):
        if self.is_valid_location(self.x - 1, self.y + 1, col, row):
            return Node(self.x - 1, self.y + 1)
        return None

    def get_south(self, col, row):
        if self.is_valid_location(self.x + 1, self.y, col, row):
            return Node(self.x + 1, self.y)
        return None

    def get_south_east(self, col, row):
        if self.is_valid_location(self.x + 1, self.y + 1, col, row):
            return Node(self.x + 1, self.y + 1)
        return None

    def get_east(self, col, row):
        if self.is_valid_location(self.x, self.y + 1, col, row):
            return Node(self.x, self.y + 1)
        return None


class Search:
    actions = {"north": "get_north", "east": "get_east", "south": "get_south", "west": "get_west", "north_east":
        "get_north_east", "north_west": "get_north_west", "south_east": "get_south_east",
               "south_west": "get_south_west"}

    def __init__(self, type_of_search, landing_site, target_sites, state, max_z_elevation, col, row):
        self.type_of_search = type_of_search
        self.landing_site = landing_site
        self.target_sites = target_sites
        self.state = state
        self.max_z_elevation = max_z_elevation
        self.col = col
        self.row = row

    def __repr__(self):
        return "Type of search: " + str(self.type_of_search) + " Landing Site: " + str(
            self.landing_site) + " Target sites: " + \
               str(self.target_sites) + " Max Z elevation:" + str(self.max_z_elevation)

    def goal_test(self, curr_site, target_site):
        return curr_site == target_site

    def find_route(self, no_of_target_sites):
        if self.type_of_search == "BFS":
            for i in range(int(no_of_target_sites)):
                self.bfs(self.target_sites[i])
        if self.type_of_search == "UCS":
            for i in range(int(no_of_target_sites)):
                self.ucs(self.target_sites[i])
        if self.type_of_search == "A*":
            for i in range(int(no_of_target_sites)):
                self.a_star(self.target_sites[i])

    def print_route(self, child_parent_dict, target_site):
        route = []
        present_site = target_site
        while present_site != self.landing_site:
            route.append(present_site)
            present_site = child_parent_dict[present_site]
        route.append(self.landing_site)
        route = route[::-1]
        print(route)

    def bfs(self, target_site):
        frontier = Queue.Queue()
        explored = []
        child_parent_dict = {}
        if self.goal_test(self.landing_site, target_site):
            self.print_route(None, self.landing_site)
            return
        frontier.put(self.landing_site)
        while not frontier.empty():
            current_site = frontier.get()
            explored.append(current_site)
            for action in self.actions:
                site = eval(
                    "current_site" + "." + self.actions.get(action) + "(" + self.col + ", " + self.row + ")")
                if site is not None and abs(
                        int(self.state[site.y][site.x]) - int(self.state[current_site.y][current_site.x])) <= int(
                    self.max_z_elevation):
                    if site not in explored:
                        if self.goal_test(site, target_site):
                            child_parent_dict[site] = current_site
                            self.print_route(child_parent_dict, site)
                            return
                        frontier.put(site)
                        child_parent_dict[site] = current_site
        print("FAIL")
        return

    def ucs(self, target_site):
        priority_frontier = {self.landing_site: 0}
        explored = []
        child_parent_dict = {}
        path_cost = 0
        while True:
            if not priority_frontier:
                print("FAIL")
                return
            sites_sorted_by_path_cost = sorted(priority_frontier.items(), key=operator.itemgetter(1))
            current_site = sites_sorted_by_path_cost[0][0]
            del priority_frontier[current_site]
            if self.goal_test(current_site, target_site):
                self.print_route(child_parent_dict, current_site)
                return
            explored.append(current_site)
            for action in self.actions:
                site = eval("current_site" + "." + self.actions.get(action) + "(" + self.col + ", " + self.row + ")")
                if site not in explored and site not in priority_frontier:
                    if site is not None and abs(
                            int(self.state[site.y][site.x]) - int(self.state[current_site.y][current_site.x])) <= int(
                            self.max_z_elevation):
                        child_parent_dict[site] = current_site
                        if action == "north_east" or action == "north_west" or action == "south_east" or action == \
                                "south_west":
                            path_cost += 14
                            priority_frontier[site] = path_cost
                        else:
                            path_cost += 10
                            priority_frontier[site] = path_cost
                elif priority_frontier.get(site) > path_cost:
                    child_parent_dict[site] = current_site
                    priority_frontier[site] = path_cost

    def a_star(self, target_site):
        return "FAIL"


inputFile = open("Test.txt")
typeOfSearch = inputFile.readline().strip()
col, row = inputFile.readline().split()
xL, yL = inputFile.readline().split()
start = Node(int(xL), int(yL))
zElevation = inputFile.readline().strip()
noOfTargetSites = inputFile.readline().strip()
targetSites = []
for i in range(int(noOfTargetSites)):
    x, y = inputFile.readline().split()
    n = Node(x, y)
    targetSites.append(n)
searchSpace = [line.split() for line in inputFile.readlines()]

s = Search(typeOfSearch, start, targetSites, searchSpace, zElevation, col, row)
print(s)
s.find_route(noOfTargetSites)