Escriu un algorisme recursiu per a trobar la sortida més curta d'un laberint.

Input Format

En primer lloc hi ha el nombre de línies que té el laberint. A continuació ve el laberint.

Cada caracter significa:

'#' mur
' ' cami
'^' inici
'_' sortida

Constraints

No hi ha

Output Format

S'imprimirà el laberint marcant amb el caracter 'o' el cami des de l'inici fins a la sortida.

Test Case 1

Input

5
#^#######
#     # #
# ### # #
#   #   #
#######_#

Output

#o#######
#ooooo# #
# ###o# #
#   #ooo#
#######o#

Test Case 2

Input

5
#^#######
#     # #
# ### # #
#       #
#######_#

Output

#o#######
#o    # #
#o### # #
#ooooooo#
#######o#

Test Case 3

Input

5
#^#######
#       #
# ### # #
#       #
#######_#

Output

#o#######
#o      #
#o### # #
#ooooooo#
#######o#

Test Case 4

Input

5
#^#######
#       _
# ### # #
#       #
#########

Output

#o#######
#oooooooo
# ### # #
#       #
#########

Test Case 5

Input

5
#^#######
#     # _
# ### # #
#       #
#########

Output

#o#######
#o    #oo
#o### #o#
#ooooooo#
#########

Test Case 6

Input

5
#^#######################
# #   #     # #   # #   #
# # # ### # # # # # # # #
#   #     #     #     # #
#######################_#

Output

#o#######################
#o#ooo#  ooo# #ooo# #ooo#
#o#o#o###o#o# #o#o# #o#o#
#ooo#ooooo#ooooo#ooooo#o#
#######################o#

Test Case 7

Input

5
#^#######################
# #   #     # #   # #   #
# # # ### # # # # # # # #
#               #       #
#######################_#

Output

#o#######################
#o#   #     # #ooo# #   #
#o# # ### # # #o#o# # # #
#ooooooooooooooo#ooooooo#
#######################o#

Test Case 8

Input

5
#^#######################
# #   #     # #   # #   #
# # # ### # # # # # # # #
#                       #
#######################_#

Output

#o#######################
#o#   #     # #   # #   #
#o# # ### # # # # # # # #
#ooooooooooooooooooooooo#
#######################o#

Test Case 9

Input

5
####################_####
# #         # #   ##    #
# # # ### # # # # ##### #
#     #                 #
##^######################

Output

####################o####
# #ooooooo  # #   ##oooo#
# #o# ###o# # # # #####o#
# oo  #  ooooooooooooooo#
##o######################

Test Case 10

Input

