Submission #1067709

#TimeUsernameProblemLanguageResultExecution timeMemory
1067709coolsentenceidontrememberSailing Race (CEOI12_race)C++17
45 / 100
790 ms4780 KiB
#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%?*+;;;;+*?%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##@@@@@@@##@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ ;;;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;;;:::::::::::::::::::::;;;;;;;;;;:::::::::::::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++ ::::::::::::::::;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); } } const int N = 501; bool adj[N][N]; int dp[N][N][2], dp1[N][N][2], nx[N][2]; void calc(int u, int v, int dir){ if (adj[u][v]){ dp[u][v][dir] = 1; dp1[u][v][dir] = 1+dp1[v][nx[u][dir]][dir^1]; } else { dp[u][v][dir] = dp1[u][v][dir] = -N; } for (int k = nx[u][dir]; k != v; k = nx[k][dir]){ dp[u][v][dir] = max(dp[u][v][dir], dp[u][k][dir] + dp[k][v][dir]); dp1[u][v][dir] = max(dp1[u][v][dir], dp[u][k][dir] + dp1[k][v][dir]); } dp1[u][v][dir] = max(dp1[u][v][dir], dp1[u][nx[v][dir^1]][dir]); } int main(){ setIO(); int n, cross; cin >> n >> cross; memset(adj, 0, sizeof adj); for (int i = 0; i < n; i++){ int x; for (;;){ cin >> x; if (!x) break; adj[i][--x] = 1; } nx[i][0] = (i+1)%n; nx[i][1] = (i+n-1)%n; } for (int len = 1; len < n; len++){ for (int i = 0, j = (i+len)%n; i < n; i++, j = nx[j][0]){ calc(i, j, 0); calc(j, i, 1); } } pair<int, int> ans = {0, -1}; for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ for (int k = 0; k < 2; k++){ ans = max(ans, make_pair(dp1[i][j][k], i+1)); } } } if (cross){ for (int b = 0; b < n; b++){ for (int c = 0; c < n; c++){ for (int dir = 0; dir < 2; dir++){ int a = nx[c][dir]; while (a!=b && !adj[a][b]) a = nx[a][dir]; if (a == b) continue; for (int d = nx[a][dir]; d != b; d=nx[d][dir]){ int tmp = max(dp1[d][nx[a][dir]][dir^1], dp1[d][nx[b][dir^1]][dir]); ans = max(ans, make_pair(2+tmp+dp[b][c][dir], a+1)); } } } } } cout << ans.ff << '\n' << ans.ss; }

Compilation message (stderr)

race.cpp: In function 'void setIO(std::string)':
race.cpp:265:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  265 |  freopen((s+".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:266:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  266 |  freopen((s+".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...