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