Submission #1094439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094439		shmax	Room Temperature (JOI24_ho_t1)	C++17	100 / 100	239 ms	32596 KiB

Main

/*


         ~??:   :!?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'000'000'000LL
#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>;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, t;
    cin >> n >> t;
    vec<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i], a[i] %= t;
    srt(a);
    a.erase(unique(all(a)), a.end());
    set<int> vals(all(a));
    auto calc = [&]() -> int {
        if (vals.empty()) return 0;
        if (len(vals) == 1) return 0;
        return (*vals.rbegin() - *vals.begin() + 1) / 2;
    };
    int best = calc();
    for (int i = len(a) - 1; i >= 0; i--) {
        vals.erase(a[i]);
        vals.insert(a[i] - t);
        chmin(best, calc());
    }
    cout << best << endl;
}

• Subtask 1: 15 / 15
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35
• Subtask 5: 15 / 15