Submission #1084938

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1084938	2024-09-07T08:47:27 Z	coolsentenceidontremember	Park (BOI16_park)	C++17	100 / 100	301 ms	41916 KB

park

/*


;;;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;;;:::::::::::::::::::::;;;;;;;;;;:::::::::::::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++
::::::::::::::::;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*****%*:::
*/


#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'
#define pii pair<int, int>
#define mp make_pair
using namespace std;

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);
	}
}

struct Tree {
	ll x, y, r;
};

struct Edge {
 int u, v;
 ll w;
 Edge(int uu, int vv, ll ww) : u(uu), v(vv), w(ww){
 	
 }	
 bool operator < (const Edge &other){
 	return w < other.w;
 }
};



ll dist(ll x1, ll y1, ll x2, ll y2, ll r1, ll r2){
	return (ll)(sqrt(1LL*(x1-x2)*(x1-x2) + 1LL*(y1-y2)*(y1-y2)) - r1 - r2);
}

int pre[4] = {3, 0, 1, 2};

vector<Edge> edge;

struct DSU{
	vector<int> e;
	DSU(int n): e(n, -1){
		
	}
	int find(int x){
		return (e[x] < 0 ? x : e[x]= find(e[x]));
	}
	bool unite(int x, int y){
		x = find(x);
		y = find(y);
		if (x == y) return 0;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return 1;
	}
};

int main(){
	setIO();
    int n, m;
    cin >> n >> m;
    int w, h;
    cin >> w >> h;
    vector<Tree> tree(n);
    for (int i = 0; i < n;i++){
    	cin >> tree[i].x >> tree[i].y >> tree[i].r;
    	edge.push_back(Edge(0, i+4, dist(tree[i].x, 0, tree[i].x, tree[i].y, tree[i].r, 0)));
    	edge.push_back(Edge(1, i+4, dist(w, tree[i].y, tree[i].x, tree[i].y, tree[i].r, 0)));
    	edge.push_back(Edge(2, i+4, dist(tree[i].x, h, tree[i].x, tree[i].y, tree[i].r, 0)));
    	edge.push_back(Edge(3, i+4, dist(0, tree[i].y, tree[i].x, tree[i].y, tree[i].r, 0)));
    	for (int j = 0; j < i; j++){
    		edge.push_back(Edge(j+4, i+4, dist(tree[j].x, tree[j].y, tree[i].x, tree[i].y, tree[j].r, tree[i].r)));
		}
	}
	sort(edge.begin(), edge.end());
	vector<pair<ll, pii>> guest;
	for (int i = 0; i < m; i++){
		ll r;
		int e;
		cin >> r >> e;
		guest.push_back(mp(r*2, mp(--e, i)));
	}
	sort(guest.begin(), guest.end());
	vector<vector<bool>> ok(m, vector<bool>(4, true));
	int p = 0;
	DSU dsu(n+4);
	for (const Edge &e : edge){
		while (p < m && guest[p].ff <= e.w){
			int cur_entr = guest[p].ss.ff;
			int idx = guest[p].ss.ss;
			bool conn[4][4];
			for (int i = 0; i < 4; i++){
				conn[i][i] = true;
				for (int j = i+1; j < 4; j++){
					conn[i][j] = (dsu.find(i) == dsu.find(j));
					conn[j][i] = conn[i][j];
				}
			}
			if (cur_entr == 0){
				if (conn[0][1]) ok[idx][1] = false;
				if (conn[0][2]) ok[idx][1] = ok[idx][2] = false;
				if (conn[0][3]) ok[idx][1] = ok[idx][2] = ok[idx][3] = false;
				if (conn[1][2]) ok[idx][2] = false;
				if (conn[1][3]) ok[idx][2] = ok[idx][3] = false;
				if (conn[2][3]) ok[idx][3] = false;
			} else if (cur_entr == 1){
				if (conn[0][1]) ok[idx][0] = ok[idx][2] = ok[idx][3] = false;
				if (conn[0][2]) ok[idx][0] = ok[idx][3] = false;
				if (conn[0][3]) ok[idx][0] = false;
				if (conn[1][2]) ok[idx][2] = false;
				if (conn[1][3]) ok[idx][2] = ok[idx][3] = false;
				if (conn[2][3]) ok[idx][3] = false;
			} else if (cur_entr == 2){
				if (conn[0][1]) ok[idx][1] = false;
				if (conn[0][2]) ok[idx][3] = ok[idx][0] = false;
				if (conn[0][3]) ok[idx][0] = 0;
				if (conn[1][2]) ok[idx][3] = ok[idx][0] = ok[idx][1] = 0;
				if (conn[1][3]) ok[idx][0] = ok[idx][1] = 0;
				if (conn[2][3]) ok[idx][3] = 0;
			} else {
				assert(cur_entr == 3);
				if (conn[0][1]) ok[idx][1] = 0;
				if (conn[0][2]) ok[idx][1] = ok[idx][2] = 0;
				if (conn[0][3]) ok[idx][0] = 0;
				if (conn[1][2]) ok[idx][2] = 0;
				if (conn[1][3]) ok[idx][0] = ok[idx][1] = 0;
				if (conn[2][3]) ok[idx][0] = ok[idx][1] = ok[idx][2] = 0;
			}
			p++;
			if (p >= m) break;
		}
		dsu.unite(e.u, e.v);
	}
	for (int i = 0; i < m; i++){
		for (int j = 0; j < 4; j++) if (ok[i][j]) cout << j+1;
		cout << '\n';
	}
    
}