51
#################################################################################
_ #   #     #   #             #   # #   # #   #         #       #   #     #   # #
# # ### # ### # # # # ####### # # # # # # ### # ####### ### ### ### # # # ### # #
#             # # # # #       # # #   #       # #   #       #   #     # # # #   #
# ### ### ### ######### # ##### ### # ### ######### ##### ##### ##### ##### # ###
# #   # # # #       # # # # # #   # # #   #   #     #     # # #       #   #   # #
# # # # # # ### # # # # # # # ### # # ### # # ### ####### # # # ####### # # ### #
#   #     #     # #     #     #   # # #     # #           #         #   # # #   #
# # ############### # ####### ### ##### ### ### ##### ### # # ####### ### # ### #
# # #     #         #   # #           # # #     #     #   # #   #       # #     #
# # ### # ### ##### # # # ### ##### ### # # ### ############# ##### # ### # # # #
# # #   #     #     # # # # #   #   #     # #   #       #       #   # #     # # #
########### ### # # ##### # ####### ####### # # ### ####### ### # ### # # # ### #
#   #       # # # # # # # # # #   #   #   # # #   # # #     #   # #   # # #   # #
# # # ##### # # # ### # # # # # ### ### ### ##### # # ####### ########### # # ###
# #   #     #   #   #         # #             #           #   #     #     # #   #
### ### ##### # ##### ##### # # ### ####### # # ### # ### ####### ### ##### # # #
# # #     # # #       # #   # #     # #   # # # #   # #     #         #   # # # #
# # # ### # ##### ### # ####### ### # ### # ######### # ### ##### ### # # ##### #
# # # #   # # #     #   #   #     #   #     #     # # # #       # #     # # #   #
# ### # # # # ##### ### # ##### # ######### ### # # # ####### ##### ### # # ### #
# # # # # #   #     #   #   # # # #   # #     # #   #   #       #     # # #     #
# # ######### # ### ####### # ### ### # ##### # ##### ### ### # ############### #
# #       # #   # #     #   # #     #             #   # #   # # #           #   #
# ### ##### ### # # ####### # # # ### ####### ######### ########### ##### ### # #
#   #   #       # #   #   #     # #     #     # #       #     #     # # # #   # #
# ### ### # # # # # ##### ##### # ######### ### # ### # # ####### # # # ### #####
#   #     # # # #     # #       # # # #     #       # #     # #   #     # #     #
# ### ######### # # ### # ####### # # # ### ### ### ### # ### # ### ### # ##### #
#   #       #   # # # #     # #     #   #       #     # #   #   #   #       #   #
# ##### # ########### ##### # # ### ####### ### # ### ##### # ### # ########### #
#     # #       #   #   #   #   #       # # #   # #   #     #   # # #       # # #
### ####### ####### ### # ### # ### ##### ##### ### ##### # ### # ### ####### # #
#   #   #             # # #   # #     #       #   # #   # # #   #   # # # #   # #
# ### ### ##### ##### # ####### # ### # ####### ##### ### ### # # # # # # # # # #
#     #     # #     #   # #     #   # #     #   # # # # #     # # # #   # # #   #
### ####### # # # ##### # ######### ### # ##### # # # # ### ### ####### # # # ###
# #       # # # #   # # #       # # # # #     # #           # # # #   #     #   #
# # # ### # # ##### # # # ##### # ### ### # # ####### ####### ### # ##### ##### #
#   # #       #       #   #   #       #   # # #           #     #     #     #   #
# ######### ### ### # ### # ### # # # ##### ##### ##### ### ### # # ##### # #####
#   # #     # # #   #   # # # # # # # #     # # #     #     #   # # #     # #   #
### # ### ### ##### # ### # # ### # ####### # # # ### ######### # ### ####### # #
#   #   #       # # #   #     # # # #   # # # #   #     #   #     # #         # #
# ##### # ##### # ### ######### ### ### # # # # # ##### ### ### # # # ####### # #
# # # # # #   #     #       #   #   # #   #   # #   #   #     # #       # #   # #
# # # # ### ### # ##### # # # ### ### # # ### ##### ### ### ### ### # ### #######
#   #   # #   # #   #   # #     #   #   # # # #     # # #     #   # # #   # #   ^
# # ### # # # ##### ##### ### ##### ##### # # ##### # # # ######### ### ### ### #
# #     #   #       #     #       #           #     #       #                   #
#################################################################################

Output

