#@@@@@@@@@@@@@@@@@@@@@@#@@######S%???%#@@@@@#%?%S####@@@@@@@@@@@@@@@@#@@@###@##?
#@@@@@@@@@@@@@@@@@@@@@#########S?*++*%##S@@#S%***?%####@@@@@@@@@@@@@@@@@##@@@#S?
#@@@@@@@@@@@@@@@@@@@##########S%??*++?S?%@#%?+++++*?S#####@@@@@@@@@@@@@@@@@@@##%
S@@@@@@@@@@@@@@@@@#########@#####S?*+*?=*#S?*+++++++?S#######@@@@@@@@@@@@@@@@@#S
#@@@@@@@@@@@@@@@##########@@@@@@@#S?***-+S?*++*+???++?#########@@@@@@@@@@@@@@@@#
#@@@@@@@@@@@@@@##########@@@@@@@@@@#?+-:=?**?**%?SS?*+%#########@@@@@@@@@@@@@@@#
@@@@@@@@@@@@@@##########@@@@@@@@@@#S+;:::-*%%?%######??%S#########@@@@@@@@@@@@@#
@@@@@@@@@@@@@##########@@@@@@@@@@S-,,,:::::;*##@@@@@@SS%S###########@@@@@@@@@@@#
@@@@@@@@@@@#########S#@@@@@@@@@@#-,,,::::::::-#@@@@@@#%#SS%S########@@@@@@@@@@@#
@@@@@@@@@@@########SS#@@@@@@@@@@*:::::::::::::=#@@@@@@#@@@S%S########@@@@@@@@@@@
@@@@@@@@@#########SS#@@@@@@@@@@#-;;;:::::::::::+@@@@@@@#@@@@#S########@@@@@@@#@@
#@@@@@@@@########SSS@@@@@@@@@@@+;;;;;;;;;;::::::=#@@@@@##@@@#S#########@@@@@@###
#@@@@@@@@########SSS@@@@@@@@@@?;;:;----;;;;::::::-#@@@@#S@@@#SS#########@@@@@@##
#@@@@@@@########SSS#@@@@@@@@@@%%SS%%?*+===+?SSSS*+#@@@@@#@@@#SSS########@@@@@@##
@@@@@@@@#######SSSS#@@@@@@@@@@##@@@@@#%**%#@@@@#%+%@@@@@@@@@#SSSS#######@@@@@###
###@@@@#######SSSSS#@@@@@@@@@@#@@#@@@@S*=*S@@#%%#%S@@@@@@@@@#SSSS########@@@@###
##@@@@@#######SSSSSS@@@@@@@@@@#@#@@@@@S;:=S@@@#%%SS@@@@@@@@@%SSSSS#######@@@@###
##@@@@#######SSSSSSS@@@@@@@@@#S#S%SS#S*::;-?SS?+-;-S@@@@@@@#SSSSSS########@@@##@
##@@@@#######SSSSS%%#@@@@@@@@*=+%SS%*=-::::-*?*-:::;@@@@@@@@SSSSSSS########@@##@
#%#@@@#######SSSSS%%%#@@@@@@S-;;-==-;;;:::::;;;:::::S@@@@@@@#SSSSSS########@@@@@
##@@@########SSSSS%%%S@@@@@@#+---==---;::::::;;;;:::#@@@@@@@SSSSSSS########@@@@@
#@@@@#######SSSSSS%%%%S@@@@@@??**+====:,,::::;----;;#%@@@@@#SSSSSSSS#######@@@@@
@@@@########SSSSS%%%%%%#@@@@#SSS%*++*+??+=;:;;;-==--%%@@@@#S%SSSSSSS#######@@@@@
@@@@########SSSSS%%%%%%S#@@@@#SSS?*+=%@@S#+::;;-==;*@@@@#S%%%SSSSSSS#######@@@@@
@@@@########SSSSS%%%%%%%S#@@@#SSS%*=-?#@#-:,,:;-=-;?@@@#S%%%%SSSSSSS#######@@@@@
@@@@#######SSSSSS%%%%%%%%##@@@SSS%*++*%?*;:,::;--;:S@@#S%%%%%SSSSSSS#######@@@@#
@@@@#######SSSSSS%%%%%%%%###@@S%%%%%S#@@#@#%?-;;;:-@@#SS%%%%%SSSSSSS#######@@@@@
@@@########SSSSSS%%%%%%%%SS#S##%%%S#####S*==*+-;::%@@#S%%%%%%SSSSSSS#######@@@@@
@@@########SSSSSS%%%%%%%%%%SSS#S%SS###@@@@S*==-;:*@@@SSS%%%%%SSSSSSS#######@@@@@
@@@########SSSSSS%%%%%%%%%%%%SSSSSSSSSS%*+=-----=#@#S%%%%%%%%%SSSSSS########@@@@
@@@########SSSSSS%%%%%%????%%%%%###S?+==-:::;-=-=S%%%%%%%%%%%SSSSSSS#########@@@
@@@########SSSSSS%%%%%%%???%%%%%##@#SSSSS?+=+*=;;-=?%%%%%%%%%SSSSSSS#######@@@@@
@@@@#######SSSSSS%%%%%%%??????%S#@@@@@@@@#S?*+-;::=?%%%%%%%%%SSSSSSS##########@@
@#@@#######SSSSSS%%%%%%%??????S#%#@@@@@@@#%+**-:-???%%%%%%%%%SSSSSS###########@@
##@@@######SSSSSS%%%%%%???????%@@##@##@@@#%+*+*+%#%?%%%%%%%%%SSSSSS########@#@@@
S#@@@######SSSSSS%%%%%%%??????#@@@@SS#S%@#*S*=#@@#S%%%%%%%%%%SSSSSS##########@@@
##@@@#######SSSSS%%%%%%%%????%@@@@@@@@#S@SS@@@@@@#S%%%%%%%%%SSSSSSS##########@@@
##@@@#######SSSSS%%%%%%%????%#@@@@@@@@@@@@@@@@@@@@#S%%%%%%%%SSSSSS#########@#@@@
#@@@#######SSSSSSS%%%%%%??%#@@@@@@@@@@@@@@@@@@@@###S%S%%%%%SSSSSSS############@@
#@@@@######SSSSSSS%%%%%%%#@@@@@@@@@@@@@@@@@@@@@###%?*S#%%%SSSSSSSS############@@
#@@@@######SSSSSSS%%%%%S#@@@@@@@@@@@@@@S*%S@@##%#S*+-*SS%%SSSSSSSS############@#
###@#######SSSSSSSS%%S#@@@@##@@##@@@@@@#*+#@#%?*S%?*;=?%+%SSSSSSS#########@@####
@@@@########SSSSSSSS#@@##@@SS#@SS##@@@@@##@@#%+*S?*+;;=?-=%#SSSSS#########@@####
@@@@@@#######SSSSS#@@@SS#@#??S@%%S?###@#@S@S?==?%---;;-%-;*#SSSS################
@@@@@@#######SS#####@#%S#@S**%@S*%*SSS@@@@@S=;+*%-;;;;=%;;=%%?SSS##############@
@@@@@@#########@@#S#@S%%%#S*+?##+*+%SS###?##+-+*?;;;:;+*;:;*?=*??S#############@
@@@@@@@#######S##%%#@S%?*#%*=?##*--=###SS?@#+==?=;;;:;*+::;*%-=+-+S######S######
@@@@@@@###@@#%?%S*?#S%+*=S?+=+S%?;;+S*%##*SS%;-%=;;;:;*=::=%S=-+;;+S###SS####@@@
@@@@@@@###@@#=*??=?#S?=*=S?+==?S===##??S#S##=;=*+;;;;-?-;;=*%=;+;:;?########@@@@
#@@@@@@#%%#@#**?*=%##*-*=%%=--*#-=+%S?S%S?SS=-?*-;;;;=?;;:;=%+;+-;;*SS#%###@@@@@
#@@@@###%*?#@S?S==%#S+-++?S*--+S=;=*S%%##?##*??*;;;;;=?-;:;=?+;+=-;?S%%*S?%#@@@@
S@@@@SS%?++#@@##=?S#%+++=?S+--=S*:;?SS%S#%SS?*S?-;;;;*%-;::+%=-=*+=SS?%*%++S#@#@
S#@@#%SS*?*###@#?%S#*+?+=+S+;;=%?;;*#S%#S%##?+%+-;;;;%?;;:;+?=-*??*S%?*+*++%S##@
#####%SS%*=?#S@##SS#**?+=+S*;;-??=;?S%#@@SS#%+%+-;;;-%S=;;;+%*+%SS%#?%*==*%S%%#@
###S#SS%??+=%#@@@#S#%??+=+S*;;-%?=-?S-*##@@@?+S+;;;;-%%=-;;+%??%####%S+=*%%S??#@
@#@##@@S*??++#@@@@###S%+++S*-;=SS*=?S+%@#S##**%=;;;-=S+----?%*%S#@@@@S???%SS??S@
@#@@@@@@S%#S%#@@@@###S%**%#*=--S#+=*#??S@#@@SSS+----+S+---=%%*S#@@@@@@#S%??%#S##
@##@@@@@@#S@@@@@@@@###S%?%#?+--SS?+?#S%S#######*=-=++S*-==+S??#@@@@##@#SSSS#@###
@SS###@@@@@#S@@@@@@@#@##S%#%%*+SS?*%#SS@#S#@@@S?+=***S*+*+?#%%#@@@@@@@#SS##@@@@#
@##S%*%#@@@@@@@@@@@@@@@@#S#SS%?#S%?S###@@SS####%*?%?%S?*?*S#SS@@@@@@@@@@@@@@@@##
@@##S??%S@@@@@@@@@@@@@@@@#####S###S#@@@@@##@@@#S?%%%S#%%%%S##@@@@@@@@@@@@#S#@S##
@@@@@S%%S##@@@@@@@@@@@@@@@#####@@###@@@@@@#@@@##SSSS##SSS####@@@@@@@@@@#####%S##
@@@@@@####S#@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@@###S#@#######@@@@@@@@@#SS#@#?%###
#@#@@@@####%#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##@@@@#@#@@@@@@@@@@#S####S?S#@#S
S###@@@@###SS@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##@@@@@@@@@@@@@@@@@@@#SSS#SS####SS
S#SSS#@@##SS#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######@##S##