Compilation message

park.cpp: In function 'void setIO(std::string)':
park.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);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.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);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	256 ms	33460 KB	Output is correct
2	Correct	265 ms	33444 KB	Output is correct
3	Correct	251 ms	33460 KB	Output is correct
4	Correct	269 ms	33460 KB	Output is correct
5	Correct	254 ms	33472 KB	Output is correct
6	Correct	263 ms	33340 KB	Output is correct
7	Correct	248 ms	33468 KB	Output is correct
8	Correct	245 ms	33460 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	9664 KB	Output is correct
2	Correct	46 ms	10696 KB	Output is correct
3	Correct	39 ms	10576 KB	Output is correct
4	Correct	40 ms	10840 KB	Output is correct
5	Correct	42 ms	10572 KB	Output is correct
6	Correct	41 ms	10828 KB	Output is correct
7	Correct	37 ms	10436 KB	Output is correct
8	Correct	38 ms	10440 KB	Output is correct

Subtask #3

42.0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	256 ms	33460 KB	Output is correct
2	Correct	265 ms	33444 KB	Output is correct
3	Correct	251 ms	33460 KB	Output is correct
4	Correct	269 ms	33460 KB	Output is correct
5	Correct	254 ms	33472 KB	Output is correct
6	Correct	263 ms	33340 KB	Output is correct
7	Correct	248 ms	33468 KB	Output is correct
8	Correct	245 ms	33460 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	40 ms	9664 KB	Output is correct
12	Correct	46 ms	10696 KB	Output is correct
13	Correct	39 ms	10576 KB	Output is correct
14	Correct	40 ms	10840 KB	Output is correct
15	Correct	42 ms	10572 KB	Output is correct
16	Correct	41 ms	10828 KB	Output is correct
17	Correct	37 ms	10436 KB	Output is correct
18	Correct	38 ms	10440 KB	Output is correct
19	Correct	301 ms	41756 KB	Output is correct
20	Correct	296 ms	41916 KB	Output is correct
21	Correct	299 ms	41844 KB	Output is correct
22	Correct	298 ms	41844 KB	Output is correct
23	Correct	289 ms	41752 KB	Output is correct
24	Correct	289 ms	41844 KB	Output is correct