*********+++++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++*******
*******++++++;++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++******
*****+++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;:;::;;;;::;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++****
****+++++++;;;;;;;;;;;;;;;;;;;;;;;:::::::;;;;;:;;:::;::;;::;:;::;;;;;;;;;:;;;;;;;;;;;;;;++++++++****
***++++++;;;;;;;;;;;;;;;;;;;;::::::::::;?+::::::;:::;;::::::::::::;:;;::;::::;;;;;;;;;;;;;+++++++***
***+++++++;;;;;;;;;;;;;;;;;;;::::::::::?#*:::::::::::::;::;;::::::::::;:::::;;;:;;;;;;;;;;;++++++++*
**+++++++;;;;;;;;;;;;;;;;;::::::::::::?##%::::::::::::::::::::::::::::::::::::::;:;:;;;;;;;;+;+++++*
**++++++;;;;;;;;;;;;;;;;:::::::::::::?####?;;:::::::::::::::::::::::::::::::::::::;:;;;;;;;;;;+++++*
+++++;;;;;;;;;;;;;;;::::::::::::::::?#SS###%*;:::::::::::::::::::::::::::::::::::::;::;;;;;;;+++++++
+++++++;;;;;;;;;;;;::::::::::::::::?##S#####S%*+::::::::::::::::::::::::::::::::::::;;;;;;;;;+++++++
++++++;;;;;;;;;;;;;;::::::::::::::*S##########S?;:::::::::::::::::::::::::::::::::::::;;;;;;;;;+++++
+++++++;;;;;;;;;;;;::::::::::::::;+*?S#########S:::::::::::::::::::::::::::::::::::::::;;;;;;;;;;+++
+++++;;;;;;;;;;;:::::::::::::::::*???%SS#######?:::::::::::::::::::::::::::::::::::::::::;;;;;;;;+++
++++;;;;;;;;;;::::::::::::::::::;%S???%%?%####S::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;++
++++;;;;;;;;::::::::::::::::::::;?*****???S##S;,::::::::::::::::::::::::::::::::::::::::;;:;;;;;;;++
++++;;;;;;;;;::::::::::::::::::::*****?**?%%*;,::::::::::::::::::::::::::::::::::::::::::::;;;;;;+++
++;;;;;;;;;;;::::::::::::::::::::;*????????*::,::::::::::::::::::::::::::::::::::::::::::::::;;;;;;+
+++;;;;;;;;;;:;::::::::::::::::::::;+????????*+;:,:::::::::::::::::::::::::::::::::::::::::;:;;;;;;+
++;;;;;;;;;;::::::::::::::::::::::,,,:*%?%%????**+::,::,,,,,,,,,,,,,,,,::::::::,::::::::::;;;;;;;;;+
++;;;;;;;;;;::::::::::::::::::::::::::*%S%????????*+:,,:,,,,,,,,,,:,,,:::::::::::::::::::;;;;;;;;;++
+;;;;;;;;;;;:::::::::::::::::::::::::*%SSSSS%%%%????*+:,,:,,,,,,,,::,:,,,,,,::,,,,:::::::::;;;;;;;++
+++;;;;;;;;::::::,:::::::::::::::::::;%SSSSSSSS%%%????*;:,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::::::;;;;;;;
+++++;;;;;;;::::::::::;;+;:::::::::::,?SSSSSSSSSS%%%????+:,,,:,,,:,,,,,,,,,,,,,,,,,,,:::::::;;;;;;;;
+++;;;;;;;;;;;:::::::;;;;;;;;:,,::::,,?SSSS#####SSSSS%%??*;,,,,,,,,,,,,,,,,,:::::,:::::::::;;;;;;;;;
++;;;;;;;;::::::::::::;;;;;;++;;:,,,,;S########SSSSSSSS%%??+:,,,,,,,,,,,,,,,,,:,,,,,:::::::::;;;;;;;
+;;;;;;;;:::::::::::::::::;;***%%**+;?S%S##############SS%??+:,,,,,,,,,:,,,:,,:,,,,,:::::::::;;;;;;;
;;;;;;;::::::::::::,::::,,:,:%SS#SS#S%%%SSS##########SS%%%%??+,,,,,,,,,,,,,,,,,,,,,,:,,::::::;;;;;;;
;;;;;;;;::::::::::::,::,:,::,*####S#SSS######SS#####SSSSS%%???:,,,,,,,,,,,,,,,,,,,:::::::::::;;;;;;;
;+;;;;;;:::::::::::::,,:::,,,,:;+*SS%S########SS##S##SSSS%%%??+,,,,:,,:,,:,,,,,,,::::::::::;;;;;;;;;
;+;;;;;;;;::::::::::::::,,,,,,,::;SSS######%###SSSS####S%%%%%??:,,,,,,,,,,,,,,,:::::::::::::::;;;;;;
;;;;;;;;;;:::::::::::::,:::,,:;++?%S######*,*###########SS%%%??+,,,,,,,,,,:::::::::::::::::;::;;;;;;
;;;;;;;;;;:::::::::::::::::::+****++?###S+,,,*############S%%%?*,,,,,,,,:::,:::::,,:::::::::::;;;;;;
;;;;;;;;;::::::::::::,:,,,,,+?**+:,,:+?S*,,,,:?#############S%%*:,,,,,,,,,,,,,,,,,,,::::::::::;;;;;;
;;;;;;;;;::::::::::::,,,,:,,:+++:,,:,,,:,,,,:,;%#############S%?:,,,,,,,,,,,,,,,,:,:::::::::;;;;;;;;
;;;;;;;;;:::::::::::::,,,:,:,,:,,,,,,,,,,,,,,,:*S##S##########S?:,:,,,,,,,,,:,,,,,,,:::::::;;;;;;;;;
;;;;;;;;;;::::::::::,,::,,,::::,,,,,,,,,,,:,,,,;%#SS##########S*,,,,,,,,,:,,,,::::::::::;;;;;;;;;;;;
++;;;;;;;;;;;::::::::::,,,,,::::::,,,:::::::,,,:?#SSSS#########%;,,,,:,:,::::::::::::::;;;;;;;;;;;;;
+;;;;;;;;;;;;:::::::::::::::::::::::::::::,,::,,+S#SS###########?;,,,,,,::::::::::::::::::;;;;;;;;;;
;;;;;;;;;;;;::::::::::::::::::::,:,,,::::::::,,,;%SS#########*+;:,,,,,,,,,,,,,,,,,,:::::::;;;;;;;;;;
+;;;;;;;;;;;:::::::::::::,,,,::,,,,,,,,,,,,::,,,;%S########S%:,,,,,,,,,,,,,,,,,,,,,:::::::;;;;;;;;;;
+++;;;;;;;;;:::::::::,,,,:,,::::,:,,::,,,,,,,::,;S########SS;,,,,,,:,,,,,,,,:::::,::::::::;;;;;;;;;+
++++;;;;;;;;;::::::::,::::,,::,:,,,,:,,,,,,::,,:%#########S%:,,,,,::,,,,,,,,,,,:::,:::::::;;;;;;;;++
++++;;;;;;;;;;:::::::::::::,,::::::,:::,,:,:,,,+##########S?:,,,,,::::::::,,:,:::::::::::;;;;;;;;;++
++++++;;;;;;;;;:::::::::::::::::::::::::,::::::?#########S%?:,,,,,::,,:::,,::,:::::::;;;;;;;;;++++++
+++++++++;;;;;;;::::::::::::::::,::::::::::::::S##########%*:,,,,:,,,,,:,,,::,::::::::;;;;;;;;;+++++
++++++++;;;;;;:::::::::::::::::::::,:::::::,,,:?##########%:,,,,,:::::::,,,::,:::::::;;;;;;;;;;+++++
+++++++;;;;;;;:::::::::::::,::::::::::::,,:,,:,:*########S:,:::::::,::,::::::,::::::::;;;;;;;;;+++++
+++++++;;;;;;;;;::::::::::,:::,:,:::::::::,,,,:,,+######S?:,::::::::::,,,::,,::::::::::;;;;;;;++++++
++++++;;;;;;;;;;::::::::::,,,::::::,::::::::::::,,*#####S??;,:::::::::::::::::::::::::;;;;;;++++++++
++++++++;;;;;;;;:::::::::::,::,::::::::::::::::::,:S#####S?*,,:,:::::::::::::::::::;;;;;;;;;;+++++++
****++++++;;;;;;;;;;:::::::::::::::::::::::,::::::,;######S?::::,:::::,:::::::::::::::;;;;;;;;++++++
*+++++++;;;;;;;;;;;;;;;:::::::::::::::::::,,:,,,::::+S###S%+:::::::::::::::::::::::::;;;;;;;;++++++*
*++++++++;;;;;;;;;::;;:::::::::::::::::,:::::,,,,:::::;??**+;:::::::;;::::::::::::;;;;;;;;++++++++**
**+++++++;;;;;;;;;;;;;;;;::::::::,,:::::::::::::::::::,;***++:::::::::::::::::::;;;;;;;;;;+;++++++++
****++++++;;;;;;;;;;::::::::::::::::::,:,:::::::::::::::+***+;::::::::::::::::;;;;;:;;;;;;++++++++++