#################################################################################
oo#   #     #   #             #   # #   # #   #         #       #   #     #   # #
#o# ### # ### # # # # ####### # # # # # # ### # ####### ### ### ### # # # ### # #
#ooooooooooooo# # # # #ooo    # # #   #       # #   #       #   #     # # # #   #
# ### ### ###o#########o#o##### ### # ### ######### ##### ##### ##### ##### # ###
# #   # # # #ooooooo# #o#o# # #   # # #   #   #     #     # # #       #   #   # #
# # # # # # ### # #o# #o#o# # ### # # ### # # ### ####### # # # ####### # # ### #
#   #     #     # #ooooo#ooooo#   # # #     # #           #         #   # # #   #
# # ############### # #######o### ##### ### ### ##### ### # # ####### ### # ### #
# # #     #         #   # #  ooooooo  # # #     #     #   # #   #       # #     #
# # ### # ### ##### # # # ### #####o### # # ### ############# ##### # ### # # # #
# # #   #     #     # # # # #   #  o#     # #   #       #       #   # #     # # #
########### ### # # ##### # #######o####### # # ### ####### ### # ### # # # ### #
#   #       # # # # # # # # # #   #o  #   # # #   # # #     #   # #   # # #   # #
# # # ##### # # # ### # # # # # ###o### ### ##### # # ####### ########### # # ###
# #   #     #   #   #         # #  ooooooooo  #           #   #     #     # #   #
### ### ##### # ##### ##### # # ### #######o# # ### # ### ####### ### ##### # # #
# # #     # # #       # #   # #     # #   #o# # #   # #     #         #   # # # #
# # # ### # ##### ### # ####### ### # ### #o######### # ### ##### ### # # ##### #
# # # #   # # #     #   #   #     #   #    o#     # # # #       # #     # # #   #
# ### # # # # ##### ### # ##### # #########o### # # # ####### ##### ### # # ### #
# # # # # #   #     #   #   # # # #   # #  ooo# #   #   #       #     # # #     #
# # ######### # ### ####### # ### ### # #####o# ##### ### ### # ############### #
# #       # #   # #     #   # #     #        o    #   # #   # # #           #   #
# ### ##### ### # # ####### # # # ### #######o######### ########### ##### ### # #
#   #   #       # #   #   #     # #     #  ooo# #ooooooo#     #     # # # #   # #
# ### ### # # # # # ##### ##### # #########o### #o### #o# ####### # # # ### #####
#   #     # # # #     # #       # # # #    o#  ooo  # #ooo  # #   #     # #     #
# ### ######### # # ### # ####### # # # ###o###o### ### #o### # ### ### # ##### #
#   #       #   # # # #     # #     #   #  ooooo#     # #ooo#   #   #       #   #
# ##### # ########### ##### # # ### ####### ### # ### #####o# ### # ########### #
#     # #       #   #   #   #   #       # # #   # #   #  ooo#   # # #       # # #
### ####### ####### ### # ### # ### ##### ##### ### #####o# ### # ### ####### # #
#   #   #             # # #   # #     #       #   # #   #o# #   #   # # # #   # #
# ### ### ##### ##### # ####### # ### # ####### ##### ###o### # # # # # # # # # #
#     #     # #     #   # #     #   # #     #   # # # # #ooo  # # # #   # # #   #
### ####### # # # ##### # ######### ### # ##### # # # # ###o### ####### # # # ###
# #       # # # #   # # #       # # # # #     # #    ooooooo# # # #   #     #   #
# # # ### # # ##### # # # ##### # ### ### # # #######o####### ### # ##### ##### #
#   # #       #       #   #   #       #   # # #      ooo  #ooooo#     #     #   #
# ######### ### ### # ### # ### # # # ##### ##### #####o###o###o# # ##### # #####
#   # #     # # #   #   # # # # # # # #     # # #     #ooooo#  o# # #     # #   #
### # ### ### ##### # ### # # ### # ####### # # # ### #########o# ### ####### # #
#   #   #       # # #   #     # # # #   # # # #   #     #   #  ooo# #         # #
# ##### # ##### # ### ######### ### ### # # # # # ##### ### ### #o# # ####### # #
# # # # # #   #     #       #   #   # #   #   # #   #   #     # #ooo    # #   # #
# # # # ### ### # ##### # # # ### ### # # ### ##### ### ### ### ###o# ### #######
#   #   # #   # #   #   # #     #   #   # # # #     # # #     #   #o# #   # #  oo
# # ### # # # ##### ##### ### ##### ##### # # ##### # # # #########o### ### ###o#
# #     #   #       #     #       #           #     #       #      ooooooooooooo#
#################################################################################

Test Case 11

Input

