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