::::::::::::::::::::::::::;:;'''''':::::::::::::::::::::::::::::::;'++:,,..........................................................................................................................
:::;;;;;;:::::::::::::::::::;''++';:::::::::::::::::::::::;;;;;:::;'++:,,..........................................................................................................................
::::;;;;;;;;;;;;:::::::::::::;;'';;:::::::::::::::::::::::;;;;;;;;;'#+:,,..........................................................................................................................
::::::::::::;;;;;;;:::::::::;'''';::::::::::::::::::::::::::::::::;'#+:,,..........................................................................................................................
:::::::::::::::::::::::::::;'++++;::::::::::::::::::::::::::::::::;'#+:,,..........................................................................................................................
::::::::::::::,,::::::::::;'+++++;::::::::::::::::::::::::::::::::;'#':,,..........................................................................................................................
:::::::::::;;;::::::::::::;'+++++;::::::::::::::::;;;;::::::::::::;'#':,,..........................................................................................................................
::::::::::;'''';::::::,,,::'+++++;::::::::::::::::::::::::::::::::;'#':,,..........................................................................................................................
::::::::::;'+++';;:::,,,,::;+++++;::::::::::::::::::::::::::::::::;'#':,,,.........................................................................................................................
::::::::;:;'++++'';:,,,,,::;++++';:::::::::,,::::::::::::::::;;;;;;'#',,,,.........................................................................................................................
:::::::::::;'++';:,,,,,,,:;;'+++';:::::::,,,,:;:;::::;;;;:::;;;''';'#',,,,.........................................................................................................................
::::::::::::;++;:,,:::,:::;;''''';::::::::,::;;;;;;:::::::::;;;;;;;'#',,,,.........................................................................................................................
:::::::::::::'';,,:;;:::::;;;;';;;:::::::::;;::;;;;;;;;;::::;;;:::;+#',,,,.........................................................................................................................
:::::::::::::'':,,:;;;;;;;;;;;;;;;;;;;:::,;';::::::::;;;;;;;;;;;;;;+#',,,..........................................................................................................................
::::::::;;;:;'';::;'';;;;;;;;;;;;;;;;;;:::;'':::::::::;;;;;;;;;;;;'+#;,,,..........................................................................................................................
::::::::::::;'+;;;'''';;;;;;;;;;;;;;''';::;'':::::::::;;;;;;;;;;;;;+#;,,,..........................................................................................................................
:::::::::,:;'++++++++''';;;;;;;;;;;''+';::'+';:::::::::::;;;;;;;;;;+#;,,,..........................................................................................................................
::::::::::;'++++++#++'''';;;;;;;;''''+'';;'++;:;;;;;;;;;;;;;;'';;;'+#;,,,..........................................................................................................................
:::::::::;''+++++###+++'''''''''''''+++''''++';:;;;;;;;;;;;;'''';;'+#;,,,,.........................................................................................................................
::;;;::::;'+++++####+++++'''''''''+++++++++++';::;;;::::::::;;;;;;'##;,,,,,........................................................................................................................
:;;;;;:::;'+++++###++++++''''''''+++++++++++++';:;;;:::::::;;;;;;;'##:,,,,,,.......................................................................................................................
:;;';;;:::'++++###++++++++''''''++++++++++++++';;;;;;::::;;;;;;;;;'##:,,,,,,.......................................................................................................................
:;;;;;;:::;'+###+''++++++++'''''++++++++++++++';:;;;;;;;::::;;;;;;'##:,,,,,,.......................................................................................................................
:;;;;;;;::;;'++';:;'++++++++''++++++++++++++++';;;;;;;;;;;;;;;;;;;'##:,,,,,,.......................................................................................................................
:::;;;;;;;;;;;;;;:;+++++++++++++++++++''''+++';:::::::::;;;;;;;;;;'#+:,,,,,,.......................................................................................................................
;:::;;;;;;;;;;;;;;;'++++++++++++++++++';;;;;;::::::::::::::::::::;'#+:,,,,,,.......................................................................................................................
;;:;;;;;;;;;;;;;;;;'++++++++++++++++++';;;;::::;;;;;;;:::::::::::;'#+:,,,,,,.......................................................................................................................
;;;;;;;;;;;;;;;;;;;'++++++++++++++++++';;;;;;;;;;;;;;;;;::::::::;;'#+:,,,,,,.......................................................................................................................
;;;;;;;;;;;;;;;;;;;+++++++++++++++++++';;;;;;;;;;;;''';;::::::;;;;'#+:,,,,,,.......................................................................................................................
;;;;;;;;;;;;;;;;;;;'++++++++++++++++++';';;;;::;;;;'';;;;;;;;;;;;;+#+:,,,,,,.......................................................................................................................
;;;;;;;;;;;;;;;;;:;'+''''+++++++++++++';'';;;:;;;;;;;;;;;;;;;;;;;'+#+:,,,,,,.......................................................................................................................
;;;;;;;;;;';;;;;;;;'+''''+++++++++++++';';;;;;;;;;;;;;;;;;;;;;;;;'+#':,,,,,,..................................................................................,,,..................................
;;;;;;;;;;'''';;;;;''''''++++++++++++'';;;;;;;;;;;;;;;;;;;;;;;;;;'+#',,,,,,,...............................................................................,:;;';,.................................
;;;;;;;;;;;;;;;;;;;'''''''+++++++++++'';;;;;;;;:::::::;;;;'''''';'+#',,,,,,,..............................................................................:;'++#+;,................................
;;;;;;;;;;;;;;;;;;;''';'''+++++++++++'';;;;;;;;;;;;;;;;;''''''''''+#',,,,,,,.............................................................................,;+######;,...............................
::::;;;;''''''';;;;;;;;'''++++++##+++'';;;;;;;;;;;;;;;;;;;;;;;;;;'+#',,,,,,,.............................................................................:+#######+,...............................
;;;;;;;''''''''';;;;;;;'''++++++###++'';;;;;;;;;;;;;;''';;;;;;;;;'+#',,,,,,,,...........................................................................,'#########:...............................
;;;;;;;;'''''''';;;;;;;'''++++++##+++'';;;;;;'';;;;;;''';;;;;;;'''+#',,,,,,,,,,..,,,,,,,,,,.............................................................:+#########;...............................
;;;;;;;;;;;;;;;;;;;;;;;'''+++++###+++'';;;;;'''';;;;;;;;;;;;;;;''++#;,,,,,,,,,,,,,,,,,,,,,,,............................................................;##########;...............................
;;;;;;;;;;;;;;;;;;;;;;;'''+++++###+++'';;;;''''';;;;;;';;;;;;;'''+##;,,,,,,,,,,,,,,,,,,,,,,,............................................................'##########;,..............................
;;;;;;;;;;;;;;;''';;;;;'''+++++###+++'';;;;;;;;;;;;;;''';;;;;;;''+##;,,,,,,,,,,,,,,,,,,,,,,,............................................................:+#########;,..............................
;;;;;;;;;;;''''''';;;;;'''++++####+++'';;;;;;;;;;;;;;''''''';;;''+#+;,,,,,,,,,,,,,,,,,,,,,,,............................................................,'+++######',..............................
;;;;;;;;;;''''''''''++++++++++####+++'';;;;;;;;;;;;;;;''''''';;;'+#+;,,,,,,,,,,,,,,,,,,,,,,,,,,,,........................................................:+++++++++';:,............................
;;;;;;;;;''''''''+++######+++######++'';;;;;;;;;;;;;;;'''''''''''+#+;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..................................................,;+++++++++++;............................
:;:;;;;;;''++'''''++###############++'';;;;;;;;;;;;;;;'''''''''+++#+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..,,,..................................................,:'++++++++##',...........................
;;;;;;;;;''+++''''++###############++'';;;;;;;;;;;;;;;;'''''''''++#+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..,,,...................................................,'+++++++###+;,..........................
;;;;;;;;''''''''''++###############+++';;;;;;;;;;;;;;;;;;''''''''+#+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..,,,...................................................,;+++########+':,........................
;;;;;;;;''''''''''++###############+++';;;;;;;;;;;;;'''''''''''''+#+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..,,,,.................................................,;++############+;,.......................
''''''''''''''''''++################++'''''';''''''''''''''''''''+#+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.......................................................:+###############+':......................
''''''''''''''''''++################++''''''''''''''''''''''''''++#+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,................................................:'##################';,....................
''''''''''''''''''+#################++''''''''''''''''''''+''''+++#+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,...............................................,'+###################+:,...................
''''''''''''''''''+#################+++'''''''''''''''''''''''++++#+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,...............................................:+#++++++##############',...................
''''''''''''''''''+#################+++'''''''''''''''''''''++++++#+,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..............................................,'+++++++++#############+:...................
'''''''''''''''''++#################++++'++''''''''''''''+++++++++#',,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..............................................:++++''''++#############+:,..................
'''''''''++++++++++#################+++++++++''''''''''''+++++++++#',,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..............................................;+++'''''+++############+;,..................
'''''''''+++++++++#########++#######+++++++++++++++++++++++++++++##',,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,............................:;;:,,...........,'+#+++''''+++###########+;,..........,.,,,,,,
'''''''''+++++++++#########+++######+++++++++++++++++++++++++++++##',,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,....,......................;+++':,........,:;++##+++'''+++###########+;,.........,,,,,,,,,
';;'''''''++++++++#########++++#####++++++++++++++++++++++++++++###',,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,....,......................;++++'';:,.....:'++####+++++'+++##########+;,........,,,,,,,,,,
;;;;;;;''''''''''+########+++++#####+++++++++++++++++++++++++++++##',,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,....,......................:'+++'++++;:,..;+#########++++++###########;,..,,,,,,,,,,,,,,,,
;;;;;;;;;''''''''+########+++++#####++++++++++++++''''''''+++++++##',,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.,....................,:''''+####+';'+###########++++############',..,,,,,,,,,,,,,,,,
;;;;;;;;;''''''''+#######++'+++#####+++++'''''''''''''''''''+++++##;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.,.....................,:;''+####################################',.,,,,,,,,,,,,,,,,,
;;;;;;;;;''''''''++######++''++#####+++++'''''''''''''''''''''+++##;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,........................,'######################################',.,,,,,,,,,,,,,,,,,
;;;;;;;;;'''''''''+######++''++#####+++++'''''''''''''''''''''+++##;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.......................,:'#####################################':,,,,,,,,,,,,,,,,,,
;;;;;;;;;'''''''''+######++''++#####+++++'''''''''''''''''''''+++##;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,........................,:;+###################################+:,,,,,,,,,,,,,,,,,,
;;;;;;;;;'''''''''+######++''++####+++++++'''''''''''''''''''++++##;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.........................,:+##################################+:,,,,,,,,,,,,,,,,,,
;;;;;;;'''''''''''+#####+++''++####+++++++'''''''''''''''''''++++##;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..........................,,;+################################':,,,,,,,,,,,,,,,,,,
;;;;;;''''''''''''+#####+++'+++####+++++++''''''''''''''''''+++++##;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.............................,:;'''+++'+#####################+',,,,,,,,,,,,,,,,,,,
;;';'''''''''''''+######+++'+++####+++++++++''''''''''''''''+++++##;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,...................................,,,,.;+####################':,,,,,,,,,,,,,,,,,,,
''''''''''''''''+#######+++'+++####++++++++++++++++++++++++++++++##:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,........................................;#####################;,,,,,,,,,,,,,,,,,,,,
''''''''''''''''+#######+++'+++####++++++++++++++++++++++++++++++#+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.......................................,'#####################;,,,,,,,,,,,,,,,,,,,,
''''''''''''''''+#######+++++++#####++++++++++++++++++++++++++++##+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.......................................,'#####################;,,,,,,,,,,,,,,,,,,,,
''''''''''''+++++#######+++++++#####++++++++++++++++++++++++++++##+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.......................................,'#####################;,,,,,,,,,,,,,,,,,,,,
+++++++++++++++++#######+++++++######++++++++++++++++++++++++++###+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.......................................,+#####################',,,,,,,,,,,,,,,,,,,,
+++++++++++++++++#######+++++++#######+++++++++++++++++++++++#####+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.......................................,+#####################',,,,,,,,,,,,,,,,,,,,
+++++++++++++++++#######+++++++########++++++++++++++++++#########+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,........................................,+#####################',,,,,,,,,,,,,,,,,,,,
'''''''''''++++++######+++++'+++#####++++++++++++++++++++++++++###+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,........................................,+#####################',,,,,,,,,,,,,,,,,,,,
::::::::::::;;;;'#####+';;;;;;'+####+'';;;;;;;;;;;;;;;;'''''''''+#+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,........................................:+#####################',,,,,,,,,,,,,,,,,,,,
:::::::::::::::;;'+###+';;;;;;'+##++'';;;;;;;;;;;;;;;;;;;;;;;;;'+#+:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.......................................,;+#####################',,,,,,,,,,,,,,,,,,,,
::::::::::::::::;'+###';;;;;;;'+##++';;;;;;;;;;;;;;;;;;;;;;;;;;;+#':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,......................................:'######################',,,,,,,,,,,,,,,,,,,,
::::::::::::::::;'###+';;;;;;''+##++';;;;;;;;;;;;;;;;;;;;;;;;;;;+#':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,........................,,,..........,;+######################',,,,,,,,,,,,,,,,,,,,
::::::::::::::;'+###+';'''''++++##+++''''';;;;;;;;;;;;;;;;;;;;;'+#':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,........................,,,,,,,......,;+######################':,,,,,,,,,,,,,,,,,,,
:::::::::::::'+###+''::'+'++++++###+++''''''';;;;;;;;;;;;;;;;;;'+#':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,........................,,,,,,,......,'#######################':,,,,,,,,,,,,,,,,,,,
:;';;;;:::::;'####+';::;''+###++++#++'';;;;';;;;;;;;;;;;;'''''''+#':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,......................,,,,,,,,.....,:+#######################':,,,,,,,,,,,,,,,,,,,
;;;;;:::::::;;'####+'';;;''+++++++'''';;;;;;;;;;;;;'''''''''''''+#':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,......................,,,,,,,,.....,;+#####################+';,,,,,,,,,,,,,,,,,,,,
;;;;::::::::;;;+####++';;;'''''''++''''''';;;;;;;;''''''''''''''+#':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,......................,,,,,,,,.....,;+####################+;:,,,,,,,,,,,,,,,,,,,,,
;;;;::::::::;;;+######+;;;;;;;;;;''+';;;;;;;;;;;;;''''''''''''''+#':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,...,,,,,,,,,,.........,,,,,,,.....,'+####################+:,,,,,,,,,,,,,,,,,,,,,,
;;;;::::;;:;;;;+#######+';;;;;::;;;++''';;;;;;;;;;;'''''''''''''##':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,...,,,,,,,,,,.........,,,,,,,.....:'#####################+:,,,,,,,,,,,,,,,,,,,,,,
''';;;;;;;;;;;'+########++'';;;;;;;''''';::::::::;;'''''''''''''##':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,...,,,,,,,,,,.........,,,,,,,.....:'#####################+:,,,,,,,,,,,,,,,,,,,,,,
:::::::::::;;''+###########+'';;;;;;:::::::::::::::;;;;;;'''''''##;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,...,,,,,,,,,,,,,,,,,,,,,,,,,,..,.,:+#####################',,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,::;'+#########++''';;;;;;:::::::::::::::::;;;;;;;''''##;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..,,,,,,,,,,,,,,,,,,,,,,,,,,..,.,;+####################+:,,,,,,,,,,,,,,,,,,,,,,,
::::::::::,,:;''''''+++'''';;;;;;;;;:::::::::::::::::::;;;;;;'''##;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..,,,,,,,,,,,,,,,,,,,,,,,,,,,.,.,;#####################':,,,,,,,,,,,,,,,,,,,,,,,
::;;;::::::::::;;;;;;;;;;;;::::::;;;:::::::::::::::::;:::::::;;'+#;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.,.,'#####################',,,,,,,,,,,,,,,,,,,,,,,,
::;;;::::::::;;;;;'''''';;;;;;;;;::::::::::::::::::::;;;;;;;;''+##;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:+#####################',,,,,,,,,,,,,,,,,,,,,,,,
::;;;::::;'''''''+++++++++++++++#+;;;;;;;;;;::::::::;+##########@#:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.,;+#####################',,,,,,,,,,,,,,::,,,,,,,,
::;;:::::;+#####+################+';;;;;;;;;;;;;::::;+++++++++++';:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.,;+#########++##########;,,,,,,,,,,,,,,::,,,,,,,,
::::::::,;+##+'';;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;:;;''''''';;;;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..,,,,,,,,,,.,'+#########;:'########+;,,,,,,,,,,,,,,::,,,,,,,,
:,:::,,,,;+++;:,,,,,,,,,,,,,,,,,,,:::;;;;;;;;;;;;;;::;;;;;;;;;::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,....,,,,,,,,,.,'#########+,,;+#######+:,,,,,,,,,,,,,,::,,,,,,,,
::::::,,,;'++';;;;;::::::::::::::::::;;;;;;;;;;;::::::::::::::::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,...,,,,,,,,,,.,+#########;..:'#######':,,,,,,,,,,,,,,::,,,,,,,,
;;;;;:::::'++'';;'''''''''''''';;;;;''''''';;;;;;;;;;::;;;;::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.:+########+:,.,'#######':,,,,,,,,,,,,,,::,,,,,,,,
++++'''';;;'+''''''''''''''''''''++++++##+++++++++++++++++++++'';:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:+########':,..;+######':,,,,,,,,,,,,,,::,,,,,,,,
+++++++++'''+''''''''''''''''''''+###########+++++++++#########++;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::,,,,,,,;+#######+;,,,.;+######':,,,,,,,,,,,,,,::,,,,,,,,
+++++'++++''++'''''''''''''''''''+#+#######++++++++++++########+';,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::,,;########+:,,,.;+######':,,,,,,,,,,,,,,::,,,,,,,,
+++++''+++'''++'''''''''''''+++''##++######++++++++++++######+++':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::;;;;;:::,,;########',,,,.;+######+:,,,,,,,,,,,,,,::,,,,,,,,
+++++''+++''''';;;''''''';''''+''+#+++++++++++++++++++++######++':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:;;;;;;';;;;:::+########;,.,,,;+######+:,,,,,,,,,,,,,,:::::::,,,
+++++''+++'''';;;;;;;;;;;;;;;;;;;+++++++++++++++++++++++++++++++';,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:;;'''''''''';:;+########;,,,,,;+######+:,,,,,,,,,,,,,,:::::::,,,
+++++'++++'';;;::;;;;;;;;;;;;::::++++++++++++++++++++++++++++++++'::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:;;'''''''''''';;+########;,,,,,;+######+:,,,,,,,,,,,,,,:::::::,,,
++++''++++'';;;;;;;;;;;;;;;;;::;'++++++++++++++++++'''+++++++++++++''';:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:;'''++++++++++'';+########;,,,,,:'######+:,,,,,,,,,,,,,,:::::::,,,
++++'''++'';;;;;;;;;;;;;;;;;;;;'+++++++++++++++++++'''++++#######++++++':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::;''+++++++++++++''+########;,,,,,,;######+:,,,,,,,,,,,,,,:::::::,,,
+++'';''''';;;;;;;;;;;;;;;;;;;'+++++++++++++++++++'''''++######+++++++++:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:;;''+++++++++++++++++########',,,,,,:+#####+:,,,,,,,,,,,,,,:::,,,,,,,
'';';;;'''';;;;;;;;;;;;;;;;;;'++++++++++++++++++++'''''+++#######++++++':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;''+++++++++++++++++++########',,,,,,:+#####':,,,,,,,,,,,,,,,,,,,,,,,,
';;;';;''';;;;;;;;;;;;;;;;;;''+++++++++++++++++++++''''++++######++++++':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:;'+++++++++++++++++++#########',,,,,,:+#####':,,,,,,,,,,,,,,,,,,,,,,,,
;';;';;;';;;;;;;;;;;;;;;;;;''++++++++++++++++++++++++'''+++++++++++++++':,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;'+++++++++++++++++############',,,,,,:+#####;,,,,,,,,,,,,,,,,,,,,,,,,,
;';:;;;;';;;;;;;;'';;';;;:;'++++++++++++++++++++++++++''''+++++++++++++';:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:;'+++++++++++++++##############',,,,,.:+####+;,,,,,,,,,,,,,,,,,,,,,,,,,
;';:;;;;;;;;;;;;;'';;'''';'++++++++++++++++++++++++++++++'++++++++++++++';:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..,:;+++++++++++++++##@@###########',,,,,,:+####+;,,,,,,,,,,,,,,,,,,,,,,,,,
;;::;;;:;;;;;;;;;''''+'''''+++++++++++++++++++++++++++++++++++++++++++++'';:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,..,:'++++++++++++++###@@@##########',,,,,,;#####+;,,,,,,,,,,,,,,,,,,,,,,,,,
:;;::;;:::::::::;''''+++++++++++++++++++++++++++++++++++++++++++++++++++++':,,,,,,,,,,,,,,:,,,::,,::::::::::::,,,,,,,,,,..,:'++++++++++++++##@@@@##########':,,,,,;#####+:,,,,,,,,,,,,,,,:::,,,,,,,
:;:,:;;:::::::::;'''++++++++++++++++++#+''+++++++++''+++++++++++++++++++++';::;;;;;;;;;;;;'';''''''''''''''''''';;:::::,,,,,'++++####++##+###@@@@@#########+:,,,,,'#####':,,,,,,,,,,,,,,,:::,,,,,,,
,::,,:::,::::,:::;'++++++++++++++++++++;,:++++++++;,;'+++++++++++++++++'++'';''''''''''''''''''''';;;;;;::::;;;;;;;;;;;;;:,:'++++###########@@@@@@#########+:,,,,,'#####':,,,,,,,,,,,,,,,::::,,,,,,
,,,,,,,,,,,::,::::'+++++++++++##++++++',`,'+++++';:.,'''+++'++++++++++''''''';;;;;;;;;;;;;;;;:::::::::::::::::::::::::;;;;;;'++++###########@@@@@##########+:,,,,,'#####',,,,,,,,,,,,,,,,::::,,,,,,
,,,,,,,,,,:::::::;'+++#+';;;;;;''''''+;..,;'++++:,:.,;:::::;'++++++++''''''';;::::::::::::::::::::::::::::::::::::::::::::::'+++############@@@@###########+:,,,,,+#####;,,,,,,,,,,,,,,,,::::,,,,,,
,,,,,,,,::::::::;'++++++;:,,,,,,,,::::,,,,,:;;;':,:..:,....,;+++++++'''''''';::::::::::::::::::::::::::::::::::::::::,,:::::;++#############@@@############+:,,,,:+#####;,,,,,,,,,,,,,,,,:::,,,,,,,
,,,,,:::::::::;;'+++++++':,,,,,,,,,,,,,,,,,,:,:':,,,,,,,,,.,;+++++++'''''''';;::::::::::::::::::::::::::::::::::::::::::::::;'+###########################@+:,,,,:+#####;,,,,,,,,,,,,,,,,,,,,,,,,,,
,,::::::::::::;'++###++++':,,,,,,,,,,,,,,,,,,,:;:,,,,,,,,,.:'++++++++'''''''';:::::::::::::::::::::::::::::::::::::::::::::::'++################++++#######+:,,,:'######;,,,,,,,,,,,,,,,,,,,,,,,,,,
::::::::::::::;'++#####+++;:,,,,,,,,,,,,,,,,,,,:,,,,,,,,,,,;+#++++++++''''''';;::::::::::::::::::::::::::::::::::::::::::::::;'++##########+++++++++######@#':::;+######;,,,,,,,,,,,,,,:::,,,,,,,,,
:::::::::::::;'+++#######++:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;+###+++++++++''''':,..,,,::::::::::::::::::::::::::::::::::::,:::::;''+++++##+++++''''';'########+;;;'#######;,,,,,,,,,,,::,,,:::,,,,,,,
:::::::::::::;'++#########+':,,,,,,,,,,,,,,,,,,,,,,,,,,,,:+####++++++++++'';:.``````..,,,,,::::::::::::::::::::::::,,,,,,,::::;;'''++++++++''';;;;'+########+;:;'#######':::::::::::,,,,:::,,,,,,,,
::::::::::::::;'+##########+;,,,,,,,,,,,,,,,,,,,,,,,,,,.,'######+++++++++'':.```````````....,,::::::::::::::::::::,,,,,,,,,::::;;;''''''''''''''++##########+;::'#######+;;;;'''';;;::::::,,,,,,,,,
::::::::::::;;;'+#####+#####',,,,,,,,,,,,,,,,,,,,,,,,,.,;+#######++++++++';.```````````````````...,,,,::::::::::::,,,,,,,,::::::;;'''''';';''+####@#########+:::;######+';;;;;;;''''''';;;;:::,,,,,
::::::::::::;;;;'+##########+;,,,,,,,,,,,,,,,,,,,,,,,,,:'#########+++++++',``````````````````````````...,,,:::::::,,,,,,,::::::::;;;;;;;;;;;''++############+:::;+#####+;:::::;;;;;;;;;''''';;;;;::
::::::::::::::::'+###########':,,,,,,,,,,,,,,,,,,,,,,,,'############++++';.```````````````````````````````..,,,,,,,,,,,,,:::::::::::;;;;;;;;;;;'++++';;;'+++;:::;+####+'::::::::::::::;;;;;;;;;''';
::::::::::::::,,:'###########+':,,,,,,,,,,,,,,,,,,,,,,:+############++++',```````````````````````````````````````..,,,::::::::::::;;;;;;;;;;;;'''+'';;;;;;;;::::'#####+;::::::::::::::::::::::;;;;;
::::::::::::,,,,:'############+;,,,,,,,,,,,,,,,,,,,,,,'+############++++;.```````````````````````````````````````````...,,,,,,:::::;;;;;;;;;;'+++++++'''+''';:::'#####+;:::::::::::::::::::::::::::
:::::::::::::::::'#############':,,,,,,,,,,,,,,,,,,,,,'############++++':.`````````````````````````````````````````````````...,,::::;;;;;;;;;;;'''+++++++++';:::'#+##+';:::::::::::::::::::::::::::
::::::::::::::::''#############+;,,,,,,,,,,,,,,,,,,,,,;+###########++++;.```````````````````````````````````````````````````````...,:::;;;:::::::;''+'''+++';:::''''++';:::::::::::::::::::::::::::
::::::::::::::::;;'''+++++++++++;:,,,,,,,,,,,,,,,,,,..:+###########+++':.``````````.,,:::::,,.````````````````````````````````````````..,,,,,,,:::;''''''''';:::''''''';:::::::::::::::::::::::::::
;;;::::::::::::::::::::::::::::::,,,,,,,,,,,,,,,,,,,,,:'###########+++',.```````````.,,,:::::,.`````````````````````````````````````   ``````...,,:;'''''''';:::''''''';:::::::::::::::::::::::::::
;;;:::::::::::::::,,,,,,,,,.......,,,,,,,,,,,,,,,,,,::;'+##########+++;,....```````````   ```````````````````````````````````````````````````````..,:;;'''';;:::;'''''';:::::::::::::::::::::::::::
;;;;;::::::::,,,,,,,,,,,..........,,,,,,,,,,,,,,,,,,:::;''+++++++++++';,.....````````````````````````````````````````````````````````````````````````..,,::::,,:;'''''';:::::::::::::::::::::::::::
::::::::,,,,,,,,,,,,,,...........,,,,,,,,,,,,,,,,,,,,,,,:::::::::::::,,.....````````````````````````````````````````````````````````````````````````````````...,:;;'''';:::::::::::::::::::::::::::
,,,,,,,,,,,,...................,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,............``````````````````````````````````````````````````````````````````````````````````````.,,:::::::::::::::::::::::::::::::
,,,...........................,,,,,,,,,,,,,,,,,,,,,,..................`````````````````````````````````````````````````````````````````````````````````````````````````....,,,,::::::::::::::::::::
.................................,,,,,,,,,,,,,,,,............````````````````````````````````````````````````````````````````````````````````````````````````````````````````...,,,,:::::::::::::::
.......................................................````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````...,,,::::::::::
....................................................```````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````..,:::::::::
..........``````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````.....,:::::::::
.......`````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````.............,:::::::::
```````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````..................................,:::::::::
```````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````..................................................,:::::::::
`````````````````````````````````````````````````````````````````````````````````````````````````````````````````````....................................................................,:::::::::
```````````````````````````````````````````````````````````````````````````````````````````````````````..................................................................................,:::::::::
`````````````````````````````````````````````````````````````````````````````````````````................,,,,,,..........................................................................,:::::::::