51
#################################################################################
_ #   #     #   #             #   # #   # #   #         #       #   #     #   # #
# # ### # ### # # # # ####### # # # # # # ### # ####### ### ### ### # # # ### # #
#   # # #     # # # # #       # # #   #       # #   #       #   #     # # # #   #
# ### ### ### ######### # ##### ### # ### ######### ##### ##### ##### ##### # ###
# #   # # # #       # # # # # #   # # #   #   #     #     # # #       #   #   # #
# # # # # # ### # # # # # # # ### # # ### # # ### ####### # # # ####### # # ### #
#   #     #     # #     #     #   # # #     # #           #         #   # # #   #
# # ############### # ####### ### ##### ### ### ##### ### # # ####### ### # ### #
# # #     #         #   # #           # # #     #     #   # #   #       # #     #
# # ### # ### ##### # # # ### ##### ### # # ### ############# ##### # ### # # # #
# # #   #     #     # # # # #   #   #     # #   #       #       #   # #     # # #
########### ### # # ##### # ####### ####### # # ### ####### ### # ### # # # ### #
#   #       # # # # # # # # # #   #   #   # # #   # # #     #   # #   # # #   # #
# # # ##### # # # ### # # # # # ### ### ### ##### # # ####### ########### # # ###
# #   #     #   #   #         # #             #           #   #     #     # #   #
### ### ##### # ##### ##### # # ### ####### # # ### # ### ####### ### ##### # # #
# # #     # # #       # #   # #     # #   # # # #   # #     #         #   # # # #
# # # ### # ##### ### # ####### ### # ### # ######### # ### ##### ### # # ##### #
# # # #   # # #     #   #   #     #   #     #     # # # #       # #     # # #   #
# ### # # # # ##### ### # ##### # ######### ### # # # ####### ##### ### # # ### #
# # # # # #   #     #   #   # # # #   # #     # #   #   #       #     # # #     #
# # ######### # ### ####### # ### ### # ##### # ##### ### ### # ############### #
# #       # #   # #     #   # #     #             #   # #   # # #           #   #
# ### ##### ### # # ####### # # # ### ####### ######### ########### ##### ### # #
#   #   #       # #   #   #     # #     #               #     #     # # # #   # #
# ### ### # # # # # ##### ##### # ######### ### # ### # # ####### # # # ### #####
#   #     # # # #     # #       # # # #     #       # #     # #   #     # #     #
# ### ######### # # ### # ####### # # # ### ### ### ### # ### # ### ### # ##### #
#   #       #   # # # #     # #     #   #       #     # #   #   #   #       #   #
# ##### # ########### ##### # # ### ####### ### # ### ##### # ### # ########### #
#     # #       #   #   #   #   #       # # #   # #   #     #   # # #       # # #
### ####### ####### ### # ### # ### ##### ##### ### ##### # ### # ### ####### # #
#   #   #             # # #   # #     #       #   # #   # # #   #   # # # #   # #
# ### ### ##### ##### # ####### # ### # ####### ##### ### ### # # # # # # # # # #
#     #     # #     #   # #     #   # #     #   # # # # #     # # # #   # # #   #
### ####### # # # ##### # ######### ### # ##### # # # # ### ### ####### # # # ###
# #       # # # #   # # #       # # # # #     # #           # # # #   #     #   #
# # # ### # # ##### # # # ##### # ### ### # # ####### ####### ### # ##### ##### #
#   # #       #       #   #   #       #   # # #           #     #     #     #   #
# ######### ### ### # ### # ### # # # ##### ##### ##### ### ### # # ##### # #####
#   # #     # # #   #   # # # # # # # #     # # #     #     #   # # #     # #   #
### # ### ### ##### # ### # # ### # ####### # # # ### ######### # ### ####### # #
#   #   #       # # #   #     # # # #   # # # #   #     #   #     # #         # #
# ##### # ##### # ### ######### ### ### # # # # # ##### ### ### # # # ####### # #
# # # # # #   #     #       #   #   # #   #   # #   #   #     # #       # #   # #
# # # # ### ### # ##### # # # ### ### # # ### ##### ### ### ### ### # ### #######
#   #   # #   # #   #   # #     #   #   # # # #     # # #     #   # # #   # #   ^
# # ### # # # ##### ##### ### ##### ##### # # ##### # # # ######### ### ### ### #
# #     #   #       #     #       #           #     #       #                   #
#################################################################################

Output

