Escriu un algorisme recursiu per a trobar la sortida 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

• Els moviments només es poden fer en horitzontal o vertical.
• Només hi ha un camí possible (i sempre n'hi ha un).

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#ooo#  ooo# #ooo# #ooo#
#o#o#o###o#o# #o#o# #o#o#
#ooo#ooooo#ooooo#ooooo#o#
#######################o#

Test Case 3

Input

11
###########_#
^ #       # #
# ### ##### #
#     #     #
# ##### #####
#     #     #
# ### # # ###
#   #   #   #
# ##### ### #
#     # #   #
#############

Output

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

Test Case 4

Input

11
#^###################
#     #       #     #
### ### # ### # ### #
#       # #   #   # #
# # ##### # # # ### #
# # #     # #   #   #
### ####### # ##### #
#       #   # #     #
# ##### # ####### # #
#     # #     #   # #
###################_#

Output

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

Test Case 5

Input

11
#^###############################################################################
# # #           # #   # #   #   #   #                 #               #         #
# # # # # ### # # # ### ### # # # ##### ### # # # ### # # # ####### # ### # # # #
#   # # #   # #   #         # #     #   # # # # # #   # # #       # #     # # # #
# ####### # # # # # ### ### # ### # # # # # ### ##### # ### ### ######### #######
#   # # # # # # #     # #   # #   #   # # #   #   # #   # # #   # #         #   #
### # # ##### ### # # ##### ##### # ### # ### ##### # ### # ### # ##### ####### #
# #     # # # #   # # #       #   # # #     # #     # #   #   # # #     #       #
# ##### # # # ### ### # ### ### # ### ##### # # ### ### ### ##### # # ### # ### #
#               #   # # #       # #         #   #     #       #     #     # #   #
##############################################################################_##

Output

#o###############################################################################
#o# #        ooo# #   # #   #   #   #  ooooooooooooooo#ooooooooooooooo#         #
#o# # # # ###o#o# # ### ### # # # #####o### # # # ###o#o# # ####### #o### # # # #
#o  # # #   #o#ooo#ooooooooo# #  ooo#ooo# # # # # #  o#o# #       # #ooooo# # # #
#o####### # #o# #o#o### ###o# ###o#o#o# # # ### #####o#o### ### #########o#######
#ooo# # # # #o# #ooo  # #  o# #  o#ooo# # #   #   # #ooo# # #   # #    ooo  #   #
###o# # #####o### # # #####o#####o# ### # ### ##### # ### # ### # #####o####### #
# #ooooo# # #o#   # # #    o  #ooo# # #     # #     # #   #   # # #  ooo#ooooooo#
# #####o# # #o### ### # ###o###o# ### ##### # # ### ### ### ##### # #o###o# ###o#
#      ooooooo  #   # # #  ooooo# #         #   #     #       #     #ooooo# # oo#
##############################################################################o##

Test Case 6

Input

21
#################################################################################
^     #     #   #   #     # # # #       # # #     #     # #   #   #             #
# ### # ### # ##### # # ### # # # ####### # # ### # # ### # ### # # ##### # # # #
# #   # # #     #     #   # #         # #     #   # #   # #     # #   # # # # # #
### ### # # # # # ##### ### # ##### ### ##### ##### # ### # ####### ### # ##### #
#         # # # #     # #       #       #       #   #   #       # #   #       # #
########### # ##### ####### ####### # # # ####### ##### ####### # ######### #####
#   # # #   #   #           #   # # # # # #   #   # #   # # #   #     #         #
### # # ####### # ### ##### # # # # ### # # ####### # # # # # # # ##### ### # ###
#   #         #   #   #       # # # #         #       #       #   # #   # # # # #
# ####### # ######### ########### ### # ##### ############### ##### ##### # ### #
#         # #         # #           # # #   # # # #     #   # #     #       #   #
##### ##### ####### ### ### ############### # # # # ####### # # ##### ##### # ###
# # #   # # #             #     # # #     #       #       #       # #   # #     #
# # # ### # ######### # ### ##### # # ##### ### # # ####### ### ### # # # ### ###
#     #     #     #   #   #   #       #     #   #     #     # #       #   # #   #
# ####### ##### # # # ### # ### ############# ####### # ##### # ######### # ### #
#   #         # # # # #     # # #         # #   #   #     # # #   # #       #   #
######### ### # ### ##### ### # # ### # # # ### # ####### # # # # # ### # #######
#         #           #       #     # # #               #     # #   #   #       _
#################################################################################

Output

#################################################################################
oooooo#ooooo#   #   #     # # # #       # # #     #     # #   #   #             #
# ###o#o###o# ##### # # ### # # # ####### # # ### # # ### # ### # # ##### # # # #
# #ooo#o# #ooo  #     #   # #ooooooo  # #     #   # #   # #     # #   # # # # # #
###o###o# # #o# # ##### ### #o#####o### ##### ##### # ### # ####### ### # ##### #
#  ooooo  # #o# #     # #  ooo  #  ooooo#       #   #   #       # #   #       # #
########### #o##### #######o####### # #o# ####### ##### ####### # ######### #####
#   # # #   #ooo#ooooooooooo#   # # # #o# #   #   # #   # # #   #     #         #
### # # #######o#o### ##### # # # # ###o# # ####### # # # # # # # ##### ### # ###
#   #         #ooo#   #       # # # #  ooooooo#       #       #   # #   # # # # #
# ####### # ######### ########### ### # #####o############### ##### ##### # ### #
#         # #         # #           # # #   #o# # #     #   # #     #       #   #
##### ##### ####### ### ### ############### #o# # # ####### # # ##### ##### # ###
# # #   # # #             #     # # #     #  ooooo#       #ooooo  # #ooo# #     #
# # # ### # ######### # ### ##### # # ##### ### #o# #######o###o### #o#o# ### ###
#     #     #     #   #   #   #       #     #   #ooooo#ooooo# #ooooooo#ooo# #   #
# ####### ##### # # # ### # ### ############# #######o#o##### # #########o# ### #
#   #         # # # # #     # # #         # #   #   #ooo  # # #   # #    o  #   #
######### ### # ### ##### ### # # ### # # # ### # ####### # # # # # ### #o#######
#         #           #       #     # # #               #     # #   #   #oooooooo
#################################################################################

Test Case 7

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######### ########### ##### ### # #
#   #   #       # #   #   #     # #     #  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# #   # #   #
# # ### # # # ##### ##### ### ##### ##### # # ##### # # # #########o### ### ### #
# #     #   #       #     #       #           #     #       #      ooooooooooooo#
###############################################################################o#

Test Case 8

Input

11
###########_#
^ #       # #
# ### ##### #
#     #     #
# ##### #####
#     #     #
# ### # # ###
#   #   #   #
# ##### ### #
#     # #   #
#############

Output

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