''''',*+:---?%%%%&&&&&$$$$$$$$$$$$$$$=%&&&%%&&$$$$$$$$$$$&&$&&&&&&&&&&&$$$$$$$$$
''''',*+:---?%%%%%&&&&&&$$$$$$$$$$$$$%===??%%&$$$$$$$$&&&&&&&&&&&&&&&&&&&&&&&&&$
''''',*+:---?%%%%%&&&&&&&&$$$$$$$$$$$%***??==%&&$$$&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
''''',*+:---?%%%%%%&&&&&&&$$$$$$$$$$&?+!!+??=%%%&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
'''''.*+:---+=%%%%%&&&&&&&$$&$$$$$$$&?+;!!?==%%&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&$
'''''.*+:---+=%%%%%&&&&&&&&%=&$&%%==&?*;!*+?==%&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
'''''.*+:---+=%%%%%&&&&&&&&%&$$&&=?%?**;!!!?=?=%&&&&&&&&&&&&&%%%%%%%%%%%&&&&&&&&
'''''.*+;--~+=%%%%%&&&&&&&&%&%%=??=?!!!:~-;!+?=%&&&%%&$$$&&&%%%%%%%%%%%%&&&&&&&&
'''''.!+;--~+=%%%%%%&&&&&&&&&=??+++*;!!-~-:;*+?=&&=+==%&###$%%%%%%%%%%%%%%%%%%&&
'''''.!+;--~+=%%%%%&&&&&&&%&&==????+*;;!:-;!!+?%&=:::+%$$###$%%%%%%%%%%%%%%%%%%&
'''''.!+;--~*===???=&&&&&?=&$%===%%%=**++;-:!++=&;~~-;=$#####&%%%%%%%%%%%%%%%%%&
'''''.!+;---*=!::-:*&&&&&&&&&&&&&&%%%%???*:;:;;==-:+*++&######%%%%%%%%%%%%%%%%%=
,,,,,-*?;---*=*::::*&&&$$$$$&&&$$$&&&&&&&&+;~~:?=*!?=%?=######??+++++++++??????=
''''.~*?;---*=*;:::*&&$$$$$$&%=$$$$&&$$$$=&%:-:%?!::!;!?$####$+===%%%&?=$$$$####
'''''.!?;---*=*;:::*&&$$$$$$&%=$$#$$$$$%;-;=+--*:+:~-*=&$#&$@&?##$$$#$=%##@@#&&&
'''''.!?;---*=+;:::*&&$$$$$$&%?$##$$$$=-==%=&*-,-!-:+=&$$%=$@#$&?++%&%?&###@#!;=
'''''.!?!---*=+;:::*&&$$$$$$&=?$##$$$$?-+++%$$&?;?!!*?%$#&$@@@##*!!=&%?&#####::?
'''''.!?!---!=+;::;*&&&&&&&&&%+$##$$$$+-:-!%###$*!!*?%$###@@@@@#*!!=&%?&#####::?
'''''.!?!:--!=+;::;*&&&&$$$$&%?$##$$$$*-;!%$##$$%%%&$$####@####&!!!=&%?&#####::?
'''''.!?!:--!%+!:::*&&&$$$$$&&$$$$$$$&--*%####$$$$$&&$$$$#%=&&&%*!*=&%?&###@#!;?
'''''.!?!:--!%+!;::*&$$$$$$$&$#####$$?,;?$#####$$$$$?&&%&$&?+*?&====&%?&#####%=&
'''''.!=!:--!%?!;::*&$$$$$$$$$$$&&$$$!~*%####$$$$$$&+?==%%&%+*?&%%%%&%?&#####%%&
'''''.!=!:--!%?!;:;*&$$$$$$$$$$&%=&&?**=$###$&&%%%%&=++=??=?=+=&%%%%&%?$#####&%&
'''''.;=!:--!%?!;;;*&$$$$$$$$$$&%=&=&?%$$##$===??+*%?!++*=?*%++???%%%%?%&&&&&%%%
'''''.;=*:--!%?!;;;*&$$$$$$$$$#$$$$=%=%$##&+%%%=??*%*;*!+?++?+**+%$##$=$#@@#####
..,,,-*=*:--!%?*;;;*&$&$$$$$$$#$$$&%+?%$#$++%&%?+*+?!*??+++=++!*&&&$&??$$$$&$$%&
'''''.!=*;:-!%=*!;;+&&$$$$$$$$#$$%+=!*=&&+=%&&%?++**+=##$$%$+!+$%&&$&*?$?;?:+%;+
'''''.;=+;:-!%=*!;!*%===========%=*%+=&$&%&&&%=???%$$#&====?*+&#=&$#$%=$+:+~+=~!
*+,''.;=+;:-!%+?===?==%%&&&&$$$$%?=%===&$$$$%=???&=???++++*+?%#$&$$#$%=$*:+~+=~!
%=,''.;=+;:-!%%&&&&$&&&&&&&$$$$$=?&===%$###$??++=**+***++++=%$#&%$$##&=$*:+~+=~!
%?~''.;%+;::!&%%%&&$&&$$$$$$$$$$++%=?&&####$=++++***!;!!;*+=%##?%$###&=#+;+~??~!
%:-''.;%+;::!%%&&$$$$$##########++=+==$####$=++++?+*!;!!!+???#$&$####==#$%&?&%+=
%**!!+=%?!;:!%&$$###############%+?==##$###@&=?*+++!*?%%&&&&$@#$$####*?##$&%&&%&
&%%%&&%%=*!;*&&$#############%=%$%?+%$######&??=?=++?=%==&@@@@#$####@%=##$&&$&&&
&=?!;::;;::;!?$############&+++?+!;++=$#####$&$$&=??==%=&#@@@@#$$###@$=&&%%%&&%&
=?+++?==%%%&&&$###########?**=?+;;*?+==%$######$&&%==%&$#@@@@@#$&###@#%######$$$
$$$$$$$$$$$$$$$$$####$$#$+*++=!!;!??=%%==$######$$%=&%$$####@@##$$##@#%###@@@@##
$$$$$$$$$$$$$$&%&$$#$$$&*!?+**!**+=+&%$&%%&##$$$$$$$$$######@@##$$###&%###@@@@##
$$$$$$$$$$$$$$%%&$##$$%+*=?*****%==%#&#&=%%%$%&$$=&#######@@@##$&$###=%#########
$$$$$$$$$$$$$$%%&$##$=+*+%***+?+%=%$#&#$&&%%%%$#%$&$####@##@#$#$&&###+%##$&&&$$#
$$$$$$$$$$$$$$%%&$$%+++*+*+**???$$%$#&##&&&%%=%$$$$#####@###&&#$$$$$#%%##$&&%$#@
$$$$$$$$$$$$$&%=&$=::;!;-;??+&==#$%##$##$&&%%=&%&&$###$@@@@#&$$$$&&%&$$###$&&$#@
$$$$$$$$$##$#&%%&?-:::--::!+?$%%#$$@@###&&&%%%&&&%&###$#@@@$&$&===?=%$$###$&&&#@
############$&%%%:::::-:::;+&#&%#$#@####$&&&&&%%&&&&&$#@@@#$&$$?=??=%&$####$&$##
#############&%%%$%+?=!;;!*?&##$########$&&&%%%&$&&&=?%$#@#$$$$=??%&##?+**?%&$$#
#############&%%&$&&=*&+*+=%$#####@@#####$&&%=%$$&&&&&%==$&*;:~~~*$&&#;,,,-:!???
##########$##$&&$$%%$##$=&$$#######@#####$&%&&#$&$&&&&&$&%&;:-:!!!==&#+;*+????=%
###$#######$#$&$&=?$#@@@#$###$#$####@####&&&$#&$&&&$&&$%&&$=?+*=$??=%#%%&%&&&&$$
#$####%*+=$#$&&%=%$#@@@@@##$$$$&$####@###$$$##&$=&$$$&$&&%%===%$$&=?=$?++%##%=$&
$&$###%--!=$$%%??$#@@@###$$$$$$$$$##@@@###$#$#&&&&$#$$$&$&&&&+%&##$?=$=++&##&$##
%%$#$$$?*=%&&&=%$@@@####$$$=++===%$##@@#####$#$$$&$#$$#$#$$$$%$$@@$=?$&%%%##&$##
%$####$$&&&&&%$#@@@@$&&&&&&!??????&#########$$$$$$$$######$$$%&#@@$%?&#$$$$#$###
&%=*!;;;*?%%&#@#@@@@#%%====*+***+++=$##@@#####$$#######@@###&%%$$$$&?%$%=%$#####
%*-'..,-!%??$##@@@@@#!~,,,,,~~~~--!*?&##@@@###########@@@@##&&&&&&&&??&$$$##$$$$
;*-'..,-??*=#@@@@@@@@*--~~,,,,,,~~:*?=&&$@@@@#######@@@@@@##$$&&&&&&%*!!**+??%&$
;*::*?=%=+=#@@@@@##@#?+?=&&&&&&&&&&&&&&$#@@@@@@@@##@@@@@@#####$$&&&&%?!!*++?=%%%
&=+%?%$#$##@@@@@@$#@&%%%%%%%&&&&&&&&&&$#######@@@@@@@@@@@###$$$$$&&&&&&$#$$$&$$$
==&&$####@@@@@@@&=$#===%%%%%%%%%%%%%%&$$$$################$$$$$$$#####@@@@@@@@@@
===%###@@@@@@@@$??$&============%%%%&&$$$$$$$$$$$$$$$$$$$#####@@@@@@@@@@@@@@@@@@
=%%$####@@@@@@#%==$%??????=======%%%&&&$$$$$$$$$$$######@@@@@@@@@@@@@@@@@@@@@@@@
###$%+;-+$$@@@@#$&$%=?????=======%%&&$$$$$$$####@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
$%*-,,;&@@@@###$&%$%?=======%%%&&$$$####@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*~..,!&$$$$$$$$$$&$&%%%&&$$$$####@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
&=*-~*%&$$$$$$$$$$$$$####@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
#$&=++&$$$$#####@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
####&$##@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@