Submission #1094773

#TimeUsernameProblemLanguageResultExecution timeMemory
1094773shmaxGift Exchange (JOI24_ho_t4)C++17
Compilation error
0 ms0 KiB
/* ~??: :!?J???????????????! .????????~ !?!~?^~!:7:?!~7?. .????????^ .:^^^^^:...............::................::::::............:.. .... .YYY: .^7JYYYYYYYYYY?!: ~YYYYYYYYJ??: :J7^Y?~Y!~J! .7?JYYYYYYYYJ .::^^^~~^.................::^~~^:::...........:::^^^^:::::.......... ..:. .YYYJ. .. .::^^^^:.. .7JJYYJYYYYY7~?^ .?. !! .?!!JYYYYYYYYY?~ .:^:::^^~~..................^~7!^:.................:::::^^::............. ..:. .:. ~YYYY~ ~77: .~~~:. :7JYY?~^^JYYYJ?JJ!!?J??YYYY!^~!!~^:. .:::::^^~~!~::::^:::..........:!^................::^::::::::::::........ .... ..:. YYJ!. .!YYJJY? .. ...?YYYYY!. .!JYYJY?. .JYYJYYYYYYYYYYJJYY: .:::::^^^~^^^^^^^^:...........:~~~:...::::..........:^!??7~^:............. . .... ..:.. YYYYY??JYYYYYY?.......JYJYYYYYYYY?...7YYYYJJYYJYYYYJJJJYYYYYJJYYY!................................^^^:::^^^^^^^^^^::..............::...::........::......:::^~7?7~.............. ........ .^^:................................................................................................... JJJJYYYYJJYJYY!......:YYYYJJJJJYYY^.:YYYYJYYYYYYY~7YYYYYJ?JYYYYJ~...............................^~~^^^^:::^^^^^^......^^^:...............::::.....::::::::^^::.:^7?~............. ....::. . .^~:.................................................................................................... YYYYYYYYYYYYY7........!YYYYYYYJJYY~.^YYJJJYYYYYY!..:~7~:..:~7!^... ........................:!7!~^^::::^^^^^^.....^!!^....................:~^::....:::^^^^^:::...:!?^....... ..... .::.::.. .. .:^:.................................................................................................... ^:~JY!:~^.~?~..........:!?JYYYYYYY^.:YYYYYYYY?!:................. .....................:!7!!^^::::^^^^~~.. .:!J?^.............:........::^~^:..::::::::^^:......:!!:..... ..^^. :~.:^:. ... .^^:................................................................................................... .^ ..............:^~!7?J?:..?J?7!~^:................ ... ...............^!!~!~^:::::^^^~!^. .!YJ~......::.......:.....:::::::^^:...::....::^::......^7~. ..^!: .!::^:...... .^^:.................................................................................................. : . .^!7????7~^:...........:^~7?????~......... . .: ........... :77!!7~^^^:::^^~!7^.. .JP7....:.:^:.......::.....:::::::::~::.........:^:........~!. .:7!:.7^:^^...::. :~^:................................................................................................ .:.. . !YYYYYYYYYYYJ?^.....:?JJYYYYYY7:. .. . .. .. ..............~7777?~^^^^^^^^!77^...:?5~......:^:........::......:::::..:^!::..........:^:.......^7: ....!J~:?~:^^...:^.. .^^:............................................................................................... ::. .:: :YYYYYJJYYJYY7..:^:..7YYJYYYJY? .. ... . .. ............:777777~~~^^^^^~7??~...:?J:......:^:.........^..............::^7::..........:^:.......:7^ ......^?77J!^~~:..:~... ^~^:............................................................................................. : . ..!YYJYJYJYYJ~..!JYJ!:.~JYYYJYJ?~... : ... .. ...........~?7?7!7~~~~~~^^~7??7...:JJ.::.....^!..........~...............~.~!.:...........:^.... .7~ .......^??7J7~!!...~~... ^~^:............................................................................................ :. .:. ...?YYYYYYYJ!:.^JYYYYYJ~.:!JYY7. .:. .: .....:..^77~~.....:!77J7!?~~!^~~^^!??J?:...JJ:^!......~~..........~:..............!:.?^.:...........:^. ..!~ ........^??7?77?!..:7~... :~^:........................................................................................... :.. . ..^!7???!^:..!YYYYJYYYY7..:^77. ...... ...:!JJ7JYYYY:...:77?J!!?~~!~^!~^~????!...JY:~7!:..:..!~..........^~............. ~~ :Y............. .:. ......!~ .........^??77777~..!?^.....:~^:.......................................................................................... ............~YYYYYJYYYYY~...... . .. .. .....~JYYY!!7?YJ?!^77JJ!!J!^!7~!!^~?????:..75^^777:.^..^!~.........::7............. ^J. 77....... .. .:.::.....7: ..........!7777!!7^.~?7:......~^:......................................................................................... .... ...............!YJYJYYYJJYY7.......... .........!JJ7:.:?YYYJ77JY!!J?^~7!~!~~?????7:.^P!^7!7?..~..!!!....::...^.!^.............:5: .5:..... .....:^^^....:7. .........:!77!!!!7::?7~..:.:..~::........................................................................................ ...............:^:...:^^...?YYYYJJYYY?:........................~JYYY??JJY!77?5Y!!?J~^~777!~7J????!~.5?^77777.^~.:7!!^...^....~:.7.........:....5~. ?Y..:.............^~!^....:! ..........^7!!~!!!~:7~!:.:::: .~^:....................................................................................... .~~:^7~......:~!YYYJ!?YYY7~:.^7!:.:~7^...........................^77~!YYJJ7~?P5!!?Y7^^~7?7~!J?77777^75~!777?7.7~.^7!!!:::!....^~.^!:......:~....P?..:P~.:7^.....:..:...~!?~^...~^ ..........~~~~^~!!^!^~^..^~!. :~::...................................................................................... :YYYYYYYJ:... !YYJ?!~7!~?JYY7........:.........::......... . .....:~:~~?P5!!75J^^~~7?7!?J777777^P?!77!!?7:?^.^7!!!~^~7..^.:^^:!7:.....^!:..:GJ:..JY:.!Y^...:^^::~...!??~^...7.........:.:!^~~.^77!^:!..^!7: :^::..................................................................................... :?Y7!??!7YJ777!~JJ^~!~~~!!^?Y~.....::!YY?~....~?YY7::...... . . .......^~?P5!!!Y5!^^~!7?77Y?77777!?P777!!777^J^.~7!!!~~7?..7:.^:!^!~.....!7:..~GY:..~G!:.JY:...~!!7~~..:???7~..^7 ^.......:.!~^~~.:77^.!:.^7?~ ^^:..................................................................................... J77~^7!~~!~7YYYYY~!7^. .^7!^JYJ^..:YYY!~~.~..~.~~!YYY^... . .. ....:~75Y!~~75J^^^~~7?7YY777777!5Y?7!!!77?!J~.~7!!!~~7?^:?~.::.?~~.....!?^..7GY~::.PJ!^:5J:..^7!7J7^..~J??7!..!::!..:...:.^7^^!^.:!!:^^.!J?! ^^:.................................................................................... !:7!~^^^!7~^JYJYY?^!!^:^!!^?YYJ^...77:::!77?7777:::!?.... . ... ....~!57!~~!Y5~^^~~~??75?777!77!5J?!!!!7!??J~.~7!!!!!!?7~??:.~.~J~^...:77~..JGY!^~.?B!?^!P?:.:7!~??~..:?J7777::7.7!:.~...:.?~^^!:.:7~:^:77?7. . :::................................................................................... :!7~: .^~7^^JYYYY?7~~7~~77JYY!......:!?77~^^~77?7:.......... .......~~Y~~~^^7P?^^^~~~?7J5!~!!!7!75?77!!!7!7JJ~.~?!!!!!7YJ77?!.^:^7?~^:.:77!:.PGY7^J.:PY~?^YY7^:^!!!Y7^.:~5?7777:!::7!^!7^.~:^?~~!!..~7::!?~!7. . ^^:.................................................................................. !~7!~:::~!!^JY7:::^YJJYJJY~:::...:^..!?7!: .!7?7:.^:................^^J~:~^^^?5~^^~~~~?75Y~~!!!7~?J777!!7777??~.!Y~!!!!75Y7777^.^~!~~7^:~777~!BPJ?^P:.7Y7!7~G?!~~!!~~Y!::^?P!?!!7!!.!~!7??77!:77:^7^..7!~7!.^7: :...^^:................................................................................. J^~!!!!!~~!~JYJ. ..~J?!7?^.::..:7YJ.:7?7!. .!7??:.JY?:.............:^!!:~^^^~YJ^^^~~~~?7P?~~!!!7~J?777!!7777??~.!G!~!!!75Y!!7J7::7!!:!!!!!!!!PP5J?^B!.!!J!!!?G!~~~::.~Y~:~~55!?~!7J.~~~~~!7J?:!?!.^7^.:7!7::~7^. ~:.: ^^^................................................................................ YYYJ^!77^?YYYYY:.^...^.::.~??~.:7YY~.~7?7!^:.^~7??~.^YY7:.............~^!.~~^^^~5!^^~~~~~7?G7~~~!!7~J?7777777!7J?!.!B7~~!!!YJ!!7J!~.!7!~^.?Y7!!?BJ577^BJ.~~~7~!!P5~~^....7J^~~!G??7^~J7:~^~~~~7J^^?7!.:!~.!7?.^7^!..?~ ^^ :~^:.............................................................................. !YYYYJ!7YYYY!:^::..::^. .^.:^...^JYY~.^~!J7??7?7~^.~YYY^.............^^~.:~^^^^75~^^~~~~~!?G!~~~!!!~J77777!7777YJ~.~G7~~!!!5?!!JJ!!^:7!!^^77JYJPP!57!~Y5:^~:~~~!7BJ~^:...:?7~~~YG!Y~^~J.~^^~~~~?~:?77~..7!!?7.^Y:!:^J^ ?! :~^:............................................................................. :~~^....^^^..^. :~7?!~ ::.......:^^:.. ^.~^:!.^ .:^::....~?~!!....:^^:.~~^^^^YY^^^^~~~!!?P~~~~!!!!J77?77777775J~.^P!~~!!75?!!5?!!!:^7!~7?!!!YBPJY7!~!J~^~.:^^^~?GJ~^:::.:7~~~!G7??^^J:^~^~~~~7~:~?77:..7YJ?:~Y::!?J:. .Y?..~^:............................................................................ ...........:::.:~~^. :^..............77?!~?!7..........~JJ7JJ^...~^:.:!^^^^~P?^^^^~~~!!J5~~~~~!!757?777777775?!.^P!!~~!7P7!7P7!!!~:~7757!!^PP?YP5?!~!!^~..:^^^^?5?^::::.^~~~~YY~Y~^7!:~^~~~~!^::?77!::.?P5:~J..?J?:.. ~7Y~.^^^........................................................................... .............^. .:.::...............:?J77JJ^..........^!?J77^..^^:.:^!^^^^!P7^^^^~~~!!Y5~~~~~~!?57?77777777P?!.^5~~~~!J5!!YP!!!!!~:~J5!~.?#7!!7?JJ!~7!^. .^^^:!7?^::...^~~~!Y!7?^^J:~~~~~~~^:.7777^:~:YG:!?..?J7... .~^Y?.:~^:......................................................................... ..............::::........................:..............::.....~:..:~~^^^^?P!^^^^^~~!!5Y^~~~~~!?P7?77?77777P?~.^Y^^!~!YJ~!GJ~~~!~!~.77^.^GJ!!!!7!!~:!7!....^~~!!?YY7!!~~^7!!!Y?!?!^?~~~~~~~~^..~?77!.!7~G7?!..7?!.... ^^^?5~.^~:........................................................................ ...............................................................^^:.::~~^^^~?5!^^^^^~~!!PY^~~~~~!JP??77J7777?P7~.^?:.^!!57~?B7~~~~~!!?::.:55!!!!!7!!^.:!J?!~^^^:7!^~!7~::^^^?!!???J7~7Y7~~~~~^^..:J777^.!JYGP^..7?!......!^:~YJ::~^:...................................................................... ...............................................................~^:.::!^^^^~7P!^^^^^^^!!GJ^~~~~~~JG?7!?J7777?5!^.~7:..^J5~~5P~~~~~~!YG:..?P7!!!!!!7!^..^^^.. .:7!:^^~~::::~7^~!~!~!!GY~~^~^^^...J7!77^:~5PP^..7!7^.:.. :^^::757::~:..................................................................... ..............................................................^^^ :^!^^^^~7P!^^^^^^^!7GJ^~~^~~~?G??7Y?777!JY~^.~~....!?^?G?~^^^~~JB!.:^~!!7!!!!~7!^ .::. ..!!^^::^^:::~7^7^~!^7GP!~^~::^...J?7~!7~^!PG!::7:7!.^:...:^^^:^JY~:^~:................................................................... ..............................................................~^: ..:!^^^^~?P7^^^^^^~!7GJ^^~^^~~?GJ?75777!!YY~:.~:... ^~7P5~^^^^~?GJ.:~??::!!~~!!7?^ .^: .~~^^:.:^::.~7!!:!!~GG~~^^..:.. ?J!~:^7!~?GY!~?.~?:^^....:^^^::~JJ^:^^:................................................................. ..........................:::::............................ .~^:::.^~^^^^~JP7^^^^^^!!7G5~^~^^~~7BY7JP777!!5?~^^!!!~:.!!7Y7^^^^^7G5::77?J?!^~~~~!~Y7 . .^. .:^:~^.:~~::~?7.:!^YB~~^^..... 7Y!~^.:?YJYP??7.:?~~^!....:^^^:::~JJ~:^^................................................................ .........................^: : .:.:........................ :~^....^~^^^^7YP?~^^^^^!!7GP~~~^^^~!GP?Y5777!JP?7^^~:...~!:.7^^^^:7P5^:J??!!YY!^~~~~~!5. .: ...::::^^^~^^^~^:^J7.:~~G^~^^..... ~5!^^::.^YPGJJ~.:^?!.?^....:^^^::::^?J!^^^:............................................................. ........................::. .. :^........................ ~~^..:.^~^^^^JYGJ~^^^^^!!7PP!~~~^^~~PG?557??7Y?:::~:. :~. :~^:::!5Y~~5?7!~!!YY^:^~^^^J^ .::^::^~7JY5PPGGGP5YJ7~7^.:~J^~^^..... ^5?~^^^!:.7GPJ::~:?~.~?. ...:^::^:::.:7?7~~^:........................................................... ................ ...:::. ...~............................!!~^::.~!^^^^YYGJ^~~^^^!?7PG7~~~^^~~JBJPP?7~!?~::^!. .: .~^:::JY!!?57!!!~~~!YY:.:~~^^~. :^!YGB####BBBB##B#&#B#P?!^~7^~^^.... ^5?7~^:^J!:?GJ.^7:?~..?7.....^^::^:::..:!?7!!~:......................................................... ................ .....:::::::...........................:7!~:...^!^~^~5YGY^~~~^^~??PGJ~~~^^!~!G5P57!~7!^:^7~ ^^::^^^7JJ77~~~!!~~~~JJ...^~^^: .!PBGY?5P55PGB#&B: :#&P!JGGGPY~~^^... :5J?7^^::YJ!55.77:?~..~J7.....:^..::::....~7?77~:....................................................... ................................. . .....................~7~!..:.~7~~~!PJBY^^~~^^~?J5G5~~~~^~!~5GP57~~!~::!7. ^::::. ^7!7!~~~~^~~~~~~??. .:^^^. .!PJ~::YBGGBB#&&&B^.7&&&5:^5GGP5?~:. .5Y???^::^JPJ5^J!^?^:..?J!.....::..:^:::....:!???7~:.................................................... ................................. . .....................7!^!^.:.~?!!~7GJB5^^~~~^~?55PP!~~~^:7~7BP57~!~^:~7: ...~^~~^..^^. .^!~^^^^^^~~^^!!.. .:^^..: .:^#&&&#BBBG#PPB&&&&&!:^PPY?J7~:.. .Y5????~^~7PG5YY~J?:^..^JJ!......::.:^:::......~7???!^.................................................. ........................ ......... . ......................?~:7^.::^?!7~J5Y#P^^!~~^~?5GPGJ^~~~^^7~5GP7~^^:^~~.::^~^!!^^^^^^. .:^:..:^^^^^^^^.. .:^. .^^B&&&BG5PBB#PP#BB#&~.:55~!^:.. ?5J?777!~7YGGBYJ57.^:..!JJ!......::.:^:::.......^!???7~:............................................... ...................... ...............................J^.!^.::^?7?!??PGG!^7~~~^?YGPG5~~~~^:!77G57~^^^^~!JPB#BG##B#BBB5^. .:. ..:^^^^^^:. .:: . ~&###Y7YBBGJJBBG#B. ^^:!:... .. !5J?^!!~77?YGGYY5J.~^...7JJ!.......:::^^:::........^7???!^:............................................ .................... .. . ...............................:J:.^~..:^??J77!GYPJ^Y!~!^?YBGPG!~!~~^^?7JP~:^^~JB&#B#BBBBGB#Y:!#&Y^ .. .::^^^:.. .. J#BG57!~!~!75PBB^ .::!. .. ... ^5YJ^:77^!JJYG5P?J:!!....?JJ7...:^..:::^^:::.........:~7??7~:.......................................... ...................... ................... . .....:J:.:!..:^??YJ!!B?YP^Y?!!~!YGGPGJ^!~^^^^??J^~!Y#&#J~PPPGG##&#! :#&B!. ..:::. ?B57:.....^?P5^ .:^~ :. ....:5YY!::?Y~~J5PGY~J:~!....:JJJ?:..:!^..:^^^^^^...........:!7??7~:....................................... ...................... ............. ........ . .. ..:J..:~^.:^?JYJ~JB?J5!?Y77!!YPGGGP~!7~^^^^?77~?##G~:^####&&###BPB#&&P. ... ~57:....:7J!... ..!^ .^. ::.::5YJ?^..75?~JGG!!J:^~.:...^YJJJ^...!?^..:^^^^^:............^!7J?7^:.................................... .................................... . .... . .. ..:J..:.^::^!JYJ^PP?JYJ~P7?7!YPPPGG7~?!^^^^^7!!GBB7:::5&&&##GP5G#BB#G#^ .~^^^^^^^::... .:!. .~. .^:.!^YY??7:..!YY~JP^J7:^7.:....~YJJJ~...~J7:.:^^^^^:..............^!7J?!^.................................. .................................. .. . .... ....:J:.:. ^^^^YYJ?GJ?JJY~5Y7?!?GP55BY~7?~~^^^:!7YGB7:::^P&#GGB?JG#BY5G#! ... ............ ..~^. :~...^:.J^YYJ??7^:.^J5~?!5^:~7:.:....!YJJY7...:JJ~..:^^^^:................:!??7~:............................... ................................. .. . ........ .......?:.:. ^~^:JYYP5?JJJY7!G???7PGPYGG~!J7~~^^:^?~!?J^^^. ~BBPPY77!^:^?P~ .................. ..!.. ^~...~:.5~?YJ?77?!:.:JY!5?.:!!::::..::!PJ?YJ^. .7J!^:.:^^^:..................:!??7~:............................ .................................... . ................?:..::^^:^?5GG5JJYYYJ~YG?J?YGPY5G?~YJ7~^^^:^7~^:... ~PP57.....!5^ .................. ..^....!~...~:.5~^YJJ?!7J?~::JJG~.~?!::^:::::.?G??J57. .^?!~^:.:^^:....................^!??7~:......................... .................................... ........:^::~.......!^..::^:..~5GG5JYYYJJ?^PPJJJGG55PY~?P?!^^^^.^7~!: ^7?~::^~~^... ................. ..^ . :7^...!^.Y7.JJJJ!~7JY?77PY::7!7:~7:::::^.PGJ7?YY^. .!!^^^:.::::.....................:!??7~:...................... .............................................~::~. ^^.^^. ^~..^^^.:::5BGYYYYJ?J?~7BPYJYG5555~!P57~^^^^.~!^7^. ....^^::......... .............. .: . ~7^:..!^.JJ.7JJJ?~^^75YJ5P^J!J?^~5~::::^:^GG5?7J57. .:~^::::.:::.......................:~7?!^:................... ............................................^^ ... .~...:7..:^:.::?BBPYYYY?J?77!JGPYJPP555!~YG?!~^^^^.~^^7^.. ................... .. ....... .: ..77^:.:!~.?Y.~JJJJ7^~!!5Y5P5!!5?:~PY::::^^.7GGPJ77YY^. .^~^::^:.::.........................:~77!^................. .............................................~: ^: .^^....?..^^..:~PGBPYYYJ??77?G!YPPYYP55P7~?B57~^^^~~.^^~~:...................... . ..:Y7^:.:7~:?5::JJJJJ~:!?7YPP7.~Y7:^5P7::^^^:.5PPG57!?Y?:...:^::^^:.::..........................:~77~:.............. ............................................^~ .. .. .!... !::^:.:^JGBPGYYY???77PG57Y5P55P55?^!GP?7~^^^!~.^^^~..................... . ..~57^:.:7!:?Y!.7JJJJJ^:~J?5P^.7Y!^~Y55^:^:^^.^GPPGPJ!!?Y~....:^^^^^::::...........................:~77~:........... .............................................:::~: ~^::.....:~:^..:!YGPY55YJ?77!JG5P57?Y5P555J^~PP?7!~^^~7!.~^^~. ................. . .:.J57^^.:77^?JJ.~J??JJJ~:^J5P!:YJ~!7JYPY:::^^^.7GPPPP5?!!??:....^^^^^::.:::...........................:~7!^......... .................................................::::.........~^: .^!PBJ5YYYJ77!7PP555Y??JY5GPJ~~5PJ!7~^^^!J!.!^^!: .............. . :7.:PY?^^::7?!??5^:J????JJ!::JGY7P7!J!JY5P?:::^^:.YP55555Y7!!?!.....^^^^::..:::............................:~7!:...... ............................................................. ^!..~~YGP75YYJ?7!!YP555YJJJJJJ5GY~~Y5?!J!~^^~75~.7~:^: . !J!.7GJ?~^::?J?J7Y7.7????J7?!^:YGGJ?YJ!YJJ5P!.::^^.:PP5555Y5J7!!!:.....^^^:::..:::.............................^77~:... ..............................................................^~ ^^?G577PYJJ7!!?P555YJJJJJJJY55!~Y5?!Y7~^^^!?P^:YJ??^ .. .. :???^:5PJJ~^^:?JYJ7?J.~????J!~77~!PP?YJ!5YJJJ5P~.::^:.!GP5J55YY5J7!!^.....:^^^::...::::............................:~77^. ..................................:?J?^~^....................:^:^^!PJ7!?PYJ?7!!Y555YJJJJJJ??J5Y!~J5?!?Y~~^^~7JG^:YJJY~ .. .7J7??:7GYJJ!^^^?J5J77Y~:?777J?^!~!JJ5JJ7J5YYJ?YPP^..:::.?GPPJJ5YJJYJ7!~:... ..^^^:....::::.............................:!7 ................................:7?JJJJYJ^...................^^^^~5?^?~JPY??7!?555YJJJYJ????Y5Y!^?5?7!57~~^^7?P5~^5J?Y7. :!??7777:YPJJ?7^~~JJ5J7!J?:7777?J~:7!^?YY!5J5JYYJ?YP5:..:::.YPPPY?JYJ?JYJ7!~:... ..^^:......:^:.............................. ................................:?J?JJJJ?:..................:^~^^J7:!7~YP5?7775555J?JY??????YYJ!^?577~JY~~~^~7JY?^^5?7JJ^ :^!7777!7!^5Y7J??~^~JYYJ7!7J:~?777J7^:7J!YJJ5Y5JJYY??YGY....:.:5PP55J7JYJ?JJJ7!~.... .:^:.....::^:............................ ..................................~JY7!?!...................^!:^7!::?~~YP5?77?555J?JY?????7JYJ?7^7P77~757~~^^77Y!?~^YJ??Y?^. .:^::~!77!!?^75?7J??!~~?PYJ7!!J~:?!!!7?!^:!JY?5Y5YJJ?YY??YGJ....:.:5PP5YY77JJ???JJ?7~.... .:^:.....::^:.......................... ....................................:......................:~:^!~::^7~~JP5??7Y55Y??YJ??7777JY?77^!57!~~JJ!~~^!7?77?!^YJ7YJ??7~:. .:^::::.~!!!!!7:J57!?J77~~7G5J7!!??:?!!!!7?7!^~YY5JPJJJ??YY??5G7......:5P5YJ5?!7?J?7??7?7~:... .:^^.....:::......................... ...........................................................^:^!~:::~!^~JP5JJJ5YYJ?JJ?77777?JJ77?~~Y7!!^7J!7~^~7!?777!~YJJJ777777!!^:.. .:^:::::...^!~~~~~~YJ7!7J7?~~7YGJ!!!7J^?!!!!!!!77!?5?YJJJJJ7?YY??5G!......:5P5YJYY7!7??777!!7?~.... .:^::....:::....................... .........................................................:::~!^:::.J~^~?P55YYYYY?JY?777777?J?!!?~~J?!!^!?777~~!!77!!!!7YYJ777!!!!777!!!~^::.. ..:^:::::.......Y5YJ?~!?J!~!???!!!!G5!!!!Y~J!~!!!7?JY5P5555GGGP5JJ5Y??5P~......:55YY?J5J!!7??777~~7?~.... .:^:.....::..................... ........................................................:::~!^:::.7J^^^7PPP55YY?JJJ7777!!7?J!!!7!^??~~~~7?~?7~!7!?!!~~!7YJ?!!!!!!!!!!!!!!77!!!:::.... ..::^::::::.........7GGGG~77J!^~!7??7~~7P7!!!Y7J!!7?Y5GGBB#BB##BBBG5JJYP5J?5P^......:55JY?75P?!!7?77?!^^!7^..... .:::.....:.................... .......................................................:.^!!^:::.~J?^^^7PPPPYYJ?JJ7!!!!!!7JJ!!!77^?J~~~^!?!!J7!7!7!~~~!!!JJ?7~~!!!!~~~!!!!!~!?::::::^^::^^:::::::............:PGG5:??J7!!!!7??~~~JJ~!~JJY7?JJYPGBB###G##B##BG5J?5GG5J5P^.:....:Y5??77YGY7!!77777~::~7^..... .:::.....:.................. .....................................................:..~!!^^^^:~7?7^^^!PPPPYJ?JJ?!!!!!!!?5!!~!!7^7J~~~^~!7~?J??7!7~~~~~!!!7J7!~~~~~~~!~~!7J5J:::::::::::::::.......... ......~GG5:??JJ!?~~77?7~~~Y!~!JJPPG5JJP####BGP5GBBBBB#BPY5BBBP55^.:....:YY7?7!JPGJ!!!777?7~::!7~..... ..::...................... ...................................................::.:!~~~:..:^~~J!^^^~5P5PYJ?J?7!!!!!~7YY~!~!!7~!J~^~^^~!~~JYJ?77~^~~~!!!~~7??!~~~^!!!7?5GBJ:::::::::::::......... .....!GY:?~?Y7Y!.^!??7~~!J!!JJGBBG5B#BBBBGPPYJPGBGP5PGBG5GBBYJ5^.:.....JY77!!?5GP?!!!7777!^:^~!~:.... .::....:............... ..................................................:..~7^^~~ .^:^~J!^^^~JGPPJJ???!!!~~~!7J7~~~!!!~^?!^^^^~~!~!YYJ?!7^^~~!~~~~^^~777~~~775BBBB!::::::::............ .....~7:77JY?Y^...!7?7~~!77YYBBBB##PGBBP5PP?7JYPBBGYJJ55YGPJ7J5^.:.....7Y!!!!?5PG57!!!7777~^:^^~~:.... .:::...:............. ...................................................:!!^.:~: .:^:~~??^^^^7PGPJ???7~~~~~~!77!~~~!!!~^7?^^^^^~~~~!J5J!7!^~^~~~^^^^^^~~!!7??YGBB?::::.............. ...:^:77?5Y7.....~7J?!~!JPJYPGBPJJGBPJJ5P?!7JYYPBGJJJ??YP5J7?Y^.^.....~J!!~~7Y5GPY!!!!777!~^:^^~^:.... .::::.::........... ...............................................:..^7~:::^~. .^.~~~?J~^^^~JGPJ???!~~~~~~7!7~!~~!~!^:~7!^^^^^^~^~~755?7~^^^^~^^^^^:...:JY??YY~................. .:^:!!!PY:......~7?J?!!J7^~~~^!Y55JJ??Y??!7JY7JYYYYY?7YGPJ77Y~:^:....^7!~~~7JYPP5J!!!!777!^^^^^:::..... ..::..:.......... ................................................:!7^::::~~ ^.^~~!J77^^^:7PBJ??7~~~~~~!7^!~~^~~~!^^^!!~^^^::^~^~~~?Y5J~^^~^^^:......:JJ!~~.................. :^^:^JYP!........~7~!??777~^^~YGGP7J?7?YJ?!7Y?!7YGGGGJ7YGPJ77J!:~:....:!!~~~7JYPPP5?!!!!!!!~^^^^...:..... ..::.::........ ............................................:..^!!^::^::~^ :::!~~??!Y!^^.~JBY77!~~~~~~7^^~~~^~~~~^^^^!~^^^^::^^^~~^^~Y57:.::. .......??~^~................ .^^^^:J5~?:.......:~J^.~??77!^^~7??7J?!!JJY?!JJ77~JBBG777JPPY7!J7^~~.....~!~~~!JYYP5PY!!!!!!~^^^^:.......... .:::^:...... ^. .............................................:~~~~::^:.^~::^.~~~777~?Y^^..75G77!^^^~~!!.!^~^~~~!^^^^:^7~^^^::::^^~~~^:^???::.........!7~^~:.... :^^^^7~!7.!!::::::^:!GP!..^7???7~^~7?7~^^^~~~~!7!7!~7P?777!JPP?!!J?~!7. ...~!~~~!JJ7555Y7!!!!~~^^^^:.......... .:^^:..... !^.:......................................... .^^^~~:.::..~~:^.^!~!7!!!~G7^^.:?GJ7!^^^~~7^^!^~^~~~^^^^:::~7!^.....:^^!~~~^.:!:^.........:?!^~:... .^^:^75J~?!:?^::::^^!~!YY~:...~7?J?YY!~~~~~~~~~~^^^^^^^^~7YYJ55Y77!?Y!7?: ...^!~~~!??^JJJJ!!!!!!~^:^^:........... .:~~^.... ^:.::........................................:~^^~^..^:...~^^.:7!!?7!!7:5P~^:.~?P7!^^^~~!:~~~~~~~:.......:~77~^:.:::^^7?!~~:..:::........~?~^~^ . .:^:^~?5Y^:7?!~?^::^^!BP7?!^~~:....^!7???7!!!~~~~~~~~^^^^^::~?PGG5?!7!?Y77J^....^!~~^!?7:7?7?~~!!!~~~^:^^:........... .::~!^.. ^..::.......................................~~:^~^..^:...:~~:.~7^!?!!!7~~G?~:..~?Y!~^~~7~:~~~^:::.....:::::^~!7!^:..:::!5J7!~^^~!~::::::::77^^^. . :^::~J5?::^^~777J^^^!GP~7?~~!!7YY~:...::~!7???77!!!~~~~~~!!!!!7?7JY!~7!?5?7J!... ^!~^~!?!.!7!7~^~!!~~!~::^^:........... .:.:!7^ ...:....................................:::!^:^~~..::....^!~.:?~^?!!!!!?:YJ!^...~??~^~~7^^~^....:..:::::::::^^:~77!~::::^J5?7777???!^::^~~!?7^^^. . .:::^!Y5!::::^^:^~7J~^5P!~?5J777JJ7~~~^:......::^^^~~~~~!!!!!!77~^::~7~~7!?5J7J7:.. :~~^~!7^ ~7~7?!^^!!~!!^.:^:.............:..:7 . ....................................::^~::^~~..::.....~!:.7!:!?!!!!?J^^Y~!:...~?7~~!!::.........::.....:::^^^^~!7??7!~^!???5J?77777~:.::~?7^^: .:. .^:::75Y^..:::::^^^^:7BP7~~!J!!!!~~^~~~~~~^^^^::........:::^^~~~^::....^^~7!75J!?J~....~~^~!!. ~!~75Y!^~!~~!~:.^^:............:. . ^^:...................................::~~.::~~:.::......~~ :7:.?!~!!7J^~:7?^!. .~!~~7^:......:...^.......::.:^^::^^~7?JY?!!7PB?7?7777!:.. .::^^^. :: ...::^^^?GY:.........:^::^!~~!~~J~~^::...:::::::::::::::^^^^^^^^^:::.........:~7!7Y?!7?7:. .^~^~!~. ^!~!5Y7~!7!~~!^..^:............:. !~:..................................:^!^.::^!:.::.......!..!^.~7~!!!J7.^~:?~^~. .^~^!:...........:............::..::::^~?J?!!??J5YYY?77^. .^:.... .::. . :^::^5B?..... ....7G~......^:........ ....^::::::..... ....:~!!7J7!~7?!:. :~^~!^..^~^!5Y!~!7?!~!~..:^:...........:. ^. ... .....:.:::................:^!:.:::~^..^:......:~ :~..7~~!!J?~.^^^:?~^~^. .:~~:.. ........................::^^^:^!!77JJ7~::^~^.. ..:::. ... .....:5G^ . ?G!...:.................. ..... ....:JG5P!......~^. ..:~!!!?!~~~!?!: .~^~!: .^~^!YY7~~!??!~!^ .^^:..........: :. .. :^... .^^::.............~!..::.~~..^:.......^:.^:.~!~!!J??::^^^^~?^:~!: .~!~:. ......... .............::!!^~!!~^^^^^:::... .^^::.. . :5J. ....^~: ........YB#PGG. ~55?. :~!~!7!~^^~!7!..~^~~. .^~^~!!!~~~7J7~!~. :^^.......... ~^^. :::: .^:^............!J..::.^~:.::........:..:..7~~~7?77.:^^^^^!?^:^!~. .:!!~:. .:. ............ ....~J:.^^^~!~^^^^::^..:^~!!~!~. ~57 .:... .... ..^7Y5? J55!.. .^7~~7~^^^^~7?~:^^~~. .^^:^^^~!!~~?J!~!: .:^:........ ?7^::.....:^:. .:::^...........75:.::.:~^.::....... .: .:.~~~~!?!7~.^^^^^~^!7^^^!~:. .^!!^:. .:. .... . .JY..:......::^^~77!!!^...^!~. .?5^ .:.. .......::^^^.. ^YY5: !557 ... ^7~~!~^^:^^~7?!!^~^ ..^::^^:^^~~~7J?!!^...^:....... ??77!^:::^~^:....::::::..........!P~.::..~~..::.. .... :.....!~~~?!!7:.^^^^~^^^~!^^~ .... .^~^^^:. .. ....... :PJ..^..........:~~~^^^:..:!7^. :JJ. .:.............. .:JY5! ^55J .... :!!~!~:^:^^^~77!~~: ..^..^^^^^:^~!?J7!~...:^:..... .~777!~^^^^::^::::::...........^57..^:.^~:.::. . .....:... ^~~~77~!7..^:^^~^:^~~~~: ... .^~:::^::: ...............~GJ.:^...........^^^:^^:::.^7~: ^5? .:....:::... ..... .:?55? :55Y ... .~~~!^::::^^^!7!~^. ..^..^^^^:::::!JJ!~:...^::... . ...::::........:::..........:5J:.::.:~~..^:... ... :: ...!~~!?~~!!.:^:^^^^:::~~7: ... .^~^..^~^. .....................^7. ... . :^:::..:::^7!:.7G~ ..:.::^~^.. ...::^!~:. ..?55J :YYY. ....^~7^^:::^^^~!!~^...:^..^^^^.::..:7J7!^...:^:.. !!^::::::.......:.::::.........?Y~.::..^~:.::........:?... ^!^~7!^!!!.::::^::::::~~~^:.. ..... .:~^..^^~^. ................. . ^?. .. ^^..: .::^7!!P: ...:::^^:. ...::::..... .. ..:?5YY. :YYY. ....^^^::::^^^~~~^...^:..^^^::^:...:7J!~...:^^. 777!~~^^^::::::.:::^:::.......:J7:.^:..~~.:^:.......^?7....~~~!7^~!!!.:::^^.:::::^7~!!!~~^^:.......:~^:..:!~:.............. .Y? .. .~^... ...:!?!^ .::::.. ......:::... ....... ....:75YY. ^BGY. .. .:::::^^^^~~^...^..:^^:.^:.....:!7!:...^^ ?77!!!~~^^^:::::^:::::........!7!.:^..^~:.::.......~!J~ . .!^~7~^~!7!.:::::.::.::~~^~!!!!~~^:.........^~^.:^~!^.......... .7?. .. .!:......!5!!!. .::......::^:...... ....::.. ......::?5YY. 7B#5 . .^^::^^^^^~^...^..:^^::^.......:~!^...^ J??7!!!~~^^^:^^^::::.........^7!^.::..~~..^:.....:~~7J^ . ^~^!!^^~!7!.:::::.::.::~..:^~~~~~~~~^:.......:^~~:.:~!^..... !5^ .. ~!.. .:JJ. .!: ..:..::::::......... ....::^^^^~:. .............::^Y55J :?! .. :^^::::::^~^..:^..^^::^:........^!~... YJ??77!!~^^^^^:::... ........^77::^:..~^.:^.....:~:~!J: ..!~~!^^^~~7~.::^::.::..:!: ..:^^:^!!!~~^:..:!:..:~!^:.~!: ~J. .. .. ^5! :^ ...:..... ...........:..:......::.. ..............::^~5557 . ^^^::::::^~^..^: :^^^^:.........:!~:. JJJ??7!~~^^^^::.............:^7!.^^..:~^.::....^^.:!!?.. .!^!~^^~~~~^.::^^:..:..^!!. .::....:^^!7??~.....^!7~::~^. .!... .7J. .^ .7Y: .........::::... ... ..:^^^^^^^^^~~!?JY5PGGY5^ . .^^:::::::^~^..~..^^^^^...........~!^ ?!!??!~^^^:.................^:?!:^^..:~:.::...^^..:!!7.. :!^!~^^~~~:^.:.^^:..:..~^:::......:.....^~7?!!!~:....^!7!^~!. :JP55Y7!: ~Y! :. ^5P^ .:::::::::.. ... ..:~~~~~~~~!!!777J#B####GYY. YJ^ . .^^:.:::::^~:.^^..^^^^:...........^! !!7!7~:^:..................:^:?!:::..^~:.::..~^...~!!7.. ^~~!^^~~~::~...^^:..:..~^..:~~......:.:^^~~....:^~^.. .^7?!!7: 757::?5?~?Y~..:??. :.:JBG?7: .... ........:::::::::....::::^!?BBB###G5! :P#5. . .^^:.:::::^^:.~:.:^^::............: 7~!!7?!^:..................:::?~:^:..^~..::.~:..:.7~!7...!~!~^^~~:::^...^^^.....~^^^...^^:....::::~... .:^:. .^!77?. ^P7 .7?~~Y5??: .:^YGGPYJJPB? .......:^^:.. ............^PBBB##BP: YGG~ . .:::.:::::^^::~..^^^::........... J7!~~7JJ^::................:::?~:^:..^~..:^~: .:.:7~!?. .!~7~^~~:::..:..^^~.....~~:......:::....^^.... .::... .^77. !5~ .~?JJPG7 .~YG#BGJ^...:!BG. .....:^::. .........^GBB#BBP:.. ^55Y .. .:::::::^::^^.:^^:::........... YY7~~~!77~^:...............:.:?!:^:..:~:.^^:..:: ~7~!?. .!~7^^!^:::..^..:^!....::........ .:^^^~~....... .... .!!: ^5J. ....~??JYBG!:^YB#BP?^. ^BG. .::::::. .......:.^GB#GP!....Y55! . ^^:::::~::^::^^^:::.......... 5YJ!~~~!7?7^:..............:..7!:^:..:^::^:..::..!!~!?. .!!7^!^:::...:..:^~^..:!.............:~7^... ..... ... ~!~ .^!?77!!7Y5!~~7P##B##5!. !GY .......:.!B#GY:.. ~5YY. . :^::^:^^.^^:^^^::::......... 555?!!!!!!?J555?~:.........:..~!:^:..:^^^^:.:.. .!~~!J. .!77!~^:^:...:...^~~...^~:..... ...:::~^...... ... .. :.^! .:..^!7~~~~!Y#G7^!BBPY!^:.. :55: ..........J#GJ....Y55! . :^^^:~^:^:^^^^:::......... 5P55J77777?J5G#B5YJ~::.....:..:!^^:...^^::::... :!~~!J: .~7?!^^:^:....:..^^~....^:... ..:.:^~.... . .. :! :~!~^:....:?G! :5B^^!7??Y555YYGG: .........:BG!....5BG7 . .^^:~:^^:^:^^::^........ Y55YJ!:...:^~!J~^~?5J7^:.......~^^^..:^^::^:....:!~~!Y^ :~?7~^~^::....^..^^~:..:^.... ...:.:^^:.... . :: .~ ...:^. ^B! ...~B? ..:..::^~!~. .........?P^....?BBY .. ^^^^:~:^::^^:::....... ???7. .~!!Y557:::....^~^^::^:^^^::....^!~~~J~ :~7~~^^^:::....:.:^~~..^:.......:::^^^.... . ~. :. ... ?B:.. 5B. . ........:Y:..:.7PB5 . :. :^~:^^^^::^::::...... Y7: .. ..7!~~JBY^.::...~^^^^:.:^:.:....~~~~~J7 .!!~^::^^:::...:..^~^:.^.......::.::::... .: . ..... JB: :BY ........7:..::Y555. .^. :~~^~:^::^^::^:..... ? .:~:.......:^~~~7GG! .~:.:~^^^..^^^.:.. .!~~~~?J..!7~^:::^^:::.....:^^^.:..:...:::.::^.... .: ... .J#~ ~#7 . .......^:...:JBGP. .^. .!^!^^:::^^.:^..... ..... ... ..:~!P#J ~57^^^^:.^^.:^:....!~~~~7Y:.77~::^..^^:::..:.:^~^~:..::::::...:^... .. .. . :BP 7B~ .......:^....!#BB^ .^...... ..::^^:::^::^:.... .. .........::!!P#^ ~5Y~^^^^^...^:.. :7~~~^7Y~.7J^::^...:^:::..:.^~^^...::::::....:.... :. . ?B~ ?B~ ......:^.....75G7... .::::... .::^^::::... ... ..^!!P7 7557^^^:....... :7~~~^!Y~.!5~:::....:^^::....~~^...::::......:.... .. . .J5^ 7B! ......:J...... .. .^^^::::. ..::::..: ... ........~!! J5Y::^^...... :?!~~~~!^:^57:^:......:^::::.^!:....::.......:.... .. .?5^ ~P7 ......^B:..... .^:^:^^:. ...^::. .. ... ..:!7!^ ^55? :^:.:.. ^?!~~~~^^^.J?^::........^:::::!.............:::... .. . !57 ^5J. .......7#?...... .:::...... ... .^^: .. ... :~7!^ .GP5. :^... ^?!~~^~^^~:!?~:^:........:::::^.......:::::.:::.... .. .. :YJ. .:?5! ........!BB:....J57. .:::........ ^^: ... :!!~^:.:~7! PBG: ... :?7~~~^::~~:?!~::..........::^:...:..::::::::::...... : .. .75! .. ^5Y: .........:^Y#7... ~BBB~ .:^^::.. .. ^^: .:. :?PGGPPY?!!77. PBB: .. :??~~~^::^!:!!~^^:...........:.....:.::::::.:::........ :. .. :YY: .. .757. ............~:~BG... .Y55? .:^^: .....^^: . .7PGPJ77!!!7?J?..PBB. .:..?J!~^::::~!^!^^^^:................:::::::.....:.......... . .: .. .~5?. . ..:J5! .. ............::::^^:.Y#7 75Y5. .:^: ..^^^ . .~5GGP5Y7!~~~~!!?^.GBG. . .!7~~:::.~!~^~^:^^:...........:.....:::::.....:........... .... .^. .. ...757: ...^5P~ ... .... .....:::::^:::::!^:.:GG. .5Y5! .:: .:^~^ .7BP5PP55Y7~~^^~~!!:.!?. . .^~^^:.^!!^^^^:::......:.......:.....:::.....:........... ..::..... .:~. .. :. .. ^55: ... ..^YY^.. ... ......:..::^^^^^^^^^^!~^~:.7#7 !5YY ...:::.......~^ ~ :^J5J5555YY?!~^^^~!!: .::. ... .::...:..:::..........:........... :::::.:.::......^^ ..... .:. . .^^JG7.... ..:7^.::. ........... ..:...::...::.:^^^^^^^^^^^~~^::~^:YB. .YY5^ .:.. ..:^ P! . .:~JJYY55YYJ!~^^^~~!^ .. ::........:::........:.......... .::::..::^::::::~:.......^:... .. ....^~^^GY^::...~!77!~..:............ ......::::..:::::^^^^^^^^^^~~^^^::^^~GJ ^55J .....~~~ PB^ . ..^7JJYY55YJ7~~^^^~!~. ... .:.....:....::.......:....:......:.:::.::^:::::^~..::::::^^:........................::^~.!!..~:..^!!~~!:.~~::::::::.........:::::..::::^^^^^^^^^^^~:^^^:.::::5~ ?55! ...~!! 5BB~ ..:!JJJY55YY7~~~^^~??. . .. ..::....::...........::....:::.......::.::^::::^~.:::::::^:^::...........:::....::..::~~^77^:!^:::~!!!^~!!..^:::::.:::.....::::^:..:::^^^^^^^^::^!^::^^^:.::.:J. .Y55^ ..^ .5B? ..:~?JJY55P?.!!!!~!?~. . . .....::.:::..........^:..:..:::..::...:..:::::~^:::::::^^::^::::::::::::::...::::..::~.^777^.:^::^~!!!^!J~.:^::::::::::..:^:^^^..::::^^^^^^^^::7!~^::^^^.::: :~ :GBG: .: ..:~!!!777:~~^^^^~.^ ...................^. ....... ........ ....:........::........................ ..::.^^^~^:::....^^^:.^~:............ .:...:. ........::::..:^^::....:.... .. .~?J. */ /* * powered by ANDRIY POPYK * in honor of MYSELF and SEGMENT DECOMPOSITION and N^(log(N)) and (Harry Potter and the Methods of Rationality) and Monkie D. Luffy */ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #pragma GCC optimize("O3") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops") #pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt") using namespace std; using namespace __gnu_pbds; //#define int long long #define float long double #define elif else if #define endl "\n" #define mod 1000000007 #define pi acos(-1) #define eps 0.000000001 #define inf 1000'000'000 #define FIXED(a) cout << fixed << setprecision(a) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define time_init auto start = std::chrono::high_resolution_clock::now() #define time_report \ auto end = std::chrono::high_resolution_clock::now(); \ std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << endl #define debug(x) \ { cerr << #x << " = " << x << endl; } #define len(x) (int) x.size() #define sqr(x) ((x) * (x)) #define cube(x) ((x) * (x) * (x)) #define bit(x, i) (((x) >> (i)) & 1) #define set_bit(x, i) ((x) | (1LL << (i))) #define clear_bit(x, i) ((x) & (~(1LL << (i)))) #define toggle_bit(x, i) ((x) ^ (1LL << (i))) #define low_bit(x) ((x) & (-(x))) #define count_bit(x) __builtin_popcountll(x) #define srt(x) sort(all(x)) #define rsrt(x) sort(rall(x)) #define mp make_pair #define maxel(x) (*max_element(all(x))) #define minel(x) (*min_element(all(x))) #define maxelpos(x) (max_element(all(x)) - x.begin()) #define minelpos(x) (min_element(all(x)) - x.begin()) #define sum(x) (accumulate(all(x), 0LL)) #define product(x) (accumulate(all(x), 1LL, multiplies<int>())) #define gcd __gcd #define lcm(a, b) ((a) / gcd(a, b) * (b)) #define rev(x) (reverse(all(x))) #define shift_left(x, k) (rotate(x.begin(), x.begin() + k, x.end())) #define shift_right(x, k) (rotate(x.rbegin(), x.rbegin() + k, x.rend())) #define is_sorted(x) (is_sorted_until(all(x)) == x.end()) #define is_even(x) (((x) &1) == 0) #define is_odd(x) (((x) &1) == 1) #define pow2(x) (1LL << (x)) struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>; template<typename T> using max_heap = priority_queue<T, vector<T>, less<T>>; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T> using matrix = vector<vector<T>>; template<typename T> using graph = vector<vector<T>>; using hashmap = gp_hash_table<int, int, custom_hash>; template<typename T> vector<T> vect(int n, T val) { return vector<T>(n, val); } template<typename T> vector<vector<T>> vect(int n, int m, T val) { return vector<vector<T>>(n, vector<T>(m, val)); } template<typename T> vector<vector<vector<T>>> vect(int n, int m, int k, T val) { return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, val))); } template<typename T> vector<vector<vector<vector<T>>>> vect(int n, int m, int k, int l, T val) { return vector<vector<vector<vector<T>>>>(n, vector<vector<vector<T>>>(m, vector<vector<T>>(k, vector<T>(l, val)))); } template<typename T> matrix<T> new_matrix(int n, int m, T val) { return matrix<T>(n, vector<T>(m, val)); } template<typename T> graph<T> new_graph(int n) { return graph<T>(n); } template<class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template<class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } using i8 = int8_t; using i16 = int16_t; using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t; template<typename T> using vec = vector<T>; using pII = pair<int, int>; template<typename T> using enumerated = pair<T, int>; template<typename T, typename P> struct SegmentTree { private: function<T(const T &, const T &)> comb; function<void(T &, const P, int, int)> apply_push; function<void(P &, const P &)> merge_push; function<pair<P, P>(const P &, int l, int r, int pos)> split_push; size_t n; vec<T> tree; vec<optional<P>> pushes; void push(int v, int tl, int tr) { if (!pushes[v].has_value()) return; if (tl != tr) { int tm = (tl + tr) / 2; auto [l, r] = split_push(pushes[v].value(), tl, tr, tm); apply_push(tree[2 * v], l, tl, tm); apply_push(tree[2 * v + 1], r, tm + 1, tr); if (pushes[2 * v].has_value()) merge_push(pushes[2 * v].value(), l); else pushes[2 * v] = l; if (pushes[2 * v + 1].has_value()) merge_push(pushes[2 * v + 1].value(), r); else pushes[2 * v + 1] = r; } pushes[v] = nullopt; } void build(int v, int tl, int tr, const vec<T> &a) { if (tl == tr) { tree[v] = a[tl]; return; } int tm = (tl + tr) / 2; build(2 * v, tl, tm, a); build(2 * v + 1, tm + 1, tr, a); tree[v] = comb(tree[2 * v], tree[2 * v + 1]); } T get(int v, int tl, int tr, int l, int r) { if (l > r) return T(); if (l == tl && r == tr) return tree[v]; push(v, tl, tr); int tm = (tl + tr) / 2; if (r <= tm) return get(2 * v, tl, tm, l, r); if (l > tm) return get(2 * v + 1, tm + 1, tr, l, r); return comb(get(2 * v, tl, tm, l, tm), get(2 * v + 1, tm + 1, tr, tm + 1, r)); } void update(int v, int tl, int tr, int l, int r, const P &val) { if (l > r) return; if (l == tl && r == tr) { apply_push(tree[v], val, l, r); if (pushes[v].has_value()) merge_push(pushes[v].value(), val); else pushes[v] = val; return; } push(v, tl, tr); int tm = (tl + tr) / 2; if (r <= tm) update(2 * v, tl, tm, l, r, val); elif (l > tm)update(2 * v + 1, tm + 1, tr, l, r, val); else { auto [lval, rval] = split_push(val, l, r, tm); update(2 * v, tl, tm, l, tm, lval); update(2 * v + 1, tm + 1, tr, tm + 1, r, rval); } tree[v] = comb(tree[2 * v], tree[2 * v + 1]); } public: SegmentTree(const function<T(const T &, const T &)> &comb, const function<void(T &, const P, int, int)> &apply_push, const function<void(P &, const P &)> &merge_push, const function<pair<P, P>(const P &, int l, int r, int pos)> &split_push) : comb(comb), apply_push(apply_push), merge_push(merge_push), split_push(split_push) { } T get(int l, int r) { return get(1, 0, n - 1, l, r); } T operator[](int i) { return get(i, i); } T operator()(int l, int r) { return get(l, r); } void update(int l, int r, const P &val) { update(1, 0, n - 1, l, r, val); } void init(int _n, const vec<T> &a) { this->n = _n; tree.clear(); pushes.clear(); tree.resize(4 * n); pushes.resize(4 * n); build(1, 0, n - 1, a); } void init(const vec<T> &a) { init(len(a), a); } void init(int _n, const T &val) { init(_n, vect<T>(_n, val)); } void reset() { fill(all(tree), T()); fill(all(pushes), nullopt); } }; template<typename T> struct SetMin { using Push = T; using Vertex = T; static SegmentTree<Vertex, Push> GET() { function<pair<Push, Push>(const Push &, int, int, int)> split_push = [](const Push &p, int tl, int tr, int pos) { return mp(p, p); }; function<void(Push &, const Push &)> merge_push = [](Push &p, const Push &q) { p = q; }; function<void(Vertex &, const Push &, int, int)> apply_push = [](Vertex &x, const Push &p, int l, int r) { x = p; }; function<Vertex(const Vertex &, const Vertex &)> comb = [](const Vertex &x, const Vertex &y) { return min(x, y); }; return SegmentTree<Vertex, Push>(comb, apply_push, merge_push, split_push); } static SegmentTree<Vertex, Push> GET_DYN() { function<pair<Push, Push>(const Push &, int, int, int)> split_push = [](const Push &p, int tl, int tr, int pos) { return mp(p, p); }; function<void(Push &, const Push &)> merge_push = [](Push &p, const Push &q) { p = q; }; function<void(Vertex &, const Push &, int, int)> apply_push = [](Vertex &x, const Push &p, int l, int r) { x = p; }; function<Vertex(const Vertex &, const Vertex &)> comb = [](const Vertex &x, const Vertex &y) { return min(x, y); }; return DynamicSegmentTree<Vertex, Push>(comb, apply_push, merge_push, split_push); } }; template<typename T> struct SetMax { using Push = T; using Vertex = T; static SegmentTree<Vertex, Push> GET() { function<pair<Push, Push>(const Push &, int, int, int)> split_push = [](const Push &p, int tl, int tr, int pos) { return mp(p, p); }; function<void(Push &, const Push &)> merge_push = [](Push &p, const Push &q) { p = q; }; function<void(Vertex &, const Push &, int, int)> apply_push = [](Vertex &x, const Push &p, int l, int r) { x = p; }; function<Vertex(const Vertex &, const Vertex &)> comb = [](const Vertex &x, const Vertex &y) { return max(x, y); }; return SegmentTree<Vertex, Push>(comb, apply_push, merge_push, split_push); } }; pair<vec<int>, vec<int>> process(vec<int> a, vec<int> b) { int n = len(a); auto calc = [&]() { auto stree1 = SetMax<int>::GET(); stree1.init(3 * n, -inf); auto stree2 = SetMax<int>::GET(); stree2.init(3 * n, -inf); vec<int> most_left(n, -inf); for (int i = 0; i < n; i++) { most_left[i] = stree2[a[i]]; int best = stree1(b[i], a[i]); chmax(most_left[i], best); stree2.update(b[i], a[i], i); stree1.update(a[i], a[i], i); } return most_left; }; vec<int> left = calc(); vec<int> right; rev(a); rev(b); right = calc(); rev(right); for (int i = 0; i < n; i++) { right[i] = n - right[i] - 1; } return mp(left, right); } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; vec<int> a(n); for (int &i: a) cin >> i; vec<int> b(n); for (int &i: b) cin >> i; auto [left, right] = process(a, b); vec<vec<int>> rrend(n); for (int i = 0; i < n; i++) { if (right[i] < n) { rrend[right[i]].push_back(i); } } int q; cin >> q; vec<vec<pair<int, int>>> queries(n); vec<bool> ans(q, false); for (int i = 0; i < q; i++) { int l, r; cin >> l >> r; --l, --r; queries[r].emplace_back(l, i); } auto st_ans = SetMin<int>::GET(); st_ans.init(n, inf); for (int i = 0; i < n; i++) { st_ans.update(i, i, left[i]); for (int j: rrend[i]) { st_ans.update(j, j, inf); } for (auto [l, idx]: queries[i]) { if (st_ans.get(l, i) >= l) { ans[idx] = true; } } } for (int i = 0; i < q; i++) { cout << (ans[i] ? "Yes" : "No") << endl; } }

Compilation message (stderr)

Main.cpp:142: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
  142 | #pragma GCC optimization ("unroll-loops")
      | 
Main.cpp: In static member function 'static SegmentTree<T, T> SetMin<T>::GET_DYN()':
Main.cpp:455:16: error: 'DynamicSegmentTree' was not declared in this scope
  455 |         return DynamicSegmentTree<Vertex, Push>(comb, apply_push, merge_push, split_push);
      |                ^~~~~~~~~~~~~~~~~~
Main.cpp:455:41: error: expected primary-expression before ',' token
  455 |         return DynamicSegmentTree<Vertex, Push>(comb, apply_push, merge_push, split_push);
      |                                         ^
Main.cpp:455:47: error: expected primary-expression before '>' token
  455 |         return DynamicSegmentTree<Vertex, Push>(comb, apply_push, merge_push, split_push);
      |                                               ^