답안 #1078839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1078839 2024-08-28T07:00:16 Z coolsentenceidontremember Mecho (IOI09_mecho) C++17
100 / 100
138 ms 4504 KB
#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 = 805;
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' && grid[x][y] != 'D');
}

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 (inside(curX, curY) && bee[curX][curY] == -1){
				bee[curX][curY] = bee[x][y] + s;
				q.push({curX, curY});
			}
		}
	}
}


bool valid(const int &minute){
	if (minute * s >= bee[startX][startY]) return false;
	memset(vis, 0, sizeof vis);
	queue<pair<pair<int, int>, int>> qq;
	qq.push({{startX, startY}, minute*s});
	vis[startX][startY] = true;
	while (!qq.empty()){
		auto p = qq.front();
		qq.pop();
		int x = p.ff.ff, y = p.ff.ss, curS = p.ss;
		for (int i = 0; i < 4; i++){
			int nx = x + dx[i], ny = y + dy[i];
			if (inside(nx, ny) && !vis[nx][ny] && ((curS+1)<bee[nx][ny])){
				vis[nx][ny] = 1;
				qq.push({{nx, ny}, curS+1});
			}
		}
	}
	for (int i = 0; i < 4; i++){
		int x = homeX - dx[i], y = homeY - dy[i];
		if (inside(x, y) && vis[x][y]) return true;
	}
	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 = 0, r = n*n;
	while (l<=r){
	//	cout << l << ' ' << r << '\n';
		int m = (l+r)/2;
		if (valid(m)) l = m+1;
		else r = m-1;
		
	}
	cout << l-1;
}














/*
                         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);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 45 ms 4188 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 1 ms 3420 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 1 ms 3420 KB Output is correct
12 Correct 2 ms 3676 KB Output is correct
13 Correct 2 ms 3672 KB Output is correct
14 Correct 2 ms 3676 KB Output is correct
15 Correct 2 ms 3420 KB Output is correct
16 Correct 2 ms 3420 KB Output is correct
17 Correct 2 ms 3420 KB Output is correct
18 Correct 2 ms 3420 KB Output is correct
19 Correct 2 ms 3420 KB Output is correct
20 Correct 1 ms 3420 KB Output is correct
21 Correct 1 ms 3420 KB Output is correct
22 Correct 2 ms 3420 KB Output is correct
23 Correct 1 ms 3676 KB Output is correct
24 Correct 1 ms 3676 KB Output is correct
25 Correct 1 ms 3676 KB Output is correct
26 Correct 2 ms 3676 KB Output is correct
27 Correct 2 ms 3676 KB Output is correct
28 Correct 2 ms 3676 KB Output is correct
29 Correct 2 ms 3676 KB Output is correct
30 Correct 2 ms 3676 KB Output is correct
31 Correct 3 ms 3676 KB Output is correct
32 Correct 2 ms 3676 KB Output is correct
33 Correct 4 ms 3792 KB Output is correct
34 Correct 5 ms 3676 KB Output is correct
35 Correct 19 ms 3904 KB Output is correct
36 Correct 5 ms 3932 KB Output is correct
37 Correct 5 ms 3932 KB Output is correct
38 Correct 20 ms 3960 KB Output is correct
39 Correct 7 ms 3932 KB Output is correct
40 Correct 6 ms 3928 KB Output is correct
41 Correct 22 ms 3932 KB Output is correct
42 Correct 7 ms 3932 KB Output is correct
43 Correct 6 ms 3932 KB Output is correct
44 Correct 35 ms 4036 KB Output is correct
45 Correct 7 ms 3932 KB Output is correct
46 Correct 7 ms 3928 KB Output is correct
47 Correct 48 ms 4052 KB Output is correct
48 Correct 9 ms 3928 KB Output is correct
49 Correct 8 ms 3932 KB Output is correct
50 Correct 33 ms 3932 KB Output is correct
51 Correct 11 ms 3932 KB Output is correct
52 Correct 10 ms 3932 KB Output is correct
53 Correct 41 ms 3932 KB Output is correct
54 Correct 10 ms 3928 KB Output is correct
55 Correct 11 ms 3932 KB Output is correct
56 Correct 47 ms 4172 KB Output is correct
57 Correct 12 ms 4184 KB Output is correct
58 Correct 12 ms 4188 KB Output is correct
59 Correct 54 ms 4216 KB Output is correct
60 Correct 23 ms 4188 KB Output is correct
61 Correct 16 ms 4184 KB Output is correct
62 Correct 60 ms 4188 KB Output is correct
63 Correct 71 ms 4184 KB Output is correct
64 Correct 138 ms 4184 KB Output is correct
65 Correct 99 ms 4180 KB Output is correct
66 Correct 80 ms 4188 KB Output is correct
67 Correct 92 ms 4432 KB Output is correct
68 Correct 31 ms 4180 KB Output is correct
69 Correct 43 ms 4188 KB Output is correct
70 Correct 25 ms 4188 KB Output is correct
71 Correct 31 ms 4172 KB Output is correct
72 Correct 23 ms 4168 KB Output is correct
73 Correct 24 ms 4396 KB Output is correct
74 Correct 43 ms 4504 KB Output is correct
75 Correct 41 ms 4440 KB Output is correct
76 Correct 43 ms 4420 KB Output is correct
77 Correct 32 ms 4440 KB Output is correct
78 Correct 50 ms 4444 KB Output is correct
79 Correct 27 ms 4440 KB Output is correct
80 Correct 45 ms 4500 KB Output is correct
81 Correct 42 ms 4444 KB Output is correct
82 Correct 34 ms 4388 KB Output is correct
83 Correct 71 ms 4436 KB Output is correct
84 Correct 41 ms 4444 KB Output is correct
85 Correct 40 ms 4432 KB Output is correct
86 Correct 45 ms 4356 KB Output is correct
87 Correct 43 ms 4444 KB Output is correct
88 Correct 44 ms 4188 KB Output is correct
89 Correct 48 ms 4440 KB Output is correct
90 Correct 43 ms 4188 KB Output is correct
91 Correct 44 ms 4184 KB Output is correct
92 Correct 52 ms 4188 KB Output is correct