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