bogi########################################MM########MM#MM#########################################
#MMM###########M########MM##MM#####M##MMMM@@HH@@M######M#######################M@#M#########MMMM#M@M
#MH@@#MMMMMMMMMMMMMMMMMMMMMM@@MMM#M#M@@@HXXMMHXHMMMM##############M#######MM####H$MMMMMM@MMMMM#M@@@#
#M@HHMM@@@@@@@@@@@@@@@@@@MMM@@@@MM@HHHX%$@######MMM#################MM######MM###XX@@@@@@H@@@MM@XHM#
##MHH@@@@@@@@@@@@@@@@@@MMMMM@HH@@M@H$/+H######MMMMM#########MMM#####MMM######MM@##$%@@@@@H@@@@@HXHM#
##M@@HH@HHHHHHHHHHHHHHH@@@@@HHXH@HX%;$M########M#M###########MM@MM####MMMM###MMMM#M/+X@HHHHHHXH@H@M#
#M#M@HHHXXX$XXXXXXXXXXXHXHHHXXXXX$+/@##M#MM#M###MMM##M########M@MMMM###M@MMMMM##M##X;+XXHHXX$$XH@@##
#M#@MHHXXXXXXXXXXXXXXXXXXXHHXXXXH$+####M@@MMM##M@MM##########MMMMMM@M#MMMM@@@M######@;%$XHXXX$X@H@##
#MM@@HXXXXXXXXXXXXXXXXXXXXHHXXHHX%+##MMH@@#@HM#M########M########MMMM###MMMMM@MM#####$;+XXHHX$XH@M##
##M@@HXXXXXXXXXXXXXXHHHXXXXHXXHHX/%#MM@##MMM#####@HHHH@@@M#####MM##M##MMM##MMM#MM##M##+;%H@@HXX@@M##
##M@@H$XXXXHHXXXXXHHHHHX$$XHXX@H$/##M@#@/M#M##MHX$%$$$$$H@MMM##MXXXH@M#MM#MMM#MM@M##M##:/X@@H$XH@M##
###@@H$XXXXHHXXXXXXXHHXX$$XXXXHX%:##M##=-M###HXXXXXXHXXXXX@#######@XXXH@M#MMM###@M##M##@;%H@HH$H@M##
###@@H$XXXXXXXXXXXXXXXXXXXXHXXH$+$##M#M::###@HXXXXXXXXXXX$X@#MMM####@HX$X@##M###M####M##H/$HX$H@@@##
#MM@@HXXXXXXXXXXXXXXXXXXXXXHX$X$;#####$/;##@@HXXXXXXXXXXHXXH@##@M@####MX$%XM##M###MMMMM##++$XXHH@@##
#MM@@HXXXXXXXXXXXXXXXXXXXXHHX$X%:#####;+;##HHHHHXXXXXXHXHXX$XHM###@@####@$+XM#####MMM@@###;+$$H@@@##
#MM@@HXXXXXXXXXXXXXXXXXXXXHHX$$%X####@/%/##HHHHHXHXXXXHXXXXXXX$$H@M##MM###H+%H#####MMM@M##H;%$H@@@##
#MM@@HXXXXXXXXXXXXXXXXXXXHHX$$$+@####;%$/@MHHHHHXXXXXXXXXXXXX$HH$$X@M###M##M$+@M#M###MM####:/$H@@M##
#MM@@HXXXXXXXXXXXXXXXXXXXHHX$$$+H#M##;%$/MMHHHHXXXXXXXX$XX$XXXHXX$$$XXH@#####M+$HM#M#M#MM##M;+X@@M##
#MM@@HXXXXXXXXXXXXXXXXXXXXHH$$$+$####:%$$#MHXXXXXXXX$$$$$$$$XXX$$XXXXXXXX$XM###@%@M###MM@M##X;X@@M##
#MM@@HXXXXXXXXXXXXXXXXXXXXHH$$X%+####;%%X#@XXXXXXXX$$$$%%$$$$$X$XHXXXXXXXX%$@#####M@@#M@M@M##;%@@M##
#MM@@HXXXXXXXXXXXXXXXXXXXXHH$$X%;####+%%@MHX$$XXXX$$$$%%%%%$$$X$XXXXXHXXXHX%$H######M#MMM@H@#$/XHM##
#MM@@HXXXXXXXXXXXXXXXXXXXXHHX$X$;####$++#HX$$$XHX$$%%%%%%%%%%$$$XXXXXHHXHHHH%%$@#####MMM##@H##%%HM##
#MM@@HXXXXXXXXXXXXXXXXXXXXHHX$X$;####X/%#X$$%$XX$%%%%%+++++%%%$$$$XXXXXXXXXXXX$%XX#M###@#M#M@#@/X@##
#MM@@HXXXXXXXXXXXXXXXXXXXXHHX$H$/####H;$M$$$%$XX$%%%%%+++++++%%$%$$$XXXX$HHXXXX$%+@#####@##M@M#%$@##
#MM@@HXXXXXXXXXXXXXXXXXXXXHHX$HX%@#M#X-M@$X$%$$$%$%%%+++/////;;//+%%%%$$$XHHXXXXX+%##+%HX+M#M##H%HM#
#MM@@HXXXXXXXXXXXXXXXXXXXXHHXXHX%%#M#X,MHXX$%%$%$+%%+++/;/;:;+XHH$/;+%$$$XX@XX$H$/$#X/+/;=/##M##$HM#
#MM@@HXXXXXXXXXXXXXXXXXXXXXHXXHH$/#M#$,@$$$$$$$%%%%+++/;/::$########X%%$$XHHHHH$$%M##$+%%;-$####@X@#
#MM@@HXXXXXXXXXXXXXXXXXXXXXHX$HH%/###$;@%$$%%%%%%%%%+//:=:$###H$XM####H$$$HHXHX+$#MM#X++%+=/####MX@#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXX$XH%/###H%X+%%%%$%$%%++/;:=:X###%-,--=;/+$X$XXXXX%H#M+H##H$/%:%#@M##$M#
#MM@@HXXXXXXXXXXXXXXXXXXXXHX$XXX$;####X%%++++%%$%++/;==$###+=-=:=:;/+%%%$XXX$$H#M%$X##M%++:%#@M##$@#
#MM@@HXXXXXXXXXXXXXXXXXXXXHX$XXX$/$###M$+++%++%%%++;X####X:--:::::;+%+%$XX$H%H#H$X$%##H++;;$#MM##%@#
#MM@@HXXXXXXXXXXXXXXXXXXXXHX$XXX$+$#M###H%;;;/++%%//##H;--,:;:;:::;/+%$$$$$%@#@$XX$%M#X;+;:@#@M##%@#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXX$%%##MXM###H$+/+%+;:/;---=::::::==:;%%+%$+%##H$$XX$$H+$+/:;#M#M##%@#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXX$/###+/%M####//+;;:==:::::;:::==-=:;+%%+%@#X$XXHXX$$/XX/:X#M#M##+@#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXX$/M##@/;::/$$//+/;;::;;/;:===,,..,-;;/;;##%$$XXHXXX$X@H$/##M####%@#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXHX;@##M%@#$/:::;//;:;::;//;=-,-+@###@/=;##%%XXHHHH$XXHH@%%#######%@#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXX/X###$#: #@X/://;::===-:/H#######$=,=##++$$XHHHX$$HX/X/%###M###$H#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXHX$+/###:M, #@#M/%%+;:::=--H##MX+/-,,,-#H;+X$XXHHXXX$XH-+;$#######$H#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXHHHX$%/###;#/ @M##H$HX/;;::-,-/+=--==-,=#M-;$$%HX$XXX$$X#;::X##M####XH#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXHHXX$%/@##+$#,+H##X%HH+/;=,--;;-=:/;:,/#$-:/%$XX$X$$X$$%##HH##M#####XH#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXHHX$$+/##H%H@HHXX%%HH+;:=$H##@X:-==-+#%-:;/%$$%XX$$X$$$@#####MM####XH#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXHH$XX%;#HM$//;%+X$$HH+:=M#######X,-X#;-:;//++$$$$X$X$$$H#####MM####XH#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXH$;#MM%%$+/+$$$HH/;%#########H##;-::;;//++%$XX$$$$%H###M#MM####HH#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXH$;$######@X/%XXX+:@#MMM@MM@@M#X=::/::;/++%$XX$$$X%H#####MM#M##@H#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXHHX;$#@M#####H/+XH%;@#M@H$XX$%%#;,:;;;;;/++$$XXXXXX$H###MMMMMM##@H#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXHXH$+##M###M###X+@H+/X#MH$XH$/;;@@=::;;;;/+%$$XXXXXXXH###MMMMM###@H#
#MM@@HXXXXXXXXXXXXXXXXXXXHXXXXXXXXX%+#####M@@X$MHMM#####X%XX+/;:X#:=::;///+%$$XXXXXHHHM####MMM###@H#
#MM@@HXXXXXXXXXXXXXXXXXXXHXXXXXXXXX%:M##M#MXH$:@#+,:/$@##%%%;/;:%#==::///++%$$XXXXXHHHM#####M###X$H#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXX$+/##M#MXH%-/#/=///:%#M%;=:::@X=:;;////+%$$$XXXXHH@####M@@##X%@M#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXX$$+X##@H$X+-,#:=+++/-;##$==:$#:=:;/////+%$$$XXXXHXM###MMM##@/XM##
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXH$/M##@//;--#==;//+:-=+M###H;=:;;///++%%$$$XXXHHH#####MM##;%HM##
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX$%/%##M$+/M#/+:;;:;:=====:-:::;;///++%%$$XXXXHH@MM##MM##=;$H@##
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXX$XHH$++$@###HH@MX%/;:;::::::=:::;;/++++%%$$XXXHH@HMMM#M##==+X@@##
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX$X@H$++//$#XX@X$+/:==:=====:=:;;///++%%%$$$XXHH@XM#MM###@=;%XHM#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXHH@X$XX$+##X$+;;=:/;++%$%;/$;:;;/++%%%%$$XXXH@HXM#@#M####@%%XM#
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXHXXXHHXXHHX+/#HHMXX$M###M%+-,X$=:;///+%%%%$$HHXH@$XM##M#M#M###@H@M
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXHHXX%$XHX$X$+;-HH@#HHHM+..   -M@-=:;;//++%%$$$XHMH%$X#M#M##MM#######
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXHHXX%$XX$%/+$###HX#$,..     :##=-:;;;;/+%+%%XX@MX%$$$#M#####M#MM####
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXX$XHHX%:M#####@X##/,   :/X##%-=::;;/++%%%XHMM$%$$X$####H@##M######
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXHHX%/M##M#M##$###M@H@M@##M=-:::;;/+%%$$HMM%+%$$$$###M=/@########
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXXHHH%;###MM##M@H@##M##@@##@;=::::;;/++$$H#@+/+%$X$$@###;%$X@######
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXHH;%###M##@MM#HM#######$;==:=::;/+%%$@#%;;/%$$$$$H#$+/$;%HHM####
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXH%:##M@###@$H#X@M@HX+/;==:::=:;;/+$HMH/:;++%%%$$$H#+%:$MXXH@M###
#MM@@HXXXXXXXXXXXXXXXXXXXXXXXXXXXHXXX+%####M#@XH#X+H/:;;;;;:::==::;/+$XH+=:;;/++%$$$X$#$%XX/$%%X@M##
#MM@@HX$XXXXXXHXHHHHHHHHHHHHHHHHHHXX$/@#MM#M@X$MH/=H%++////;::::::;+$HX;=::;/++%%%%$$XH$$/-:+X%H@M##
#MM@@HXXXXXXHHHHHHHHHHHHHHHHHHHHHHHX%%#MH#M#%X#H%;,%H$+++//;:::::/+$X+:::::;//++%%%$$$X$/%$::+HM@@##
###@@HXXHHHHHHHHHHHHHHHHHHHHHHHHHHXX+$#@M@MHX#H++-=,/$///;;:::::/+$X+;;::::;///++%%%%%X@M@$;=:;$H@##
##M@@HXXXXHHHXXXXXXXXXXXXXXXXXXXHHX$/@#@MM@X#M+/:--,-%%;;;;:;:=:/$$+/;;::::;;//+++++%%$H$$%;;+=+X@##
#MM@@H$$XXXXX$$$$$$$$$$$$$$$$$$$$XX+;##MMM@##%%;-;===;X$++;;/;;+XHX%//;;;;;;//+++++%$$$%//%%;/+$XH##
#MMHH$$XXXXXXX$$XXXXXXXXXXXXXXXXXXX+/##MMM@#@%X+%/:+=-+XX$$HHH@M@HX%+//++//++++%%+%$XHX%XX+$+;;%XHM#
##MXXXH@@@@@@HHH@@@@@@@@@@@@@@@@@HH$H##MMM##X$+/%%///;//=:/@@MMMHHX$%%%%%%%%$%$$$$XH@HX$%%$%$X/%$XM#
#M@XH@MMMMMMMM@@MMMMMMMMMMMMMMMM@@@X###@#M#@$%%%$%+++%+%+%$#@@MM@@H$XXXXXXXXXXXXHHH@M@HX%%%HHH$X$X@#
#MHH@@@@@@MM@@@@@@@@@@@@@@@@@@M@@@@@###MMM#@XXXX$$$$$$%%%X@M@MMM@@HHHHHHHHHHHHHHH@@@@HHXXXXXHHXXXX@#
#M@M###MM######################M#M######MM#MMMMM@@@M@@@@H@M#M###MMMMMMMMM@@@@@@@MMMMM@@@@@@@MMM@@@M#
####################################################################################################