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