#################################################################################
oo#   #     #   #             #   # #   # #   #         #       #   #     #   # #
#o# ### # ### # # # # ####### # # # # # # ### # ####### ### ### ### # # # ### # #
#o  # # #ooooo# # # # #ooo    # # #   #       # #   #       #   #     # # # #   #
#o### ###o###o#########o#o##### ### # ### ######### ##### ##### ##### ##### # ###
#o#ooo# #o# #ooooooo# #o#o# # #   # # #   #   #     #     # # #       #   #   # #
#o#o#o# #o# ### # #o# #o#o# # ### # # ### # # ### ####### # # # ####### # # ### #
#ooo#ooooo#     # #ooooo#ooooo#   # # #     # #           #         #   # # #   #
# # ############### # #######o### ##### ### ### ##### ### # # ####### ### # ### #
# # #     #         #   # #  ooooooo  # # #     #     #   # #   #       # #     #
# # ### # ### ##### # # # ### #####o### # # ### ############# ##### # ### # # # #
# # #   #     #     # # # # #   #  o#     # #   #       #       #   # #     # # #
########### ### # # ##### # #######o####### # # ### ####### ### # ### # # # ### #
#   #       # # # # # # # # # #   #o  #   # # #   # # #     #   # #   # # #   # #
# # # ##### # # # ### # # # # # ###o### ### ##### # # ####### ########### # # ###
# #   #     #   #   #         # #  ooooooooo  #           #   #     #     # #   #
### ### ##### # ##### ##### # # ### #######o# # ### # ### ####### ### ##### # # #
# # #     # # #       # #   # #     # #   #o# # #   # #     #         #   # # # #
# # # ### # ##### ### # ####### ### # ### #o######### # ### ##### ### # # ##### #
# # # #   # # #     #   #   #     #   #    o#     # # # #       # #     # # #   #
# ### # # # # ##### ### # ##### # #########o### # # # ####### ##### ### # # ### #
# # # # # #   #     #   #   # # # #   # #  ooo# #   #   #       #     # # #     #
# # ######### # ### ####### # ### ### # #####o# ##### ### ### # ############### #
# #       # #   # #     #   # #     #        o    #   # #   # # #           #   #
# ### ##### ### # # ####### # # # ### #######o######### ########### ##### ### # #
#   #   #       # #   #   #     # #     #    ooooooooooo#     #     # # # #   # #
# ### ### # # # # # ##### ##### # ######### ### # ### #o# ####### # # # ### #####
#   #     # # # #     # #       # # # #     #       # #ooo  # #   #     # #     #
# ### ######### # # ### # ####### # # # ### ### ### ### #o### # ### ### # ##### #
#   #       #   # # # #     # #     #   #       #     # #ooo#   #   #       #   #
# ##### # ########### ##### # # ### ####### ### # ### #####o# ### # ########### #
#     # #       #   #   #   #   #       # # #   # #   #  ooo#   # # #       # # #
### ####### ####### ### # ### # ### ##### ##### ### #####o# ### # ### ####### # #
#   #   #             # # #   # #     #       #   # #   #o# #   #   # # # #   # #
# ### ### ##### ##### # ####### # ### # ####### ##### ###o### # # # # # # # # # #
#     #     # #     #   # #     #   # #     #   # # # # #ooo  # # # #   # # #   #
### ####### # # # ##### # ######### ### # ##### # # # # ###o### ####### # # # ###
# #       # # # #   # # #       # # # # #     # #    ooooooo# # # #   #     #   #
# # # ### # # ##### # # # ##### # ### ### # # #######o####### ### # ##### ##### #
#   # #       #       #   #   #       #   # # #      ooo  #ooooo#     #     #   #
# ######### ### ### # ### # ### # # # ##### ##### #####o###o###o# # ##### # #####
#   # #     # # #   #   # # # # # # # #     # # #     #ooooo#  o# # #     # #   #
### # ### ### ##### # ### # # ### # ####### # # # ### #########o# ### ####### # #
#   #   #       # # #   #     # # # #   # # # #   #     #   #  ooo# #         # #
# ##### # ##### # ### ######### ### ### # # # # # ##### ### ### #o# # ####### # #
# # # # # #   #     #       #   #   # #   #   # #   #   #     # #ooo    # #   # #
# # # # ### ### # ##### # # # ### ### # # ### ##### ### ### ### ###o# ### #######
#   #   # #   # #   #   # #     #   #   # # # #     # # #     #   #o# #   # #  oo
# # ### # # # ##### ##### ### ##### ##### # # ##### # # # #########o### ### ###o#
# #     #   #       #     #       #           #     #       #      ooooooooooooo#
#################################################################################