*********+++++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++++++******
*******+++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++******
******+++++++;;;;;;;;;;;;;;;;;;;;;;;;+?;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++++****
****++++++++++;;;;;;;;;;;;;;;;;;;;;;+S%;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++****
**++++++++++;;;;;;;;;;;;;;;;;;;;;;;;S##;:;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+;;++++++++***
**+++++++++;;;;;;;;;;;;;;;;;;;;;;;;%###%;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++***
***++++++++;+;;;;;;;;;;;;;;;;;;;;;%#####S%?+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++++*
***++++++++;;;;;;;;;;;;;;;;;;;;;;%########S%?+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++*
**+++++++;;;;;;;;;;;;;;;;;;;;;;;?##########SS?;;;;;;;;;:;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++*
*+*+++++;;+;;;;;;;;;;;;;;;;;;;;;+?S##########?:;;;;;;:;;;;;;;;;;;;;::;;;;;;;;;;;;;;;;;;;;;;+++++++++
++++++++;;;;;;;;;;;;;;;;;;;;;;+????%SS######S+:;;;:;:;;;;;;;;;;::;;;;;;;;;;;;;:;;;;;;;;;;;;;++++++++
++++++++;;;;;;;;;;;;;;;;;;;;;:*#%??%%??S####?:;;;:;:;;;;:;;;;;;;;;::;;;;;;;;;;;;;;;;;;;;;;;;++++++++
++++++++;;;;;;;;;;;;;;;;;;;;;;;?****??*%S##%;:;::;:::;;;;:;;;;;;;;;:;;;;;;;;;::;;;;;;;;;;;;;;+++++++
+++++++;;;;;;;;;;;;;;:;;:::;;;;+***??*??%%+:::::::::::::;::;;::::::;:;;;;:;:::::;;;;;;;;;;;;;;++++++
+++++++;;;;;;;;;;;;::::;::::;::+??%?????**::::::::::::::::;;:::::::::;::::::::;::;;:;;;;;;;;;;;+++++
++++++;;;;;;;;;;;;::::::::::::::;;+*?%????*+::::::::::::::::::::::::::::::;::;;:::::;;;;;;;;;;;+++++
+++++++;;;;;;;;;;;::::::::::::;::::;??%%%???*;:::::::::::::::;:::::::::::::::::;:::;:;;;;;;;;;++++++
++++++;;;;;;;;;;::::::::::::::::;::;?%%%?????**;:::::::::::::::::::::::::::::::::::;;;;;;;;;;;++++++
++++++;;;;;;;;;;::::::::::::::::::;?SSSS%%%?????*;:::::::::::::::::::::::::::::::::;::;;;;;;;;++++++
++++++;;;;;;;;;:::::::::::::::::::;%SSSS%SS%%%???*+::::::::::::::::::::::::::::::::::::;;;;;;;;;;+++
++++;;;;;;;;;;;;::::::::::::::::::+SS%%%%SSS%%%%???+;::::::::::::::::::::::::::::::::;;;;;;;;;+;++++
++++;+;;;;;;;;;;::::;;;;:::::::::;%SSSSSSSSSSS%%%%??*;::::::::::::::::::::::::::::::::;;;;;;;;;;;+++
+++;+;;;;;;;;;;:::::+***+;;:::::;?S###SSS##SSSSS%%%%?*;:::::::::::::::::::::::::::::::;;;;;;;;;;;+++
++;;;;;;;;;;::::::::;++*****+;;;??%S####SSSSSSS%%%%%%??;:::::::::::::::::::::::::::::::;;;;;;;;;++++
+++;;;;;;;;;:::::::::;;;+*%%S%%%%SSS##########SSS%%%%??*;::::::::::::::::::::::::::::::;;;;;;;;;++++
+++;;;;;;;;;;;:::::::::::;?###S####SS##S#######SSS%%%???*:::::::::::::::::::::::::::::::;;;;;;;+++++
+++;;;;;;;;;;;:::::::::::::+S#S########S##SS###SS%%%%????;:::::::::::::::::::::::::::::::;;;;;;;++++
+++;;;;;;;;;;;:::::::::::::::;%########S###SSSSSS%%%?????+::::::::::::::::::::::::::::::;;;;;;;;++++
+++;;;;;;;;;::::::::::::::::::;S####%*;:?########S%%?????*::::::::::::::::::::::::::::::;;;;;;;;++++
++;;;;;;;;;;;;:::::::::::::::::*###S%%*:;S########SS%????*:::::::::::::::::::::::::::::::;;;;;;;++++
+++;;;;;;;;;:::::::::::::::::::;?#SSSS%;:*##########S%????:::::::::::::::::::::::::::::::;;;;;;;;+++
+++;;;;;;;;;;::::::::::::::::::::*%*?%%+:+S##SSS#####S%???:::::::::::::::::::::::::::::::;;;;;;;++++
+++;;;;;;;;;;::::::::::::::::::::::::;++:+S#SSSSS#####S%%?::::::::::::::::::::::::::::::;;;;;;;;;+++
+++++;;;;;;;;::::::::::::::::::::::::::::+SSSS########SS%+::::::::::::::::::::::::::::::;;;;;;;;++++
+++;;;;;;;;;;::::::::::::::::::::::::::::?SSSS########SSS;::::::::::::::::::::::::::::::;;;;;;;;+;++
+++;;;;;;;;;::::::::::::::::::::::::::::;%SSSS########SSS;::::::::::::::::::::::::::::::;;;;;;;;++++
++++;;;;;;;;;:::::::::::::::::::::::::::;%SSSS########SS?::::::::::::::::::::::::::::::;;;;;;;;;;;++
+++;;;;;;;;;;:::::::::::::::::::::::::::*SSSS########SS*:::::::::::::::::::::::::::::::;;;;;;;;;++++
+++++;;;;;;;;:::::::::::::::::::::::::::?#########SSS+;:::::::::::::::::::::::::::::::;;;;;;;;;;;+++
++++;;;;;;;;;;;::::::::::::::::::::::::*S########S?%+,::::::::::::::::::::::::::::::::;;;;;;;;;;;+++
++++++;;;;;;;;;:::::::::::::::::::::::+S##########%;,::::::::::::::::::::::::::::::::;;;;;;;;;;;++++
+++++;;;;;;;;;;;::::::::::::::::::::::%###########S::::::::::::::::::::::::::::::::;;;;;;;;;;;;+++++
++++++;;;;;;;;;;;;:::::::::::::::::::+###########S*::::::::::::::::::::::::::::::::;;;;;;;;;;;;+++++
++++++;;;;;;;;;;;;:::::::::::::::::::*#S#########*:::::::::::::::::::::::::::::::::;;;;;;;;;;;;+++++
+++++++++;;;;;;;;;:::::::::::::::::::;%########*;::::::::::::::::::::::::::::::::::;;;;;;;;;;;++++++
++++++;;;;;;;;;;;;;;::::::::::::::::::;######S%:,::::::::::::::::::::::::::::::;;::;;;;;;;;;;;++++++
+++++++++;;;;;;;;;;::::::::::::::::::::+####S%%?;::::::::::::::::::::::::::::;;;;;;;;;;;;;;;++++++++
+++++++++++;;;;;;;::::::::::::::::::::::%###S%?%?:::::::::::::::::::::::::::::;;;;;;;;;;;;;;+++++++*
+++++++++;;;;;;;;;;;::::::::::::::::::::;####S%%%;::::::::::::::::::::::::::::::::;;;;;;;;;;++++++++
*++++++++;;;;;;;;;;;:::::::::::::::::::::*###S%*+;::::::::::::::::::::::::::;;;;;;;;;;;;;;;;++++++**
**++++++++;;;;;;;;;;;:::::::::::::::::::::;?%?*+;::::::::::::::::::::::::::::::;;;;;;;;;;;;+++++++**
**++++++++++;;;;;;;;;;;:;:::::::::::::::::::***+;::::::::::::::::::::::::::::::;;;;;;;;;;;++++++++**
**++++++++;;;;;;;;;;;;;;;::;;:::::::::::::::;**+;;::::::::::::::::::::::::::::::;;;;;;;+++++++++++**
***++++++++++;;;;;;;;;;;;;;;;;:::::::::::::::***+;::::::::::::::::::::::::;;;;;;;;;;;+++++++++++****
****++++++++++;;;;;;;;;;;;:;:::::::::::::::::***+;;::::::::::::::::::::;;;;;;;;;;;;;;;+;++++++++****