





'''simple docstring'''

import heapq
import sys

import numpy as np

__lowerCAmelCase							:     Optional[int]		     =tuple[int, int]






class        UpperCAmelCase     :
 def __init__(    self				:Any							)->							List[str]:
     A__    =      []
     A__    =      set()
 def 					UpperCAmelCase_							(    self				:Optional[int]							)->							Dict:
     if not self.empty():
         return self.elements[0][0]
     else:
         return float("inf"							)
 def 					UpperCAmelCase_							(    self				:Any							)->							List[str]:
     return len(self.elements							) == 0
 def 					UpperCAmelCase_							(    self				:str						,	lowercase_				:Union[str, Any]						,	lowercase_				:Any							)->							Union[str, Any]:
     if item not in self.set:
         heapq.heappush(self.elements						,	(priority, item)							)
         self.set.add(lowercase_							)
     else:
         # update
         # print("update", item)
         A__    =      []
         ((A__),     (A__))    =      heapq.heappop(self.elements							)
         while x != item:
             temp.append((pri, x)							)
             ((A__),     (A__))    =      heapq.heappop(self.elements							)
         temp.append((priority, item)							)
         for pro, xxx in temp:
             heapq.heappush(self.elements						,	(pro, xxx)							)
 def 					UpperCAmelCase_							(    self				:str						,	lowercase_				:List[Any]							)->							str:
     if item in self.set:
         self.set.remove(lowercase_							)
         A__    =      []
         ((A__),     (A__))    =      heapq.heappop(self.elements							)
         while x != item:
             temp.append((pro, x)							)
             ((A__),     (A__))    =      heapq.heappop(self.elements							)
         for prito, yyy in temp:
             heapq.heappush(self.elements						,	(prito, yyy)							)
 def 					UpperCAmelCase_							(    self				:List[str]							)->							Any:
     return self.elements[0][1]



 def 					UpperCAmelCase_							(    self				:Union[str, Any]							)->							Dict:
     ((A__),     (A__))    =      heapq.heappop(self.elements							)
     self.set.remove(lowercase_							)
     return (priority, item)





def 						UpperCamelCase    (							_lowerCamelCase : TPos						,	_lowerCamelCase : TPos	):
    # euclidean distance
    A__    =      np.array(_lowerCamelCase	)
    A__    =      np.array(_lowerCamelCase	)
    return np.linalg.norm(a - b	)





def 						UpperCamelCase    (							_lowerCamelCase : TPos						,	_lowerCamelCase : TPos	):
    # integer division by time variable
    return consistent_heuristic(_lowerCamelCase						,	_lowerCamelCase	) // t





def 						UpperCamelCase    (							_lowerCamelCase : TPos						,	_lowerCamelCase : TPos	):
    # manhattan distance
    return abs(p[0] - goal[0]	) + abs(p[1] - goal[1]	)





def 						UpperCamelCase    (							_lowerCamelCase : TPos						,	_lowerCamelCase : int						,	_lowerCamelCase : TPos						,	_lowerCamelCase : dict[TPos, float]	):
    A__    =      g_function[start] + Wa * heuristics[i](_lowerCamelCase						,	_lowerCamelCase	)
    return ans





def 						UpperCamelCase    (							_lowerCamelCase : Optional[Any]						,	_lowerCamelCase : List[Any]						,	_lowerCamelCase : Tuple	):
    A__    =      np.chararray((n, n)	)
    for i in range(_lowerCamelCase	):
        for j in range(_lowerCamelCase	):
            A__    =      "*"

    for i in range(_lowerCamelCase	):
        for j in range(_lowerCamelCase	):
            if (j, (n - 1) - i) in blocks:
                A__    =      "#"

    A__    =      "-"
    A__    =      back_pointer[goal]
    while x != start:
        ((A__),     (A__))    =      x
        # print(x)
        A__    =      "-"
        A__    =      back_pointer[x]
    A__    =      "-"

    for i in range(_lowerCamelCase	):
        for j in range(_lowerCamelCase	):
            if (i, j) == (0, n - 1):
                print(grid[i][j]						,	end=" "	)
                print("<-- End position"						,	end=" "	)
            else:
                print(grid[i][j]						,	end=" "	)
        print()
    print("^"	)
    print("Start position"	)
    print()
    print("# is an obstacle"	)
    print("- is the path taken by algorithm"	)
    print("PATH TAKEN BY THE ALGORITHM IS:-"	)
    A__    =      back_pointer[goal]
    while x != start:
        print(_lowerCamelCase						,	end=" "	)
        A__    =      back_pointer[x]
    print(_lowerCamelCase	)
    sys.exit()





def 						UpperCamelCase    (							_lowerCamelCase : TPos	):
    if p[0] < 0 or p[0] > n - 1:
        return False
    if p[1] < 0 or p[1] > n - 1:
        return False
    return True





