*********+++++++++;;;;;;;;;;;;;;;;;;;;;;+*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++++*******
*******++++++++;;;;;;;;;;;;;;;;;;;;;;;;+S*:;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++++*******
*****+++++++++;;;;;;;;;;;;;;;;;;;;;;;;+S#%:;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++++*****
****+++++++++;;+;;;;;;;;;;;;;;;;;;;;;+S###+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++++*****
***+++++++++;;;+;;;;;;;;;;;;;;;;;;;:+S#####%?*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++++++****
**++*++++++;;;;;;;;;;;;;;;;;;;;;;;;+S#######S%%*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++++++***
****+++++++;+;;;;;;;;;;;;;;;;;;;;;;%##########S%+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++++**
+**++++++++;;;;;;;;;;;;;;;;;;;;;;:;*%S#########S+:;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++++++**
**+++++++;;;;;;;;;;;;;;;;;;;;;;;;*???%S########%;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++*
++++++++++;;;;;;;;;;;;;;;;;;;;;;;SS??%%%?S###@S;;;;;;;;;;;;;;;;;;;;;;:;;;;;;;;;;;;;;;;;;;;;++++++++*
+*+++++++;;;;;;;;;;;;;;;;;;;;;;;:***??*?*%S##S*:;;;;;;;;;;;;;;;:::;;;;;;;;;;;;;;;;;;;;;;;;;;++++++++
+++++++;;;;;;;;;;;;;;;;;;;;;;;;::+*???????S%*;:::;;:;;;;;;;;;;;;;;;;;;;;;;;;:;;;;;;;;;;;;;;+++++++++
+++++++;;;;;;;;;;;;;;;;;;;;;;;:::;*?%%?????*:::;;::::;;::;;;;;;;;;;;:;;:;;;;;;;;;;;;;;;;;;;;;+++++++
+++++++;;;;;;;;;;;;;::;;:::;;::::::;+**???%%*+;:::::::::::::::::::::;;:;;;:::::;;;;;;;;;;;;;;+++++++
+++++++;;;;;;;;;;;::::::::::;:::::::::*%%%%???*+;::::::::::;;:::::::::;:::;;;:;;;;;;;;;;;;;;;+++++++
++++++;;;;;;;;;;;;:::::::::::;:::::::+%%S%%%????*+;:::::::::::::::::::::::::::::::;;;;;;;;;;;;++++++
+++++++;;;;;;;;;;:::::::::::::::::::;%SSSSSSS%%%??*;::::::::::::::::::::::::::::;;:;;;;;;;;;;;++++++
++++++;;;;;;;;;;;;:::::::::::::::::;%S%%%%%%SS%%%%??+:::::::::::::::::::::::::::;::::;;;;;;;;+++++++
+++++;;;;;;;;;;;;:::::::::::::::::+%SSSSSSS#SSSS%%%%?+:::::::::::::::::::::::::::::;;;;;;;;;;;;+++++
++++++;;;;;;;;;::::::::::::::::::*%%S###SS#SSSSSSS%%%?+::::::::::::::::::::::::::::::;;;;;;;;;;;++++
++++;;;;;;;;;;;::::::::::::::::;*??%S#####SSSSSSSSS%%%?*;::::::::::::::::::::::::::::;;;;;;;;;;;++++
++++;;;;;;;;;;;;::::::::::::::;%#####S##########SSSS%%%?*;::::::::::::::::::::::::::::;;;;;;;;;+++++
+++++;;;;;;;;;::::::::::::::::%##########S#######SSSS%%%?*;::::::::::::::::::::::::::::;;;;;;;;+++++
++;;;;;;;;;;:::::::::::::::::+S########SSS######SSS%%S%%??*::::::::::::::::::::::::::::;;;;;;;;+++++
+++;;;;;;;;;::::::::::::;;;+?SSSS######SS%###SSSSSSS%%%%%??+::::::::::::::::::::::::::::;;;;;;;+++++
++;;;;;;;;;;;;::::::::+*****S###SSSS#S???+%##S##SS%%%%%%%???;::::::::::::::::::::::::::::;;;;;;;++++
++++;;;;;;;;;;:::::::;**+;;:?@@@##S%*;:::,;S#####SS%%%??????*::::::::::::::::::::::::::::;;;;;;;;+++
+++;;;;;;;;;;;:::::::;;;:::::*SS?+;:,::::::?######SS%%%%????*:::::::::::::::::::::::::::;;;;;;;;;+++
+++;;;;;;;;;:::::::::::::::::::::,:::::::::+S######SS%%%???%?:::::::::::::::::::::::::::;;;;;;;+++++
;+;;;;;;;;;;:::::::::::::::::::::::::::::::;%#######S%%%??%%?:::::::::::::::::::::::::::;;;;;;;;;+++
;;+;;;;;;;;;::::::::::::::::::::::::::::::::?#SS#####S%%%%%%*:::::::::::::::::::::::::::;:;;;;;;;+++
+;+;;;;;;;;;;:::::::::::::::::::::::::::::::?SSS######S%%%S%*::::::::::::::::::::::::::::;;;;;;;++++
+;+;;;;;;;;:;:::::::::::::::::::::::::::::::?SSS#######SSSS%+:::::::::::::::::::::::::::;;;;;;;;;+++
++++;;;;;;;;::::::::::::::::::::::::::::::::?SSS########SSS%;:::::::::::::::::::::::::::;;;;;;;;;+++
+++;;;;;;;;;::::::::::::::::::::::::::::::::?SS#########SSS?::::::::::::::::::::::::::::;;;;;;;;;+++
+++;;;;;;;;;:::::::::::::::::::::::::::::::;%S###########?;;:::::::::::::::::::::::::::;;;;;;;;;;+++
++++;;;;;;;:::::::::::::::::::::::::::::::::*#########S#S;,:::::::::::::::::::::::::::::;;;;;;;;;;++
++;;;;;;;;;:::::::::::::::::::::::::::::::::%#######SSSS;,::::::::::::::::::::::::::::::;;;;;;;;++++
+++;;;;;;;;::::::::::::::::::::::::::::::::?########S?%;:::::::::::::::::::::::::::::::;;;;;;;;;;+++
+;+;;;;;;;;;:::::::::::::::::::::::::::::,;S########S%+::::::::::::::::::::::::::::::::;;;;;;;;;;+++
+++;;;;;;;;;::::::::::::::::::::::::::::::%#########%%:::::::::::::::::::::::::::::::;;;;;;;;;;;++++
++++;;;;;;;;;:;:::::::::::::::::::::::::::S#########S+:::::::::::::::::::::::::::::::;;;;;;;;;;;++++
++++++;;;;;;;;;:;;::::::::::::::::::::::::%####S###S+:::::::::::::::::::::::::::::;;;;;;;;;;;;;+++++
+++++++;;;;;;;;;:::::::::::::::::::::::::::%######S*,:::::::::::::::::::::::::::::::;;;;;;;;;;;+++++
+++++;+;;;;;;;;;:::::::::::::::::::::::::::;S####S%?;::::::::::::::::::::::::::::::::;;;;;;;;;++++++
+++++;;;;;;;;;;;:::::::::::::::::::::::::::,*####%%%%;::::::::::::::::::::::::::::::;;;;;;;;;;++++++
++++++++;;;;;;;::::::::::::::::::::::::::::::?####%?%?::::::::::::::::::::::::::::;;;;;;;;;;++++++++
+++++++;;;;;;;;::::::::::::::::::::::::::::::;S####%??::::::::::::::::::::::::;;;;;;;;;;;;;;;++++++*
++++++;;;;;;;;::::::::::::::::::::::::::::::::+%S%?+;;::::::::::::::::::::::::::;;;;;;;;;;;;+++++++*
++++++++;;;;;;;:::::::::::::::::::::::::::::::::***+;;::::::::::::::::::::::::::;;;;;;;;;;;;++++++**
*+++++++;;;;;;;;;::::::::::::::::::::::::::::::::**+;;;::::::::::::::::::::::::;;;;;;;;;;;++++++++**
++++++++++;;;;;;;;;;;;::;::::::::::::::::::::::::+**+;;:::::::::::::::::::::::;;;;;;;;;;;;++++++++**
*+++++++;+;;;;;;;;;;;;:::::::::::::::::::::::::::;**+;;;::::::::::::::::::::;;;;;;;;;;;;;;++++++++**
***++++++++++;;;;;;;;:::::::::::::::::::::::::::;++**+;;;::::::::::::::::::::;;;;;;;;;;;+++++++*****
%??????*******+++++++;;;;;;;;;::::::::::::::;;;;;;;;++;;;:::::::::::::::::::::;;;;;;;;;;++++++*???**