#include"bits/stdc++.h"
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define ld long double
#define ff first
#define ss second
#define db double
#define time_begin() auto begin = chrono::high_resolution_clock::now()
#define time_end() auto end = chrono::high_resolution_clock::now(); auto elapsed = chrono::duration_cast<chrono::nanoseconds>(end-begin); auto sec = elapsed.count() * 1e-9; cerr << "\n\nExecution time: " << sec << " seconds";
#define check_time() cerr << "\nStatus : "; if (sec>1) cerr << "Time Limit Exceeded 1!!!1!111"; else cerr << "You good brother"
#define precision(x) fixed << setprecision((x))
#define check_ok(s) cout << s << " is aight" << '\n'
using namespace std;
/*
;;;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;;;:::::::::::::::::::::;;;;;;;;;;:::::::::::::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++
::::::::::::::::;S*.......+%:,....,*%,......,S+,,:;*%+:,..........,:*S##+.......+#SS:.......?@*.............%S:....;%;.....,%?%?,.....*%+?*:,,........,,:;?*,+S,......,S#?.......;S;....................
:::;;;::::::::::+S*.....,.+S;,,...,*%,......:S?;+*%S;......:?*,......+#@%,......:##S......,,S@*.......,,,,::%#?;,..,*%:.,...*#S;...,.;S*%*,.....,*%;......,%?*S,......,S#?.......;S;....................
::::::::::::::::+S*.......+S;,,...,*%,......:#%???#?.......+@@;......,%@#;......,%@*.......;##*.......+#%%%%%%%?+,..,?%,.,..:#S,....:S?*%:.,....,S@?.,.....+S?S,......,S#?.......;S;....................
;;;;;;;;:::;;;::+S*.......+S;,....,*%,......:#S??%#?.......+@#:.......%##*,.....,%@+......,?##*.......*#S%%%???%%*:,.:%*...,,?+....,%?:*%,......,S#*.,.....+S?S,......,S#?.......;S;....................
;;;;;;;;;;;;;;::+S*.......+S;,...,,?S,......:#S%%%#?.......+@@:.......%##S,......*#:......,SS#*......,:;;;;+S%??%%?:.,+S;...,,,....*S:,*S,......,S#*.......+S?S,......,S#?.......;S;....................
;;;;;;;;;;;;;;::+S*.......+S;,,,,,:?S,......:#S%%%#?.......+@@:.......%#S#;......;#:......;#S#*............:#%????%%;,,*S:.,......;S+,,*S,......,S#*.......+S?S,......,S#?,......;S;....................
;;;;;;;;;;;;;;::+S*.......+S;,,,:;+%S,......:#S%%%#?.......+@@:.......%#%#?......:*,......?#%#*.......:++++*S??????%%+,:%?,......:%*,.,*%,......,S#*.......+S?S,......,S@?.......;S;....................
;;;;;;;;;;;;;;::+S*.......+S;::;+*?SS,......:#S??%#?.......+@@:.......%#?%S:.....,+......:SS%#*......,*#%???****????%%*:;S;......*S:..,*S,......,S#*.......+S?S,......,S@?.......;S;....................
;;;;;;;;;;;;;;::+S*.......+S;:+???%#S,......:##%%%#?...,...+@@;......,%#?%#+.....,,......+#??#*.......+#%%%??****????%%?*S;......*%:..,*%,......,#@*.......+S?S,......,S@?.......;S;....................
;;;;;;;;;;;;;;::+S*.......+S*?%%?%%#S,.....,,:;::+#S:..,,.,:%%:..,,..;#%??#%,............?#??#*.......,:;;;;*S?****????%S#;......*%:...;S+......,?S+.,....,%?+%+.....,,?S+,.....,*%:....................
;;;;;;;;;;;;;;:;+S*.......+#%%%%%%S#S,...........:##%;,............,+S%?*?%#;...........:#S??#*.............+#?*****????S#;......*S:...,+%*:,...........,:??:,+%+:,...........,:*?;,....................
;;;;;;;;;::;;;::+%?;;;;;;;?#S%%%SSS#S;;;;;;;;;;;;*S%%SS?+;;::::;;*?%S?*****S?;;;;;;;;;;;*S%??%?;;;;;;;;;;;;;*S?******???%S*;;;;;;*?,....,:+**+;;:::::;+***;,..,:+**++;;::::;;+**;,......................
:::::;;;;:;;;;:;;;+++++*%SSS%%%SSSSS%S##SS%%%%%SS%??%%%%%SSSSS%%%%???****+**??????%%???%?++*?**????%%%***????*********???%%SS?+;;:,,.......,,:;++++++;;:,........,,:;;++++++;:,,........................
;;;;;;;;;::;;;;;;::,::;?%%%S%SSSSSS%SSSS%?????%%???%%???%%%%%%??%??%%*****??****+++*+++*?+++*?*++++*?*+;;;++***********??????*;,........................................................................
;;;;;;;;;;;;;;;;:::::+?%SSSSSSSSSS%SS#SS%%???%S%?%S%%?%%%%%%???%?*?%%***????????**???***??***??*****???*++;+**************+;:;++:,......................................................................
;;:;;;;;;;;;;;;:::;;+%SSSSSSSSSSSSS###SSS%%%%S%?%SS%%%%%%%???**??**%%?*???%?????????%?**?%?**?%?*?***%?***+;+*******++;:,,,,::;;+;,.....................................................................
;;;;;;;;;;;;;;:::++*%SSSSSSSSS##SS#S#SSSS%%%S%%%SS%%%%%%????*:++?**%%?????%%?%%%%%??%????%????%%????*?%?***;;++;;;::,,,..,,,,::;;+;:....................................................................
::;;;;;;;;;;;::;+*?%SSSSSS######S####SSSS%%SS%%%%%%%SS%??%?+,,*;?**?%%????%%?%%%%%%%%%???%????%%??????S%?**+:,,,,........,.,,,:::;++:,..................................................................
;;;;;;;;;;;::;+*?%%S###SS############SSSS%%#S%%%%SSSS%%?*+;:::*;????%%???%%%%?%%%%%%%%%??%????%%%?????%%???*;,.............,,,,,::;;+;,.................................................................
;;;;;;;;;;::+*?%%SS##################SSSS%S#S%%%SSSS%?*;:,.,,,*;+%%%%S%???%%%%%%%%%%%%%??%%???%%%%????%S%??*;:...............,,,,::;;++:,...............................................................
;;;;;;;;;;+++*SS%SS#################SSSSSSS#S%%%SSSS?*+;;::,,,:;:*S%SSS%??%%%S%?%%%?%%S%?%%????%S%????%S%??*;:...............,,,,,:::;++:,,,............................................................
;;;;;;;+**+;+?SS%SS#################SSSSSSS#S%%%S#S%S###SSS?+;::::*%SSSS%%%%%%S%?%%??%%%?%%????%S%????%S%%?*;:................,,,,,:::;;+;,.............................................................
++++++******?S##SS##################SSSSSSS#S%%SSS+;S#SS######%*;::;?SSSS%%%%%%S%%%%??%%%%%????%SS????SS%%?*;:,.................,,,,,::;;++:,...........................................................
******??????%S##SS##################SS#SSSS#SS%SS%:;%?%SSS#SS?*?%+:::+%%SSS%SS%%SS%%%%%%%%%????%SS???%SSS%?*;:...................,,,,,:::;++;,..........................................................
?????????????S##SS##################SS#SSSS##S%SS?::++;++?%?;:::+;:,,,:+??%SSSS%%%SSSS%%S%%???%SSS???%SS%??+;:....................,,,,,:::;;+;:.........................................................
%????????????%##SS###################S#SSSS##S%SS?;::;++;;::,:::,:,,,,,,;+++??%SS%?%SSS%SS%???%S#S%??SSS%?*:,,......................,,,,,::;;++:,.......................................................
%%%%%%%%?????%S######################SS#SSS##SSSS?;:::::::::,:,,,,,,,,,,,:;;+?SS##S%%SSS%%%??%S##S??%SSS%?+,,........................,,,,,::;;++;,......................................................
????%%SSSSSSSSSS#####################SS#SSSS#SSSS%;::::::::::::::,,,,,,,,,,+%S%SSS%+:;?#SS%?%S###%??S%SS%?;,,.........................,,,,,:::;;+;:.....................................................
????????%%%SSSS#######################SSSSSSSSSSSS*:::::::::::::::,,:::::::++++++;:::;***%%?%S##S%%%%*S%%?:,..........................,,,,,,:::;;++:,...................................................
?????????????%%%SSSSS##################SSSSSSSSSSSS;,::::::::::::::::::::::;;;:::,,,:+*%SS%%S###S%%%*%?%?:,..............................,,,,,:::;+++:..................................................
????????????????%%?%%SSSSS#SS##########SS#SSSS#SSS%*:::::::::::::::::::::::::::;:::;*S##S%%S####S%%?%*+;,.................................,,,,::::;*%?;,,...............................................
??????????????????%??%%%%%%%%#######%%####SSSS###SS*+;:::::::::::::::::::::::::::;?S####SS######SS%S*,,...................................,,,,,,:;*?%%%+,,,.............................................
%%%%%%%%%%%?%??%???%%?%%%%%?%S#S%%%%%?S####SSS%S###S+:;::::::::::::::::::::::::;?S#####%S#######S?*;,......................................,,,,;+*???%%%?;,.............................................
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S#S%???%??%####SSS%S###S+::::::::::::::::::::;;+?%######S?%#####S%+:,.......................................,,::++*??????%%%%+,............................................
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S%%%%%%%%%S#####SS%SS##S*;:::::::;;;;;++**?%SS########%*%#####?:.....................................,,,,::;++******?????%%%%*:,,.........................................
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%SSS#####S%%%S##S%*++**?++**%SSS############S?*%####?:,..................................,,,::;;++***********??????%%%%;,.........................................
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%SSSSSSSSSS%%S###S%%??%S#S%?%%%%%*??*SSSSS##########?+?###?:............................,,,,,,:::;++++*****************??????%%%*:........................................
%%%%%%??%???????%%%%%%%%SSS########SSSSSSS%SS###S%%???%SS%???%%%+%%?S%%%#########?+%#S?:,.....................,,,,,,:::;;;+++++++********************???????%%%?;,,.....................................
%??????????????%%%SSS#################SSSSSSS####S%%%%%%SS%%%%%%?*%????%########%*%?;:,.......,,,,,,,,,,,::::;;;;+++++++++++++++++*+++*****************??????%%%%+,.....................................
????????????%%SSSSSSSSS%%%%%%%%%%%SSSS###SSSSS#S###SS%%%%S#S%??*?**?%??S####S%SS??*;;;;;;;;;;;;;;;;+++++++++++++++++++++++++++++++++++++****************???????%%%?;,...................................
???????%%%%SSSSS%%%%%%%%%%%%%%%%%%%%%%%SS%???%%%?%%S%?****%#%+;+*?*??%?%###S?*?********************+*++++++++++++++++++++++++++++++++++++****************????????%%%+,..................................
?%%%%%SSSSSSSS%%????%%%%%%%%%%%%%%%%%%%%%*++++++++*?%%?*+;+%#%+++??*???%##S???*?**************+++++++++++++++++++++++++++++++++++++++++****+***************???????%%%*:.................................
+*?%%SSSSSSS%%%?????%%%%%%%%%%%%%%%%%%%%?+;;;;;;+++++**???**%#*;;+%***?S##%???*?**************+++++++++++++++++++++++++++++++++++++++++****+***************????????%%%?;,...............................
;++*%SS%%S%%???%???????%%%%%%%%%%%%%%%%%?+;;;;;:;;;;;;;;;;;;+S*;:;??*+?#S%??????**************++++++++++++++++++++++++++++++++++++++++++++*+*****************??????%%%%%*:,.............................
;+*%S%%%%%%%????%%%%%%%%%%%%%%%%%%%%%%%%?+;;;;;;;;:::::;;;;;;?*;++*?*+*#S???????**************++++++++++++++++++++++++++++++++++++++++++++*+******************????????%%%?;,...................,,,,,,:::
;+%%%%%%?????????????%%%%%%SSS%%%%%%%%%%%*;;;;;;;;;;;::::::::+;;;;+??**S%???????***************+++++++++++++++++++++++++++++++++++++++++++*+********************???????%%%?;,........,,,,,,:::;;++++++**
:?%%%%%%%%%%?????????%%%%%%%%%%SSSSS%%%?%?+;;;:;;;;;;;::::::;;:::::;?*+%S%???????**************++*+++++++++++++++++++++++++++++++++++++++++++*++******************????????*++:,,:::;;;+++++*************
;%%%%%%%%%??????**????????%%%%%%%%%%SSSSSS*++;;;:;;;+;;:::::::::::::;?*?%%??????***************++++++++++++++++++++++++++++++++++++++++++++++*++*******************??????+;;+++++*************+*********
+%%%%%%%%%%???********???????????%%%%%%%%S%*+;++;;:;;+;::::::::::::::+??%%?????******************++*++++++++++++++++++++++++++++++++++++++++++++*********************??*;::;;;+*************++++********
?%%%%%%%%%%?*******?????%%%%%?***??????%%%%%*;;;;;;;;;;;::::::::::::::*?%%?????******************++*++++++++++++++++++++++++++++++++++++++++++++**********************;:,:::;;;++***********+*++********
%%%%%%%%%%%?********??????%SSSS%??****?????%%?+;;;;;;;;;::::::::::::::;?%%?????********************++++++++++++++++++++++++++++++++++++++++++++++*****************++:,,,,,::::;;++**********************
%%%%%%%%%%%%?*******????????%SS#S%%???***?*?%%*+++;;;;;;::::::::::::::;?%%?????********************+++++++++++++++++++++++++++++++++++++++++++++***************++;:,,,,,,,,,:::;;++*********************
%%%??%%S%%%%??*****????????????%S##SS%%?????%S%+++;;+;;:::::::::::::::;*%%?????********************+++++++++++++++++++++++++++++++++++++++++++++***********++;:,,,...,,,,,,,,:::;;;++*******************
%%%???%SS%%%%??****??????????????%S###SS%%?%SS%+++;;;;;::::::::;;;;;::;*%%???????*****************+**++++++++++++++++++++++++++++++++++++++++++++******++;::,,..........,,,,,,,:::;;;+******************
??????%SS%%%%%??*****???????????????%S###S%SSS%+++;+++;:::::::::;;;;::;*%%??????********************++++++++++++++++++++++++++++++++++++++++++*+**+;::::,,,,,,,,........,,,,,,,::::;;;++****************
???????%SS%%%%%???***??????????????????%S####S?+;++++;::::::::::;;;;::;*%%?????***********************++++++++++++++++++++++++++****++++++********?*;:..,.,,,,,,,,,.......,,,,,,,::::;;++**********++***
????????%SS%%%%%??****????????????????????%SSS?++*++;:::::::::::;;;;::;;+**?????***********************++++++++++++++++++++++*?????%??*************???;,,.,,....,,,,,,,,....,,,,,,,:::;;;++********+++*+
?????????SSS%%%%%??*****?????????????????????%%?*+++;::::::::::;;;;;::;;;;:;++*******************+++++*+++++++++++***********?%%%%??%%?**************??+,,,.....,,,,,,:,,...,,,,,,,,::::;;++*?*+***++++*
?????????%SSS%%%%%???******????????????????????%?++;:::::::::::::;;;::;;;;:::,,,::;;++++++***+*****+****+++++****************?%S%%????%?*************???+,......,,,,,,,,,,,,,..,,,,,,::::;;;+??**+*++++*
%?????????%SSS%%%%%%???*******????????????????????+:::::::::::::::;;::;;;;:::,,,,,,,,,,,,,,,:::::::::::::;+**??***************%S%%%????%??????????????%??;....,,,,,,,,,,,:::::,,,,,,,,,:::;;+?%?***+**++
%%???????*?%S#S%%%%%%%??***************????????????+::;;;;;::::::::::::;;;:::,,,,,,.,,..............,:;+***?*****************?%S%%%?????%%%%????????????%*,.,,,,:::::::,:::;;;;:,,,,,,,,::::+?%%??*+*+++
%%%??????**?S##S%%%%%%%???*************************?*+;;;++;:::::::::::;;;:::,,,,,,............,,:;+*???*?******************?%%%%%%?????%%%%?*****???????*:,,,,,,,,,:::::::::;;;:,,,,,,,,,::*??%%%?***++
?%%%????**?%%SS#S%%%%%%%????***********************???*;;+;;;::;;;;;++;;+;:::,,,,,,.........,,;+*????????%%%%????**********?%%%%%??***?%%%%%?*******?????*;;;:::,,,,::::;;:::::::,,,.,,,,,:+?????%%?**++
??%%%????%??*?SS#SS%%%%%%%???**********************???%*++;;;;+++++++++++++;:,,,,,,.......,:+*????????%%%%%%%%%%%%????????%%%????****??%%%%%%?******??*+;:,,,......,,,,,:::::,,...,.....,;**?????%%%?***
S??%%%%%%??????SS##S%%%%%%%?????******************??%SSS%??*+++++++++++;;;++:,,,,,,.....,;*???????????????%%%%%%%%%%%%%??%????******???%%%%%%????*+;:,,..............................,,:+*??????????%?*+
%%??%SS%????????S###S%%%%%%%????***************?%%SSSS%%%%?????*++++++;:;++**+;,,,,..,:*??????????????????%%%%%??%%%%%%??????******?%????%%%?+;:,,.................................,,:+********???????*+
%??*%%%%%????????%S##S%%%%%%%???***********??%%S%%%%%???%SS%?***?**+++;+**???%%?*+::;*%%?????????????????%%%%%%%%%%%%?????????****????????*;,....................................,:;+***********??????*+
;;*?????%%%???????%S##S%%%%%%%?******?????%%%%?????????%%##S??***?????????%%??%%SSSSS%??????????????????%%%%%%%%%%%%%??????????**?????%??+,..................................,,,:;+****************??**+
;;+??????%%%%??????%S##SS%%%%%%?***??????????????????%%%%###%???***?????%SS%?%%SS#S%????????????????????%%%%%%%?????%??????????????%??*;:,,...............................,,,:;+**********************++
;;;**??????%%%%?????%S###S%%%%%????????????????????%%%%%%###S%????????%SSS%??%S#S%?????????????????????%%%%%%%?????????????????????*;:,..............................,,,,:;++************************+++
;;;++??????%%%S%??????%S##S%%%%%%%%%?????????%??%%%%%%%%S###%%%%%%%?%S###S%%%SSS%?????????????????????%%%%%%%%???????????????%%%?;,,..............................,,::;+++***************************+++
;;+++**?????%%%SS%?????%S##SS%%%%%%%%?%%%%%%%%%%%%%%%%%%S##S%%%%%%%%S####SSSSS%???????%%%????????????%%%%%%%?????????????%%%?*+:,...........................,,,,:;;+++***++************************+++++
+++++***???%%%%%%SS%%????%S##S%%%%%%%??%%%%%%%%%%%%%%%%%S##%%%%%%%%S####SSS%%????????%SS%??????????%%%%%%%%%?????????%%%??*;,,........................,,,,::;;++++***+++*+++*********************+++++++
****?*?*??%?%%%%%%SSS%%???%S###S%%%%%%??%%%%%%%%%%%%%%%S###%%%%%%%S####SS%%?????????%SSS%??????????%%%%%%%??????%%???*+;:,.....................,,,,,::;;++++++++++++++++****+******************+++++++++
***++++;;+*??%%%%%%SSSSS%???%S###S%%%%%%?%%%%%%%%%%%%%%S##S%%%%%%S####S%???????????%SSS%%?????????%%%%%%%????%?*+;:,,.................,,,,,:::;;;++++++++++++++++++++++++++*+++*************++++++++*+++
;;;::;;;;;;+*??%%%%%%SSSSS%???S###S%%%%%%%%%%%%%%%%%%%%S##S%%%%%S###S%????????????%SSS%%%????????%%%%%??????*+:,...,,,,,,,,,,,,:::::;;;;+++++++++++++++++++++++++++++++++++*++***+*******+++++++++++++++
:::;;;;;;;+++**???%%%%%%SSSS%%?%S###S%%%%%%?%%%%%%%%%%%##S%%%%%%S##S%????????????%SSS%%%????????%%%%%????*+;;;;;;;;;;;;;;+++++++++++++++++++++++++++++++++++++++++++++++++++++***+++++++++++++++++++++++
:::;;;++****+++++*???%%%%%%SSSS%%%S###S%%%%%%%%%%%%%%%S##S%%%%%S#S%????????????%%SSS%%%????????%?%%%%??**++*****++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
;;++*****+++;;+++++**???%%%%SSS#SS%SS##SS%%%%%%%%%%%%%S#S%%%%%%SS%????????????%SSS%%%%?????????%%???**+****++*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+***++++;;;;;;;++++++++***??%%%SS##SS####S%%%%%%%%%%%SSSS%%%%%%%?????????????%%%%%%%????????????***++++*****++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++;;;++;;;;;;;;+++++++++++++***??%%SS######S%%%%%%%%%SS%%%%%%%%????????????%%%%%%%??????????*****************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
;;;;;;+++;;;;;+++++++++*************??%%SS###S%%%%%%%%%%%%%%%%???????????%%%%%%%%???????*******************+**++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++;;++++++++++
;;;;;;;++++;;++++++++++++++++***********??%SS##SS%%%%%%%%%%%%??????%%%%%%%%%%%%??%%%%??******************++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++;;;;+;+++++++++++
;;;;;;;;;;+++++++++++++++++;;;;;++***?%%%%%%%%S%%%%%%%%%%%%%%%%%%%%%%%%%%?%??????????????????********************+*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++;+;+;;++++++++++++++
;;;+++;;;;;+++++++++++++++*****??%%%%%???****++++++**??%%%%%%%%%%%%%%%%???**++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++;;;;+++++++++++++++++++
;;;;;;;;;;;;;++++++++++**????%%%??***+++;;;;;;;;;::;;;;;+++****????***++;;;;;:::;;;;::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;+;;;+++++++++++++++++++++++++++++++++;;;;;;;;;++++++++++++++++++
;;;;;;++++++;;;;+++**?????%??*++;;;;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;+++++++++++++++++++;;;;;;;;;;;;;;;++++;+++++++++++++
;++++++++++++++**?????%??*+;;;;:::::::::::::::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::::::::::::::::::;;;;++++++++;;;;;;;;;;;;;;;;;;+;;;;++++++++++*+***
;;;++++;;+++*??????%%?*+;;::::::::::,,:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::;;;;;+++++;;;;;;;;;;;;;;;+++++*********???
+++++;;+**??????%%?*;;:::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::::::::::::;;;;+++;+++++++*****?????????????
++;++*???????%%?*;:::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::::::::::::::::::::::::::::::::::::::::::;+****??????????????????????
;;+*??????%%?*+;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::::::::::::::::::::::::;*????????????????????????
+???????%%?+::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::::::::::::::::::::::::::::::;*??????????????????????
??????%%*;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::,,,:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::,,,,,,,:::::::::+*?????????????*****++
?%??%?+;:::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;:::,,,,,,,,,,:::::::::;+??****++;;;::,,,,,,
%?%?+::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;::;;;;;;;;;;;;;;;++;;;;;;;;;::::,,,,,,,,,,,,,,,,,,,::::::::+:,,,,,............
?%*;:::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;+++++++++;;;:::::,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::;,.................
%+::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;++++++++++;;;::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::;,.................
*:::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;+++++++++++;;;:::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::;:..................
:::,,,,,,,,,,,:,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;+++++++****++;::::::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::;;,..................
:::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;;;;+++++++****++;;::::::,::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;,...................
::,,,,,,,,,,,,,,,:,,,,,:,,,,:::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;;;;;;;+++++++*****++;::::::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::,,....................
,,,,,,,,,,,,,,,,,,,,,::::::,,:,:::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;;;;;;++++++********+;:::::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;:,......................
:::::,,,::::::,,:::::,::::::::::::::::::::::::::::::::::::;;;;;:::;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++*****???***+;::::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:,,,,,:::::;;;;:,,......................
******++******?******+;:::+**?****?**;::::::;**?????**+***????*****???????*??????????????*+*????%%%%??%?????***+:,,,,,:+**********+::+******+:,,,:+***************++******????*****+++++********++:,....
,,,,,*##;,,,,,S+,,,,;S*:+??;:,,,,,,:+??+:::;?%:,,,,,,%#S:,,,,,,?#S,,,,,,,,,S#;,,,,,,,,::;?SS%,,,,,*S?S*,,,,,,,;S+:,,,,+S;,,,,,,,::;?%S:,,,,+S;,,:*S:,,,,,,,?#:,,,:S#?,,,,?@;,,,,,,,,*@?,,,,,,,,::;?*:...
,....;@S,....;#;....:S*;%?,..,,%?,...,%%;::;?S,......+@?.......?@S,....:+++S#;....:?+....,S@S,....*S%S:..,:,..,%%:,,,,+S;....:?:...:##:....;S+,,;%?,..,:,..;@%,..,%@;...;##;....,++;*#?.....*?,...,%*,..
+....:#?,....*@;....:S*+S+....,#S.....*S+::;?S,...,,.:S;.,:....?@S,....*@S%%#;....:@%.....?@%,....*SS?,..,;:.,.+S+,,,,+S;....;#;...,##:....;S+,:+S;...,+,..,%@*...+%,..:%%S;....:#S*+%?.....%@,....%?,..
%,...,S*....,S@;....:S*+S*....,SS+++++??;::;?S,...+;.,+,.:+....?@S,....,;:+##;....:#?.....?@S,....*#S+..,,%*.,,,%?:,,,+S;....:+,...:##:....;S+::?%,...;S:,,.+##+..,:,.,%?+S;....,:::%#?.....;;,,,:+%;,..
#;....+;....;##;....:S*+S*....,SS%%%%%*+;::;?S,...+*..,,.+*....?@S,...,:;:+##;....:#?.....?@S,....*#S:...,S?,.,.+S;,,,+#;....,,::;+?SS:....;S+:;S*....+@;.,.,%SS:.....*%:;S;....,:::%#?.....;;,,,;?%;...
#*....;:....*##;....:#*+S+....,SS,,,,,*%;;:;?S,...+%,...,%*....?@S,....*#?*?S;....:@?.....?@%,....*@?,...,++,.,.,S*:,,+S;....:S%**+;*S:....;#*;*S;....;*:..,.*SS*....:S+,;S;....;#%+;%?.....%#,...,%?,..
SS,...,,...,SS#;....:??*#*....,S%.....?%;:;;%S,...+#;.,.:#*.,..?@S,....+%?*?#;.,..:S*.....?#%,....*@+...,,::,....?%:,,+S;....:S+:,,:*S:....;%?*S%,...,:::,...:##?....:S+,;S;....:??*+S?.....%#,....%?,..
%#+........+#S#;.......,S#+,...::..,:*S?+++*SS,...+@*...;@*....?@%,........+@;....,,,....:%S%,....*S,....*##+....;S+,,+S;....:S+::::*S:.......,#*....,S#%,...,?@?....:S;.;S;........:#?.....%#,....%?,..
%SS********%#S#?********S##S?*++++*?SS%?????%S****?#S***S#%****%SS*********?#?*********??%?*%*****%S*****%%%?*****%*;;+%?****?%*;+;+*S?********#?****?S%%*****%#S*****%+:;%?*********S%*****%S*****%*:::
*/
void setIO(string s = ""){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
if (!s.empty()){
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
}
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 800;
char grid[N][N];
int n, s;
int startX, startY, homeX, homeY;
int bee[N][N];
bool vis[N][N];
queue<pair<int, int>> q;
bool inside(const int &x,const int &y){
return (x>=0 && y >= 0 && x < n && y < n && grid[x][y] != 'T');
}
void ff(){
while (!q.empty()){
pair<int, int> p = q.front();
q.pop();
int x = p.ff, y = p.ss;
for (int i = 0; i < 4; i++){
int curX = x + dx[i], curY = y + dy[i];
if (curX == homeX && curY == homeY){
bee[curX][curY] = n*n*s;
} else if (inside(curX, curY) && bee[curX][curY] == -1){
bee[curX][curY] = bee[x][y] + s;
q.push({curX, curY});
}
}
}
}
bool valid(const int &minute){
memset(vis, 0, sizeof vis);
queue<pair<pair<int, int>, int>> qq;
qq.push({{startX, startY}, minute*s});
while (!qq.empty()){
pair<pair<int, int>, int> p = qq.front();
qq.pop();
int x = p.ff.ff, y = p.ff.ss, curS = p.ss;
if (x == homeX && y == homeY) return true;
vis[x][y] = true;
for (int i = 0; i < 4; i++){
int curX = x + dx[i], curY = y+dy[i];
if (inside(curX, curY) && !vis[curX][curY]){
int nxt = curS + 1;
if (nxt < bee[curX][curY]){
qq.push({{curX, curY}, nxt});
}
}
}
}
return false;
}
int main(){
setIO();
cin >> n >> s;
memset(bee, -1, sizeof bee);
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cin >> grid[i][j];
if (grid[i][j] == 'M'){
startX = i;
startY = j;
} else if (grid[i][j] == 'D'){
homeX = i;
homeY = j;
} else if (grid[i][j] == 'H') {
bee[i][j] = 0;
q.push({i, j});
}
}
}
ff();
int l = -1, r = 100000;
while (l < r){
int m = (l+r+1)/2;
if (valid(m)) l = m;
else r = m-1;
}
cout << l;
}
/*
Me when im restarted
++++++++++++++++*S%+*++***?%+;;;;;;*%++**+***S*;;;;;*%S%?*+;;;;+*?%SSSS#*+++***+%%?S?+*****+?@%***+***++****%?;;;;;*%**+*++?%+*S****+**%*;*%%?*+;;;;++*%%?+;;*%*+**+++*%S%+++++++?%+:;;::::::::::::::;;;
;;;;::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;::::::::::::::::::::::;;;;;;;;;::::::::::::::::::::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++
;;;;;::;::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;::::::::::::::::::::::::::;;;;;;;;::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++
;;;;;;;;;;;;;;::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;::::::::::::::::::::::::::::;;;;;;;;;;:::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;;;;:::::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++
;;;;;;;;;;;;;;;;;;;:::::::::::::::::::::::::::::::::::::::::::::::::;;;::::::::::::::::::::::::::::;;;;;;;;;;:::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;:::::::::::::;;;;;;;;;;;;;;;;;;;;;;;;;+++++
;;;;;;;;;;;;;;;;;;;;;;;;;;;;:;:::::::::::::::;;;;;;;:::::::::::::::;;;:::::::::::::::::::::::::::::;;;;;;;;;;:::::::::::::::::::::::::::::::::;;;;;;;;;;;;:::::::::::::::::::::::::;;;;;;;;;;;;;;;;+++++
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;????%??**++;;;;;;;;;:::::::::::::;;;;;;:::::::::::::::::::::::::::::;;;;;;;;;;::::::::::::::::::::::::::::::::::;;;;;;;;:::::::::::::;*?;::::::::::::;;;;;;;;;;;;;;;+++++
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;:*#S%S#S#SSSSS%%%**+;;::::::::::::;;;;;:::::::::::::::::::::::::::::::;;;;;;;;;;;:::::::::::::::::::::::::::::::::::;;;;;:::::::::::::+%#S?+:::::::::::;;;;;;;;;;;;;;;+++++
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;?S%%#S#SSSSSS####S%%*+;;::::::::;:::::::::::::::::::::::::::::::::::::;;;;;;;;:::::::::::::::::::::::::::::::::::::::::::::::::::::*?#%???+::::::::::;;;;;;;;;;;;;;;+++++
++;;;;;;;;;;;;;;;;;;;;;;;;;;;;*?++?S##SSSSS####S%S%%%%??*+;::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*?%%???**;:::;;::::;;;;;;;;;;;;;;;;++++
++++;;;;;;;;;;;;;;;;;;;;::::::+%??*+?%%%SS######SSSS%%%%%??*+;::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*?%%????*++;;:::::::::;;;;;;;;;;;;;;++++
++++;;;;;;;;;;::::::::::::::::;*?SS?**++**??%%%SSSSS?SS%%?*++;,,,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*?%%??????++;::::::::::;;;;;;;;;;;;;;++++
;;;;;;;;;;;;:::::::::::::::::;;;*%#%%?*%?*++++++***??SS%%*++;,,,::,::::::::,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::+?%%?*?????*;;:::::::::;;;;;;;;;;;;;;+++++
;;;;;;::::::::::::::::::::::::;;;+?%%%%S#S%?*+;;;;;;;;+***++:::::::,,,,,,,,:,,,,,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::+?%S%?*?????+;:::::;;:;;;;;;;;;;;;;;;;;;+++
::::::::::::::::::::::::::::::;;;;;;+*%%S%???****++;:;:,,,:;::,,,:,,,,,,,:;+;;;:;;:,,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::?%%??*??????+;;::::;;;;;;;;;;;;;;;;;;;;;;++
::::::::::::::::::::::::::::::;;;;;:::;;***??********++;;:,,,,,,,,,,,,,:;+**++++;;;;::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*%S??**?????*+;:::::;;;;;;;;;;;;;;;;;;;;;;;+
:::::::::::::::::::::::::::::;;;;;::::::::;+*++***+++++++++;;:,,,,,...,,,:++:,:*******+;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;?S??**?????**+;:::::;;;;;;;;;;;;;;;;;;;;;;;;
::::::,::::::::::::::::::::::;;;;;;:::::::;;;;;;++++;;;;;;;;;::;;;:::::,,,,,,,:;????????+::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*??***??????**;;;:::::;;;;;;;;;;;;;;;;;;;;;;;
:::::::,::::::::::::::::::;;;;;;;;;;;;;;;;;;;;;;+;;;;;;::::::,:;;;;+;;;++;;;:;:;********?+::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;??*?????%??**+;;::::::;;;;;;;;;;;;;;;;;;;;;;;
:::::::,,::::::::::::::::;;;;;++++++;;;;;;;++;;+;;;;;;;;;::;::::;;;++*+*?***++;;+;;;;;;+**+:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::+?*?????%?***+;+;::::::;;;;;;;;;;;;;;;;;;;;;;;
:::::::::::::::::::::::::;;;;;;;;+++++++;;;;;;;;;;;;;;;;;::;;;;;;;;++++;*+**??*+***********;::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*???????**+++++;::::::::;;;;;;;;;;;;;;;;;;;;;;
:::::::::::::::::::::::::::::::::;;;+++;;;;;;;;;;;;;::::::::::::;;::::::++++***++*******??**::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::**?????*+;;+**;:::::::::;;;;;;;;;;;;;;;;;;;;;;
:::::::::::::::::::::::::::,,,,:::;;+++;;;;;;;;;;;;;;;;;;::::::;;;;;;:::;;;;;++++*++*******?+::::::::::::::::::::::::::::::::::::::::::::::::;:::::;;;;;;+**??**+++;+++:::::::::::::;;;;;;;;;;;;;;;;;;;;
::::::::::::::;;;;;::::::,,,,,,,::;;+++;+++;;;;;;;;;;;;;;::::::::::::::::;;;::;;;+;;*******??+::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;++***????*+;;++;;;;::::::::::::::::::;;;;;;;;;;;;;;;;;;
::::::::::::::;;;;;;::::,,,,,,,,::;++++++++++++;;;;;;;;;;;::::::::::::::::;;:::;:;+:;+****????;::::::::::::,:::::::::::::::::::::::;;;;;;;;++***????????*?**+:::::::::::::::::::::::::::::::;;;;;;;;;;;;
:::::::::::::;;;;;;;:::,,,,,,,,::;++++++++++++;;;;;;;;;;;;:::::::::::::::::+;::;;:+;,;*++?????*;:::::::::::::::::::::::::::::::::;;;;;;++**????????????%S%%?*+;:;::::::::::::::::::::::::::::;;;;;;;;;;;
:::::;;;;:;;;;;;;;;;:::,,,,,::::;;;+++++++;;;;;;;;;;++;;;;:::::::::::::::::++;::;:;;::+****?????+:::::::::::::::::::::::::::::::;;;+**??????????????%S####S%?**+;;;;;;::::::::::::::::::::::::;;;;;;;;;;
;;;;;;;;;;;:::;;;;;;::::::::::::;;;;;++++;;:::::;;;;++++;;;:::::::::::::::,;+;;:::;;:::+*+*??????+::::::::::::::::::::::::::::;++**?????????????%S#######S#S%%?*++;;;;;;;:::::::::::::::::::::;;;;;;;;;;
;;;;;;;;;;;:::;::::::::::;;;;;::::;;;;++;;:::::::;;++++++;;;:::::::::::::,,,+++:::;+:::;*++*??????+::::::::::::::::::::::::::;**?????????????%S##@@#######S#SS%?*+;;;;;;;;;::::::::::::::::::::;;;;;;;;;
;+++;;;;::::::::::::::;;;;;;;:::::;;;;+;;:::::::::;;++++;;;;:::::::::::::,,,;++;:;;;::::+*****?????*;:::::::::::::::::::::::+*??????????%SS##@################S%?*+;;;;;;;;;;;;::::::::::::::::;;;;;;;;;
;;;;;:::::::::::::::::::::::::::::;;;;;;::::,,::::;;;;;;;;;::::::::::::,,,,,:+*;;;;+;:::;***+*?????%?;:::::::::::::::::;;;:+?????%??%%%SS################S#SS##S%?*+;;;;;;;;;;:::::::::::::::::;;;;;;;;;
:::::,,,,,,,,,,,,,,,,,,,,,:::::::::;;;;:::::,,,:::::;;;:::::::,,,,,,,,,,,,,,,:++;;++;::::;*****????%%?+;:;;;;;;;;;;;;;;;;;;+?%%%%#%%%%%SS##@##@@@######S?????S##S%%*;;;;;;;;;;;::::::::::::::::;;;;;;;;;
:::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::,,,,,,:::::::::::,,,,,,,,,,,,,,,,,,,;*;;;;;:::::+****?????%%%?+;:;;;;;;;;;;;;;;;;;?%%??%S%%%%SS####@@@@@@@@##?SS%%??%S#S%%+;;;;;;;;;;;:;;:::;;:::::::;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::,,,,,,,,,,::::::::,,,,,,,,,,,,,,,,,,,;++++;;,,,,,:+****????%%%%%?+;;;;;;;;;;;;;;;;;*%%%%%SS%%SSSS######@@@@##SSS#SS%?%SSSS%*;;;;;;;;;;;;;:;:::::::::::;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::,,,,,,,,,,,,,,,,,;;++;:,,,,,,;*****????%%%%%%*+;;;;;;;;;;;;;;;+%%%%%SSSSS%%SSSSSSS##@@##SSSS##%?%SSS#S?;;;;;;;;;;;;;;;:::::::::::;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::::::::,,,,,,,,,,,,;*++;:,,,,:::;****????%%%%%%%?*;;;;;;+++++++;;+%%%%%S%%%%%%SSSSSSS##@##SSSS#%??SSSSSS%+;;;;;;;;;;;;;;;:;:::::::;;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;+++;;;:::::,,,,,,,:**++:::::::::;****???%%%%%%%%%*;;++++++++++++;*%%%%%%?%%%%%S#SSSSS####SSSSS%*%#SSSS%%?+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
,,,,,,,,,,::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;++++++;;;;:::::::::;*+;:;;;;;;;;;+***???%%%%%%%%%?;::;;;+++++++++;?%%%%#%%%SSSS%%%SSSS###SSSSSSS##SSSSS%%*+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
,,,,,,,,,,::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;+++++++++++;;;;;;;;;:;+;:++;++++++;***????%%%%%%%%?++;;;::::::::::;;*?%%SSS###S%%%%SSSSSSSSSSSSS###SSSSSSS?*+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
,,,,,,,,,,,:::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;++++++++++++++;;;;;;;;+;;+++++++++++*?????%%%%%%%%%????**+++++++;;;;;;+*?SSSSS%%%%%SSSSSSSSSSSSSSSSSSSSSSS%*+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
:::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::;;++++++++++++++++++++++++::;+++++++++++*?????%%%%%%%%%%%%%%???????****+++++%%%%%%%?%%%SSSSSSSSSSSSSSSSSSSSSS%*:::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::;;++++++++++++++++++++++++++;:+++++++++++++*????%%%%%%%%%%%%%%%%%%??????????????%%%%??%%%%%SSSSSSSSSSS##SSSSS%%%?;,,,,:;;;;;;;;;;;;;;;;;;;;;;;;;;
::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::;;++********++++++++++++++++++;;;+++++++++++++*?????%%%%%%???????????????????%%%????%S%%??%%%%%%SSSSSSS###SSSSS%%%?;:;;;:::;;;;;;;;;;;;;;;;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;;+*****************++++++****+;;;******++++++++**????%%%?%??????????????????????????SS%????%%%%%SSSSSS##SSSSSSS%??*+**++++++;;:;;;;;;;;;;;;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::;;++****************************+;+;**********+++*************?????????????????????????%%%%S#S??%%%SSSS###SSSSSSS%??*+++;++++;:;;;;:;;;;;;;;;;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;+******************************;;;*******************++++;;;+++++***????????????????????%%%%%%%%%SS#####SSSSS%%%?*+;::::;;;;;;;;++;;;;;;;;;;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;+*******************************++;*******************+++;;;;;;;;;++++++*******************?*?????%%%?SSSSSSS%%%?*+;;;:,,::;;;+**+++;;;;;;;;;;;;;;;;;
,,,,,,,,,,,,,,,,,,:::;;;;;:::::::,,,,,,,,,,,,::::;+*********************************;;**********+++;;;;+++;;;:::::::;;++++++++;;+++++++++++;;;;+*****+;:+%SSSSS%%??**+;;;:,,,:::;+*%?**?;;;;;;;;;;;;;;;;
,,,,,,,,,,,,::::;;;+++++++++;;;;:::::::::::::::;;+*******************************+++;:+*****+++;;::::::;;;;::::::::::;;;+;;;;;;;;;;;;;++;;;;;;;;****+;:;+?%%%%%???***;;;:,,,:::::;+?SS%%*+;;;;;;;;;;;;;;
,,,,,,,,::::;;;++++++++++++++++;;;;;;;:::::::;;++*****************************++++++;;+++;;;;;:::::::::::::::::::::::;;;;;;;::::::::;;;;;;;;;;;;+++;::;+*?%%%????***+;;;:;;++++;;++?SSSS%**;;;;;;;;;;;;;
,,,:::::;;;;;+++++++++++++++++++;;;;;;;;;;;;+++**??*********+++++++++++++++++++++++++;;;;;;:::::::::::::::::::::::;;;;+++;;:::::::::::;;;;;;;;;;++;:,:++*?????******+;;;*****????***SSSSS?%?;;;;;;;;;;;;
::::;;;;;;;++++++++++++++++++++++;;;:::;;;;;;++****++++++;;;;;;;;;;;;;;;;;;;++++++++;:;;;;;::::::::;;;;;;:::::::;;++***++;;;:::::::::::;;;;;;;;;+;;,,:++????********+;;*****??%SSS%*SSSSS%?S+;;;;;;;;;;;
;;;+;;;;;;++++++++++++++++++++++;;::::::::::;;;;;;;;;;;;;;:::::::::::::::;;;;;;;;+++;:+++;;;;;;;+++++++;;;::::;;++******+++;;::::::::;;;;;;;;++++;:,,:+************++;+?????%SSSS##?SSSSSS?S%;;;;;;;;;;;
;++;;;;;;+++++++++++;;+++++**++;;;::::,,,::::::::::;;;;;;;:::::::::::::::;;:::;;;;+++:+*****++++++++++++++;;;;++++********++;;;::;;;;;+++++++++++:,,:;+***********+*+;*???%%SS#####%%#SSSS%SS*;;;;;;;;;;
;;;;;;;+++++++++++++++++****+++;;;;::::::::::::;;;;;;;++++;;;:::::::::::;;;;;;;;;;+*+:;*****++++++++++++++++++++************++++;+++++*****++++++:,:;++******??******?%%%%SSS#SSS##%?SSS##SSS%*;;;;;;;;;
;;;;;;;++++++++++++++++++*++;;;;;;::::::::::;;;;;;;;++++++;;:::::::::::::;;;;;;;;++*+:;++++;;;;;;+++******************????*****++*************++;,:;+++*****??*********?%%SSSSSSS##%?%#S##SSSS%+;;;;++++
;;;;;+++******++++;;;::::::::::::::::::,,:::;;;;;:::::::::::,,,,,,,,,,,,,,,::::;;;++;;:;::::::::;;++*************???*********++++*********++++++::+*+++*****?*****+;;;+*?%%SSSSSS#S%?%#S##SSSSS*;;;+++++
+;;;+++*??????**+;;:::,,,,,,,,,::::::,,,,,,,,,,::,,,,,:::,,,,,,,,,,,,,,,,,,,,:::::::::,,,:,,::::;;+********???????**++;;;;;;;;;;;;;;;+++****++++;+*+++****????***+;:;;+*??%%SSSS##S%?S#S##SSSSS?;;+++***
++++++*???????**+;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::,,,::,,,:::;;++*?????********++;;;::::::::::::::::;;++******+***++****?????*+;:::;;+*??%%%SSS###%%##SS#S#SS%?+++***??
*++++++**?******+;;:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::,,,:;;;,,::;;++**?????***+++;;::::,,,,,,,,,,,,,,,,:::;++*???%?***++****??????*;:::;;++**??%SSS##@#SS##SS#SS#S??***???%%
?**++++*********++;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::,,,:::::;;++***??????**+++;::,,,,,,,,,,,,,,,,,,,::::;+*??%SS****+******????*;::::;;+;*??%%SS###@#S####S#SS#%?????%%%%%
??**++******+++++;;:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:,,,,,,,,,,,:::::::::;;;;++++****???***+++;::,,,,,,,,,,:::::::::::::;;+**%S?***++*****?????+::::;;;++*??%SSSS##@######SSSSS%????%%%%%%
??**++++++++;;;;:::,,,,,,,,,,,,,,,,,,,...,,,,,,,,,,,,,,,,,,::::;;;;:::,,,,,,,:::::::::;;;;+++++++*******++++;;::::::::::;;;;::::::::::;;++**?***+++*****?????;::::;;;+*+?%SSS###@#########S#S%????%%%%%%
?***+++;;;;::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::;;;+++****+;;::::::::;;;;;;;;;,:;+++++++++;;;;;;:;;;;;;;;+++++++++;;;;:::;::;;;;+++****+*+*****?*??*;;;;;;;+***%%SS###@@@########S#S%????%%%%%%
++++++;;;;:,,,,,,,,,,,,,,,,:::::,,,,,,,,,,,,:::;;;;;+++***************+++++++++**+++++:,:+++++++++;;;;:::;::::::;:;********+++;;;;;;;;:;++******+++****??*??;;;:::;;+**??%SS#S#@@@####S##SSSS%????????%%
;;+++++;;;:,,,,,,,,,,,,,::;:;**+;;:::::::;;+++*****?*?????*???******??*???*???????****;::********++;;;;:;::::::::;:;++*****+++;;;;;;;+++**??***+*++****??*?*;;:::;;++*?%%S####@@@@@####S#SSSS%????%%?%%%
++++++*++++;::,,,,,,,,::;;;;*%%??**++++**????????????***??*????*??????????*???????????*:+???????****+++++;;;;;;;;;+:;;++;;++;;+;::++++*+*******+;+*****??*?*::::;;+**?%%SSS##@@##@@######SSSS%??*????%%%
**?**?*????*+;;:::::::::;;;+*******+*++*++*++++++++++++;++******+***?******************:;******************+++++++++:,;;;;;;;;;;;++++*********++++++*****++;:::;;+**??%S##S###@##@@@####SSSS%%??*???????
+***??*?****+;:::::::::::::::::::::::::::::::::::::::::::::;;:;::;++;+++;;;;;+;++++++++::;++++++++++******+*??**++++;;;;:;;,:;+;;++++*******++;;;;;;+++++;:,::;++**?%%SS##S#@##@@@@@@###SSSS%%??*%??????
;+*****+++;;::::::::::::::::::::::,,,,,,,,,,,,,,,,,,,:,,,,,:::,,:;:;;++;;;;;;;;;;;;;;;;;:;++++++++*++****++*??**+;;;;;;::;::++;;++++**;+*?%+++++******+;:,::;+++**%%%?S#########@@@@@####SSS%%??*?%%%%??
;+****+++;;::::::::;;;;;;;;;;::::::::::,,,,,,,,,,,,,,,,,,,,::,,:::;;++++++;;;;;::::::;;::;*+;;;;++*+++**++;;??**+;;++;;;::+;++;+*;:******?**+*******;:::;;++***?%SSSS%###########@@@@####SSS%%%?+?%%%%??
++*****+;*++++++++*****???****+++++++;:;;::,,,,,,,::::::;;;;;:,;;+++***+;+;;:::::::,::::,,::::,,:::;;++;+**:*%%*+++;+*;;;;++***??*+*;+*;++++*****+:,::;+**???%%SSS#SS###S#########@@@@###SSS%%%?+???????
***?????*?+????%%?%%%%%???*??????*+?*++*+;;:::,,,,:;;+++++++;;,:+++++++;:::::::::,,,,,,,:,,::,,:,,:::;;+++:;*???*:+++*+;+*+**?????*+*%?**+++***;:::;++*?%%%%SSSSSSSS###S#########@#######SSSS%?%*???????
++****????*??%???*********++;;*++*;++++++;;;:::::::;;;;;;:;;::,:;;;;;::::::,::,,,,,,,::;;,;;::;;::::;::;+;++?%?*?*;**;::+%????%?*+;;+**:+***+;:::;+*??%SSSSSSS%%%SS##SSS#################SSSSS%%*?%?????
;;++++++*********++++++;;+;;:;++++;;;;;;;;;;::;;+;;::::::,,:,,,,::::::,::::,,,,,::,:;+;:,:+;::::++::;;;:::;*???*??;;;:;+*?%***?*+;+?******;:::;++*?%SSSSSSSS%%%SS#####SS##################SSSS%%*?%?%?%%
;;;;;+++**+++++;;++++++;;;;;:::;;;;;;;;;;;;;::+++;;::::::::,,,,,,:::::::,,,,,,:::;:;;;::+;::;++;:::;;;;:::::;+??*;;+*?%%??*+;;++;+;+++*;;::;++*?%SS##SSSSS%%SS###S#@@#####################SSSSS%??%?%%%%
+++*****?****+;;:::;++;;;;;::::::;;+;++;+:;;;++++;;;;;;;;;::::::,,:::::,,,,:;+;;;:;**++?+;;*?++;;;+*;:;+;:;;:::;;;+**?%???*;;*?*+*+++;:::+**?%%S###SSSSSSSS#####S?#@########S############SSSSSSS??%%%%%S
??%%%?%S%%%?**++;;+:+++++;:;:::::;;;;;+;;;:;;:::;;;;;:;;;;;;;::;:::,,,,:::;;;+;+?;+*+;+%?+;*+++******;**+;+;;;::;+?%?*+;;++*+**+++;:::;+*?%%SS#SSSS%SSSS####SS%%?*S@##@@@@###@@@@@@@@@###SSSS%SSS%%%SSSS
?*%?%??%??****;++;;;++;;;;;;;::::::::::::::::::::::::::::::::::::::::::++**+**++??**+*?S%*?%+*?%?*?%S?*?*****+;;:::++++++**++++;::;;**??%SSSS%SS%SSSS####S%%?????*%@@@@@@@@@@@@@@@@@@##@@#SSS%%SS%%%SSSS
+;+++++++;;;;;;;;;;:;:::::;::::::::::,,,,,,,::::::,:::::::,,,,,,,:::::+***?*+?%??%%??%?**%SS?%SSS?%%%S????*?%*++++::+**++*+;;:;;+*?*?%%SSSSSSSSS######S%??***?????%@@@@@@@@@@@@@@@@@@@@@@@##SS%%SS%%%%%%
;;;;;;;;;;;;;;;::::,,::::::::::::::::::::::::::::::::;::::,,,,,,,,,:;?%*******%?%%%S#S???%SSS%S#S?%%S#S%SSSS%%?*++;;++++;;;;+*??%%%S%%SSSSSSSS#####S%?***++*?%????%#@@@@@@@@@@@@@@@@@@@@#@#SSS%%SSS%????
;;;;+;;;;;;;++;;;;;:::;;::;::;;;;;;;;;;;;;;;:::;;;;;;;:;;;::::::::;;?%%??%S%S%%?%SS%S####S##SS##SSS###SS####%S%?**+;;:;;+*?%%%S%%SSSSSS######S%%???**?%%%?%SSS%??%%#@@@@@@@@@@@@@@@@@@@##@@#SSS%%SS%**?%
+********+**+++;;;;;;;:::;;;::;;;;;;;;;;;;;;+;;:;;;;;;+;+++;;+++;+++?????%?%%?%SS##%?S##SS#S%S@##S%*++;;;;;;;;:::::;+*??%SSSSSS%SSSS#####SS%?**++*++*???%S##S%%??S%S@@@@@@@@@@@@@@@@@@@##@@@#SSS%SSS??%S
*******+****++++;;;;;;::;;:::::;;;;;;;;;;::;+;;;;;::++++++++;+++++++?%%%?*??%S#S%SSSS#####S%S#S?+;:;++++++;;:::;+**?%S%S%?SSSSSS####S%%%?**+++++++*?%%SS#SSSSSS??S%S@@@@@@@@@@@@@@@@@#%#@@@@###SSSSS%%SS
***********+;;+++;;;;;:::;:::::;;::::;;:::;;;;;;++;;;;*+++++++++++++?%%%%%SS#SSSS####S#@@#S#S*;;*??%%%S???*?***??%%SSSSSSSSSS##S%??*++*?**+++*++**%%S##SSS#S#S?*%%%%@@@@@##S#@@@@@@@@#%#@@@@@##SSSSS%%%%
+++++++++++++;;;;;;;;;;;;;;::::;;::::;;;;;;;;;;;;;;;;;+;;;;++++;;;+;+%%%SS###SS###@@SSS#SS##%?%%SSSS%%%*??????%%%SSS#SS#####%?**+*;;*?%?*+++++**?%SS##S####S%???%#S%#S#######@@@@@@@##%#@@@@@@#SSSSSS%??
+++++;++++++;;;;;;;;;;;;;;;;:::;;;::::;;;;;;;;;;;;;;;;;;;;;+++;;;;+++*?%SS##SS#####SS#S#S##%%S###?*+**?????*%SSS##S+?SS%#%?*++**+?++%%?*++++*???%SSSSSSS%%???**?S#S%SS#@@@@@@@@@#@@@@@@@@@@@@@#SSSSSS?**
++++++++++;;;;;;;;;;+++;;;;;;;;;;;;;;;;;;;;;;;++++;+++*++++*+********+;*??SSSSSSSSSS#######%???*++**??%%SSS%SS####S?%S%**++*****+***?**+;++++;;;+****????????*+?S##S###@@@@@@@@@@@@@@@@@@@@@@@##SSSSS???
***+****++++;;;;;++++++;+;+++;+;++;;;+++;+;++++++++++************+*++*++****?????%S######S%?****?%SSS%SSSS##SS##SS##S%**?*?*+++++++;;;;;+***+++++++*?%SSSSSSSS%%###SS#@@@@@@@@@@@@#@@@@@@@@@@@#S%S#SS%%%
************+++++++++++++++++++++++++++++*+++*+*************++***+;++*****??%%%SS#@@#####SSSSS#####%%%SS#%#####SS##S%?**+**+++++++*******????%%????***%SS############@#@@@@@@@@@@##@@@@@@@@@@@#S%%S#S%%%
????*???????*******++++++++;+++++*+++*+***+++*++*+++********++*+**+*****??S@S%S#S@@@@@@@@@#@@@@@@@#%S##S####S%##S%%%?*???%*????%?????????????%%SS%%%%%%%SSS####@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#SSSS##%??
????????????????***+++++++++++++++++**********+*+**********+************%%%#@##@#@#@@@###S%%S###@@@@@@@#@@@@##@##%%###SSSS%?*?%%S#SSSSS%%%%%%%%%%?%%%%%%###@@##@@@@@##@@@@@@@@@@@@@@@@@@@@@@@#SSSSSSS%??
?????????%??????****************+*****************???????????????+++***?%%?%#@#@##@##S%%%%%%#######@@#@@@@@@@@@#@##@@##@@SS%SSS######@@@#######SSS#####@@@@@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@#S######%%%%
????????????????************????**???????*????????????????%??%?***?%S%%%%%S%S@#@@#@#SS%?%SS#######@####@@#@@@@@@@@@@#S#@@###@@@@@@@@@@@@@@@@##@@@@@@@##@@@@@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@#S####S%%%%%%
????%%%%%%%????????****?*??????***?????????????????????????**?????%SSS%S#SS%S###@#@#%%####S##S######@#@@##@@@@@@@@@@##@@@@##@##@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@####S%%%%%%%%
?%%%%%?%%%%%%%%%%%????????????????????????%?????%%%%%?%%%%%%%%?%S%%S%%S####S##SS@##%%S######@##@@@#@@@@@@@@@@#@@@@@@@##@@#S#@@@@#@@@@#@@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@@##SS%SS%%%%%%SS
%%%%%%%%%%%%%%%%%%%???????%%%%%%%%%%??%%%%%%%%%%%%%%%%S%%%%%%S%SSSSS%####S###S%S@@S%S@#S######@@@@@@@@@@@@@@@@@@@@@@@@@@@##@@@##@@@@@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@###S%%%%SS%%SSSSSS
%%%SSSSSSS%%%%%%%%%SS%%%%%%%%%%%%%%%%%%%%%%%%S%%%%%%SSSSSSSSSSSSSSSS#@##SS##@###@#SS###########@@@@@@@@@@@@#@@@##@@@@@@@@##@@@#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#SSSSSSSSS#SSSSSS%SS
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS%%%%%%%%%SSSSSSSSSSSSSSSSSSSSSS##SS#@@#######@@@@SSSS#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##SSSSSSSSS#S##SSSSSSSS
########SSSSSSSSSSSSSSSSSSSSSSSSSS%SSSSSSSSSSSSSSSSSSSSSSSSSSSS###@@@@##@@@#@@@@#SS##@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##S######SSSSSS#SSS#####
########SSSSS####S##SS####S##########S##SSSSSS#SS##########S###S#@@@@@@@@@@##@@#####@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#SS######SSSSSSSS########
###################################################################@@@@@@@@@@@@#####@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###########################
#####################################################@@@@@@###@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@####@#######@#@#@@@@@@@@@@@@@
################################@####@#######@##@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@
######################@#######???S##S??%##S???#S??%#@@#%??S@@@@S???%@@S?????????%@@@@S?????????%@#???#@@@%??%@@S???????%@@@@@@SSSSSSSS#@#SSS#@@@SSS#@@@@@#SSSS#@@@SSS#@@#SSS#@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@#@@@###@@###@@#######@@###@#:..+@@;..:#@+..;@*..,#@@#,..?@@@#:....%@+.,.......;@@@@?.........,#S...%@@@:..;@@*.......,#@@@@@;:::::::*@S:::S@@@;::?@@@%+::::::?@#;::?@S;::?@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*..:@%....%@:..?@?..,S@@S,..?@@@*..*,.:@###%...?###@@@@###S,..*###@S...?@##;..;@@*..,SSSS#@@@@@@;::*SSSS#@S:::S@@@;::?@@?:::?SS%%#@#;::??::+S@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@S,.,#+.;:.+#,.,#@?...,,,,...?@@S,.;@+..*@@@S...%@@@@@@@@@@@:..*@@@@S...,,,,,..;@@*...,,,:S@@@@@@;::+????@@S:::S@@@+::?@S:::%@@@@@@@#;::;::;#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@;..?,.%*.,?..+@@?..,++++,..?@@;..:*;..,S@@S...%@@@@@@@@@@@:..*@@@@S...;+++,..;@@*..,+***#@@@@@@;:::;;;+#@S:::S@@@;::?@S:::%@@@@@@@#;:::;::+#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*..:.,#S..,..%@@?..,#@@#,..?@?..,;;;:..;@@S...%@@@@@@@@@@@:..*@@@@S...%@@@;..;@@*..,%%%%%#@@@@@;::*@@@@@@#;::*##%:::S@@+::;%##S%#@#;::+#?::;S@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#,,..+@@;..,:#@@?.,,#@@#,,.?#:,,?@@@%,,,%@S,,,%@@@@@@@@@@@:..*@@@@S,,,%@@@;,.+@@?.,,....,S@@@@@;::*@@@@@@@S+::::::;%@@@#?;::::::*@#;::%@@%:::?@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#S###@@#SSS#@@@#SSS@@@@SSS##SSS@@@@@SSS#@@SSS#@@@@@@@@@@@#SS#@@@@@SSS#@@@#SS#@@#SSSSSSSS@@@@@@S%%S@@@@@@@@@#%%%%S@@@@@@@@S%%%%#@@@SSS#@@@#SSS@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@?**%@@@@%****%#@@@@@#**********#@?**%@@@%**?@@S***#@@@S?*+*?S#@@@@@@@@#%?*+*?S@@@?**%@@@S**?#***S@@@?**%@@@@@?***??%S@@@@@@@S?*+*?S@@@@#***S@@?**?@@@%**%@@@@@S?***?S@@@S*+;;+?@@@@@@@@@@
@@@@@@@@@@@@@@@:..+@@%:..,,,.+#@@@@S,,,....,,,S@,..*@@@+..:@@%...S@#+,.,:,.,%@@@@@@#*,..,,,.;#@@:..+@@@*..:@*..:#@?..,S@@@@@:...,,.,:%@@@%:..,,,.,:%@@S...%@@:...+@@+..;@@@?:..,,,.,%@@?:;+:..+@@@@@@@@@
@@@@@@@@@@@@@@@:..+@@;..:%##S@@@@@@@@@@;..;###@#:..+###+..:@@%..,S@S...+S#S#@@@@@@@;..:%#@#S#@@@:..+@@@*..:@@+..+S,.,S@@@@@@:..+@#*,.,%@S,..*#@#+..,S@S,..%@@:.,,.+@*..;@@?..,?#@@S#@@@@@@#;..*@@@@@@@@@
@@@@@@@@@@@@@@@:..+@@S;,..,;*%@@@@@@@@@;..;@@@@#:...,.,...:@@%..,S@@*,...:;?#@@@@@S...%@S;;;;*@@:..+@@@?..:@@@+.,:.,%@@@@@@@:..+@@@:..+@*..,#@@@#,..?@S,..%@@:.,*,.*?..;@@:..+@@;;;;+@@@@?,.:S@@@@@@@@@@
@@@@@@@@@@@@@@@:..+@@@@#%*;...?@@@@@@@@;..;@@@@#:..;?**:..:@@%..,S@@@#S?+:..:#@@@@S,..*@#+:..;@@;..+@@@*..;@@@@;..,%@@@@@@@@:..+@@S,..*@?..,S@@@S,..%@S,..%@@:..%%,.;,.;@@:..;@@+;..,#@@@*++#@@@@@@@@@@@
@@@@@@@@@@@@@@@:..+@@%;+?%?,..*@@@@@@@@;..;@@@@@:..*@@@+..:@@%...S@#+;*%%+..,#@@@@@*,..+?%+..;@@?..,*%*,..?@@@@?..,#@@@@@@@@:..;?*:..;#@#;..:?%*,..;@@S...%@@:..?@%,...;@@%,..;?%?,.,#@@#;:;S@@@@@@@@@@@
@@@@@@@@@@@@@@@;,,+@@*:,...,;?@@@@@@@@@+,,+@@@@@:,,*@@@+,,;@@%,,,S@S;:,..,:+S@@@@@@@S+:,..,,;%@@@%;,...,;%@@@@@?,,:#@@@@@@@#:,,,,,:+?#@@@@?;,...,;?@@@S,,,%@@;,,?@@?,,,;@@@#*;,...,:*@@@S,.,%@@@@@@@@@@@
@@@@@@@@@@@@@@@###@@@@@#####@@@@@@@@@@@@###@@@@@###@@@@@###@@@###@@@@@#SS##@@@@@@@@@@@@#SS##@@@@@@@#SSS#@@@@@@@####@@@@@@@@@######@@@@@@@@@@#SSS#@@@@@@###@@@###@@@@####@@@@@@##S##@@@@@@@##@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/
Compilation message
mecho.cpp: In function 'void setIO(std::string)':
mecho.cpp:143:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
143 | freopen((s+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:144:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
144 | freopen((s+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3676 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3420 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3580 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 7 |
Runtime error |
146 ms |
65536 KB |
Execution killed with signal 9 |
| 8 |
Correct |
3 ms |
3420 KB |
Output is correct |
| 9 |
Correct |
2 ms |
3428 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3428 KB |
Output is correct |
| 11 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
3540 KB |
Output isn't correct |
| 13 |
Runtime error |
193 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
142 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 16 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 17 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 18 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 19 |
Correct |
2 ms |
3484 KB |
Output is correct |
| 20 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 21 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 22 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 23 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 24 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 25 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 26 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 27 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 28 |
Correct |
2 ms |
3564 KB |
Output is correct |
| 29 |
Correct |
3 ms |
3416 KB |
Output is correct |
| 30 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 31 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 32 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 33 |
Correct |
5 ms |
3932 KB |
Output is correct |
| 34 |
Correct |
4 ms |
3928 KB |
Output is correct |
| 35 |
Runtime error |
122 ms |
65536 KB |
Execution killed with signal 9 |
| 36 |
Correct |
4 ms |
3888 KB |
Output is correct |
| 37 |
Correct |
4 ms |
3932 KB |
Output is correct |
| 38 |
Runtime error |
149 ms |
65536 KB |
Execution killed with signal 9 |
| 39 |
Incorrect |
6 ms |
3932 KB |
Output isn't correct |
| 40 |
Correct |
6 ms |
4072 KB |
Output is correct |
| 41 |
Runtime error |
133 ms |
65536 KB |
Execution killed with signal 9 |
| 42 |
Incorrect |
6 ms |
4188 KB |
Output isn't correct |
| 43 |
Correct |
6 ms |
4188 KB |
Output is correct |
| 44 |
Runtime error |
134 ms |
65536 KB |
Execution killed with signal 9 |
| 45 |
Incorrect |
7 ms |
4184 KB |
Output isn't correct |
| 46 |
Correct |
6 ms |
4188 KB |
Output is correct |
| 47 |
Runtime error |
125 ms |
65536 KB |
Execution killed with signal 9 |
| 48 |
Incorrect |
10 ms |
4184 KB |
Output isn't correct |
| 49 |
Correct |
8 ms |
4188 KB |
Output is correct |
| 50 |
Runtime error |
159 ms |
65536 KB |
Execution killed with signal 9 |
| 51 |
Incorrect |
9 ms |
4316 KB |
Output isn't correct |
| 52 |
Incorrect |
8 ms |
4520 KB |
Output isn't correct |
| 53 |
Runtime error |
137 ms |
65536 KB |
Execution killed with signal 9 |
| 54 |
Incorrect |
9 ms |
4444 KB |
Output isn't correct |
| 55 |
Incorrect |
10 ms |
4444 KB |
Output isn't correct |
| 56 |
Runtime error |
126 ms |
65536 KB |
Execution killed with signal 9 |
| 57 |
Incorrect |
11 ms |
4696 KB |
Output isn't correct |
| 58 |
Incorrect |
10 ms |
4700 KB |
Output isn't correct |
| 59 |
Runtime error |
135 ms |
65536 KB |
Execution killed with signal 9 |
| 60 |
Incorrect |
13 ms |
4696 KB |
Output isn't correct |
| 61 |
Incorrect |
12 ms |
4828 KB |
Output isn't correct |
| 62 |
Runtime error |
133 ms |
65536 KB |
Execution killed with signal 9 |
| 63 |
Correct |
70 ms |
4736 KB |
Output is correct |
| 64 |
Correct |
107 ms |
4700 KB |
Output is correct |
| 65 |
Correct |
101 ms |
4832 KB |
Output is correct |
| 66 |
Correct |
76 ms |
4696 KB |
Output is correct |
| 67 |
Correct |
71 ms |
4696 KB |
Output is correct |
| 68 |
Correct |
34 ms |
4764 KB |
Output is correct |
| 69 |
Correct |
26 ms |
4756 KB |
Output is correct |
| 70 |
Correct |
33 ms |
4692 KB |
Output is correct |
| 71 |
Correct |
29 ms |
4700 KB |
Output is correct |
| 72 |
Incorrect |
24 ms |
4752 KB |
Output isn't correct |
| 73 |
Runtime error |
152 ms |
65536 KB |
Execution killed with signal 9 |
| 74 |
Runtime error |
120 ms |
65536 KB |
Execution killed with signal 9 |
| 75 |
Runtime error |
134 ms |
65536 KB |
Execution killed with signal 9 |
| 76 |
Runtime error |
147 ms |
65536 KB |
Execution killed with signal 9 |
| 77 |
Runtime error |
154 ms |
65536 KB |
Execution killed with signal 9 |
| 78 |
Runtime error |
138 ms |
65536 KB |
Execution killed with signal 9 |
| 79 |
Runtime error |
137 ms |
65536 KB |
Execution killed with signal 9 |
| 80 |
Runtime error |
126 ms |
65536 KB |
Execution killed with signal 9 |
| 81 |
Runtime error |
127 ms |
65536 KB |
Execution killed with signal 9 |
| 82 |
Runtime error |
130 ms |
65536 KB |
Execution killed with signal 9 |
| 83 |
Runtime error |
171 ms |
65536 KB |
Execution killed with signal 9 |
| 84 |
Runtime error |
152 ms |
65536 KB |
Execution killed with signal 9 |
| 85 |
Runtime error |
160 ms |
65536 KB |
Execution killed with signal 9 |
| 86 |
Runtime error |
147 ms |
65536 KB |
Execution killed with signal 9 |
| 87 |
Runtime error |
142 ms |
65536 KB |
Execution killed with signal 9 |
| 88 |
Runtime error |
130 ms |
65536 KB |
Execution killed with signal 9 |
| 89 |
Runtime error |
159 ms |
65536 KB |
Execution killed with signal 9 |
| 90 |
Runtime error |
128 ms |
65536 KB |
Execution killed with signal 9 |
| 91 |
Runtime error |
136 ms |
65536 KB |
Execution killed with signal 9 |
| 92 |
Runtime error |
153 ms |
65536 KB |
Execution killed with signal 9 |
