This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
~??: :!?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) {
n = 0;
}
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) {
// if (this->n < _n) {
// tree.clear();
// pushes.clear();
// tree.resize(4 * _n);
// pushes.resize(4 * _n);
// }
if (this->n != _n) {
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);
}
};
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) {
auto stree1 = SetMax<int>::GET();
auto stree2 = SetMax<int>::GET();
int n = len(a);
auto calc = [&]() {
stree1.init(2 * n + 2, -inf);
stree2.init(2 * n + 2, -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: In instantiation of 'void SegmentTree<T, P>::init(int, vec<T>&) [with T = int; P = int; vec<T> = std::vector<int>]':
Main.cpp:411:13: required from 'void SegmentTree<T, P>::init(int, const T&) [with T = int; P = int]'
Main.cpp:483:36: required from here
Main.cpp:396:21: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
396 | if (this->n != _n) {
| ~~~~~~~~^~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