def 						UpperCamelCase    (							_lowerCamelCase : str						,	_lowerCamelCase : Union[str, Any]						,	_lowerCamelCase : Optional[Any]						,	_lowerCamelCase : List[Any]						,	_lowerCamelCase : Dict						,	_lowerCamelCase : List[Any]						,	_lowerCamelCase : Optional[int]						,	_lowerCamelCase : Any						,	):
    for itera in range(_lowerCamelCase	):
        open_list[itera].remove_element(_lowerCamelCase	)
    # print("s", s)
    # print("j", j)
    ((A__),     (A__))    =      s
    A__    =      (x - 1, y)
    A__    =      (x + 1, y)
    A__    =      (x, y + 1)
    A__    =      (x, y - 1)

    for neighbours in [left, right, up, down]:
        if neighbours not in blocks:
            if valid(_lowerCamelCase	) and neighbours not in visited:
                # print("neighbour", neighbours)
                visited.add(_lowerCamelCase	)
                A__    =      -1
                A__    =      float("inf"	)

            if valid(_lowerCamelCase	) and g_function[neighbours] > g_function[s] + 1:
                A__    =      g_function[s] + 1
                A__    =      s
                if neighbours not in close_list_anchor:
                    open_list[0].put(_lowerCamelCase						,	key(_lowerCamelCase						,	0						,	_lowerCamelCase						,	_lowerCamelCase	)	)
                    if neighbours not in close_list_inad:
                        for var in range(1						,	_lowerCamelCase	):
                            if key(_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase	) <= Wa * key(
                                _lowerCamelCase						,	0						,	_lowerCamelCase						,	_lowerCamelCase	):
                                open_list[j].put(
                                    _lowerCamelCase						,	key(_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase	)	)





def 						UpperCamelCase    (							):
    A__    =      []
    for x in range(1						,	5	):
        for y in range(1						,	6	):
            some_list.append((x, y)	)

    for x in range(15						,	20	):
        some_list.append((x, 17)	)

    for x in range(10						,	19	):
        for y in range(1						,	15	):
            some_list.append((x, y)	)

    # L block
    for x in range(1						,	4	):
        for y in range(12						,	19	):
            some_list.append((x, y)	)
    for x in range(3						,	13	):
        for y in range(16						,	19	):
            some_list.append((x, y)	)
    return some_list


__lowerCAmelCase							:     Union[str, Any]		     ={0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

__lowerCAmelCase							:     int		     =[
    (0, 1),
    (1, 1),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1),
    (6, 1),
    (7, 1),
    (8, 1),
    (9, 1),
    (10, 1),
    (11, 1),
    (12, 1),
    (13, 1),
    (14, 1),
    (15, 1),
    (16, 1),
    (17, 1),
    (18, 1),
    (19, 1),
]
__lowerCAmelCase							:     Optional[Any]		     =make_common_ground()


__lowerCAmelCase							:     Tuple		     =blocks_blk
# hyper parameters
__lowerCAmelCase							:     Optional[Any]		     =1
__lowerCAmelCase							:     List[str]		     =1
__lowerCAmelCase							:     Dict		     =20
__lowerCAmelCase							:     Optional[int]		     =3  # one consistent and two other inconsistent

# start and end destination
__lowerCAmelCase							:     Any		     =(0, 0)
__lowerCAmelCase							:     Union[str, Any]		     =(n - 1, n - 1)

__lowerCAmelCase							:     List[str]		     =1





def 						UpperCamelCase    (							_lowerCamelCase : TPos						,	_lowerCamelCase : TPos						,	_lowerCamelCase : int	):
    A__    =      {start: 0, goal: float("inf"	)}
    A__    =      {start: -1, goal: -1}
    A__    =      []
    A__    =      set()

    for i in range(_lowerCamelCase	):
        open_list.append(PriorityQueue()	)
        open_list[i].put(_lowerCamelCase						,	key(_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase	)	)

    A__    =      []
    A__    =      []
    while open_list[0].minkey() < float("inf"	):
        for i in range(1						,	_lowerCamelCase	):
            # print(open_list[0].minkey(), open_list[i].minkey())
            if open_list[i].minkey() <= Wa * open_list[0].minkey():
                global t
                t += 1
                if g_function[goal] <= open_list[i].minkey():
                    if g_function[goal] < float("inf"	):
                        do_something(_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase	)
                else:
                    A__,     A__    =      open_list[i].top_show()
                    visited.add(_lowerCamelCase	)
                    expand_state(
                        _lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase						,	)
                    close_list_inad.append(_lowerCamelCase	)
            else:
                if g_function[goal] <= open_list[0].minkey():
                    if g_function[goal] < float("inf"	):
                        do_something(_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase	)
                else:
                    A__    =      open_list[0].top_show()
                    visited.add(_lowerCamelCase	)
                    expand_state(
                        _lowerCamelCase						,	0						,	_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase						,	_lowerCamelCase						,	)
                    close_list_anchor.append(_lowerCamelCase	)
    print("No path found to goal"	)
    print()
    for i in range(n - 1						,	-1						,	-1	):
        for j in range(_lowerCamelCase	):
            if (j, i) in blocks:
                print("#"						,	end=" "	)
            elif (j, i) in back_pointer:
                if (j, i) == (n - 1, n - 1):
                    print("*"						,	end=" "	)
                else:
                    print("-"						,	end=" "	)
            else:
                print("*"						,	end=" "	)
            if (j, i) == (n - 1, n - 1):
                print("<-- End position"						,	end=" "	)
        print()
    print("^"	)
    print("Start position"	)
    print()
    print("# is an obstacle"	)
    print("- is the path taken by algorithm"	)


if __name__ == "__main__":
  multi_a_star(start, goal, n_heuristic)










'''simple docstring'''

def 						UpperCamelCase    (							):
    A__    =      [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

    A__    =      6
    A__    =      1
    A__    =      19_01

    A__    =      0

    while year < 20_01:
        day += 7

        if (year % 4 == 0 and year % 1_00 != 0) or (year % 4_00 == 0):
            if day > days_per_month[month - 1] and month != 2:
                month += 1
                A__    =      day - days_per_month[month - 2]
            elif day > 29 and month == 2:
                month += 1
                A__    =      day - 29
        else:
            if day > days_per_month[month - 1]:
                month += 1
                A__    =      day - days_per_month[month - 2]

        if month > 12:
            year += 1
            A__    =      1

        if year < 20_01 and day == 1:
            sundays += 1
    return sundays


if __name__ == "__main__":
  print(solution())



