??*******+++++++++++++++++++;;;;;;;;;;;;;;;;;;;+;+;;;;;;;;;+++++++++++++++++++++++***************???
?*******+++++++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++++******??
******+*+++++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++;+++++++++*******
*****+++++++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+;+;+++++++++*******
*******+++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++******
****++++++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*S+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++++*****
*****+++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;S@S+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++****
*****+++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;%##S%+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++****
**+*+*+++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;?@##S%S?+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++++**
**++++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;?@#######*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++**
*++++++++;++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+*?S##@#@S?+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++**
*+++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+%???S##@S+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+;+++++++**
++++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*??%%S%*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++*
+++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+*????*++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++
++*+++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+?%??????*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++
++++++++;+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;?%%%%%??????+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++++
+++++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+%%%%%%%%%%%%?;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++
++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+%%%%%%%%%%%%%*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+;;;+++++
++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+##S%%%%%%%%%%?;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++
++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;?#S####SSS%%%%?;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+;++++++
++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;%##S#@@###S%%%%+:;::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++
++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;?%SS######SS%%%*:;::;;;:;:;;;;;;;;;;;;;;;;;;;;;;;;;;+++++
++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;%SSSSS####SS%%%?;;;:;;::;;;;:::;;;;;:;::::;;;;;;;;;++++++
+++++++;;;;;;;;:;;;;;;;;;;;;;;;;;;;;;;;;;:;%S%%%%####SSS%%%+:;::;;::;;;;;:;;;:::::;;;;;;;;;;;;++++++
++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;:;;;;;;;:;????%S#####SSSS%*;;::::::::;;;;:;;;:::::;::;;;;;;;;++++++
++++;;;;;;;;;;;;;;;;::;;;;::;:;;;;;;;;;;;;;;;;;%#######SSSS%+:;;::::::::::;;;;:::::::;;;;;;;;;+++**?
++++;;;;;;;;;;;;;;;::;;;:;;;:;;:;;:;;;:;;;;;;:+S###########S*:;::::::;:::::;;;::;;::;;;;;;;;;+++*???
+++++;;;;;;;;;;;;;;;::;:;;:;:::::;;:;;:;;;;;;:*############S?;;::::::;;::::::::::;::;:;;;;;;;;+*????
++++;;;;;;;;;;;;;;;;;;:::;;;:;;:::;;;:;;:;;:::*###SS####SSSS+::::::::;:::::::::::::::::;;;;;;;;*%%%%
++++++;;;;;;;;;;;;;:;;:::;;::;::::::::::::::::+S###########%;::::::::::::::::::::::::::;;;;;;;+*??*?
++++++;;;;;;;;:;;:;:::;::;;:;;:::;;::::::::::::%###########*:::::::;:::::::::::::::::::;;;;;;+******
+++++;;;;;;;;:;;;:;;::::;::::::::;::::::::::::;###########S;::::::::::::::::::::::::::;;;;;+*???????
++++;;;;;;;;;;:;;::;:::::::::::;::::::::::::::+###########*::::::::::::::::::::::;;;+;;;;+*??%%%%%??
++++;;;;;;;;;;;;:::::::::::::::::;;:::::::::::?##########?::::::::::::::::::::::;*?***++??%%%%%?*?%%
++++;;;;;;;;;;;;::::;:::::::::::::::::;;:::;;;?SS#######?:::::::::::::::::::::::;;++???%%%%%?*++++?%
++++;;;;;;;;;;;;:::::::::::::::;:::;::::::::;::%#######S+:::::::::::::::::::::::::::+*??*+;;;;;++++?
++++;;;;;;;;;;;:::::::::::::::::::;:::::::::;::*#SSSSSSS%;::::::::::::::::::::::::::::;+;;;;;;;+++++
+++++;;;;;;;;;:::::::::::::::::::::::::::::::::;SSS%*+###*:::::::::::::::::::::::::;:;:;++;;;;;+++++
+++++;;;;;;;;;::::::::::::::;:::::::::::::::::::*%?+;:?%*;:::::::::::::::::::::::;::::+*?%*+++++++++
++++++;;;;;;;;::::::::::::::;:::::::::::::::::::::++;;:+;;::::::::::::::::::::::::::;?#####%??*??***
+++++;;;;;;;;;;;;:::::::::::::::::::::::::::::::::;++;:++;::::::::::::::::::::::::+?S#####S????????%
++++++++;;;;;;;;;::::::::::;:::::::::::::::::::::::++;;;+;;:::::::::::::::::::::+%#####@#@%++++%SSSS
+++++++;;;;;;;;;::::::::::::;;+;;;;;;;;;;;;;;;::::;;+;;**+;:::::::::::::::::::;%######S?+??****%####
++++++;;+;;;;;;::;;::::::::::;+***+++++++++++++;;;;;;++??*+;;;;;:::::;:::::::*#@###@#?;:+?S%???%%%%%
+++++++;;;;;;;;;;;:::::::::::::;+????*??*??**?*******+++++++;;;:::::+;;;:::;?######%*;;*S##S%%%%%%%%
+++++++++;;;;;;;;;;::::::::::::::;*%????*?%??%??%?*%?*??*??*******++++++;;*######S*+++*?%%SSSSSSSSSS
+++++++;;;;;;;;;;;;;:::::::::::::::+%%%????%%%??%%??%?%%?%%?%S%%%%%%?*+***S####S%%%%?????*??%%%%%%%%
+++++++;;;;;;;;;;;;;::::::::::::::::;++****????????????%%%%%%S%%%%S%%?+*??%%SS%%%%%%%S%???%%%%%%%%?%
*+++++++++;;;;;;;;;;;::;;::::::::::::::::::::;;;++++***????%%%%%%%SS%%?*?%%%%%%%%S%SS%%S#S%%%%%%%%??
*++++++++;;;;;;;;;;;;;::;:::::::;;;;;;;++;;++++++++;;;;;;;;++++***??%%%%%%%%%%%%%%%%%%SSSSSSS%%%%%??
**++++++++;;;;;;;;;;;;;;::;:::::;;;;;++++++++++++++++++++++++++++++*******?*?????%??%%%???**?%%?????
**+++++++++;;;;;;;;;;;;;;:;:;:;:::;;;;;;;;;;;;;;;+;;;;;;;;;;;;;;;;;;;;;;;;++++++++++**********??????
****++++++++;;;;;;;;;;;;::;;:::::::;::::::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++++********??????
****+*+++++++;;;;;;;;;;;;;;::;:::::::;;;::::;;;;;+;;;+;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++**********??
*****++++++++;;;;;;;;;;;;;;;;;:;:::::::::::;;;;;+;;++++++;;;;;;;;;;;;;;;;;;;;;;;;;;++++++++*******??