#include"bits/stdc++.h"
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define ld long double
#define ff first
#define ss second
#define db double
#define time_begin() auto begin = chrono::high_resolution_clock::now()
#define time_end() auto end = chrono::high_resolution_clock::now(); auto elapsed = chrono::duration_cast<chrono::nanoseconds>(end-begin); auto sec = elapsed.count() * 1e-9; cerr << "\n\nExecution time: " << sec << " seconds";
#define check_time() cerr << "\nStatus : "; if (sec>1) cerr << "Time Limit Exceeded 1!!!1!111"; else cerr << "You good brother"
#define precision(x) fixed << setprecision((x))
#define check_ok(s) cout << s << " is aight" << '\n'
using namespace std;
/*
++++++++++++++++*S%+*++***?%+;;;;;;*%++**+***S*;;;;;*%S%?*+;;;;+*?%SSSS#*+++***+%%?S?+*****+?@%***+***++****%?;;;;;*%**+*++?%+*S****+**%*;*%%?*+;;;;++*%%?+;;*%*+**+++*%S%+++++++?%+:;;::::::::::::::;;;
;;;;::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;::::::::::::::::::::::;;;;;;;;;::::::::::::::::::::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++
;;;;;::;::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;::::::::::::::::::::::::::;;;;;;;;::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++
;;;;;;;;;;;;;;::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;::::::::::::::::::::::::::::;;;;;;;;;;:::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;;;;:::::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++
;;;;;;;;;;;;;;;;;;;:::::::::::::::::::::::::::::::::::::::::::::::::;;;::::::::::::::::::::::::::::;;;;;;;;;;:::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;:::::::::::::;;;;;;;;;;;;;;;;;;;;;;;;;+++++
;;;;;;;;;;;;;;;;;;;;;;;;;;;;:;:::::::::::::::;;;;;;;:::::::::::::::;;;:::::::::::::::::::::::::::::;;;;;;;;;;:::::::::::::::::::::::::::::::::;;;;;;;;;;;;:::::::::::::::::::::::::;;;;;;;;;;;;;;;;+++++
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;????%??**++;;;;;;;;;:::::::::::::;;;;;;:::::::::::::::::::::::::::::;;;;;;;;;;::::::::::::::::::::::::::::::::::;;;;;;;;:::::::::::::;*?;::::::::::::;;;;;;;;;;;;;;;+++++
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;:*#S%S#S#SSSSS%%%**+;;::::::::::::;;;;;:::::::::::::::::::::::::::::::;;;;;;;;;;;:::::::::::::::::::::::::::::::::::;;;;;:::::::::::::+%#S?+:::::::::::;;;;;;;;;;;;;;;+++++
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;?S%%#S#SSSSSS####S%%*+;;::::::::;:::::::::::::::::::::::::::::::::::::;;;;;;;;:::::::::::::::::::::::::::::::::::::::::::::::::::::*?#%???+::::::::::;;;;;;;;;;;;;;;+++++
++;;;;;;;;;;;;;;;;;;;;;;;;;;;;*?++?S##SSSSS####S%S%%%%??*+;::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*?%%???**;:::;;::::;;;;;;;;;;;;;;;;++++
++++;;;;;;;;;;;;;;;;;;;;::::::+%??*+?%%%SS######SSSS%%%%%??*+;::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*?%%????*++;;:::::::::;;;;;;;;;;;;;;++++
++++;;;;;;;;;;::::::::::::::::;*?SS?**++**??%%%SSSSS?SS%%?*++;,,,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*?%%??????++;::::::::::;;;;;;;;;;;;;;++++
;;;;;;;;;;;;:::::::::::::::::;;;*%#%%?*%?*++++++***??SS%%*++;,,,::,::::::::,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::+?%%?*?????*;;:::::::::;;;;;;;;;;;;;;+++++
;;;;;;::::::::::::::::::::::::;;;+?%%%%S#S%?*+;;;;;;;;+***++:::::::,,,,,,,,:,,,,,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::+?%S%?*?????+;:::::;;:;;;;;;;;;;;;;;;;;;+++
::::::::::::::::::::::::::::::;;;;;;+*%%S%???****++;:;:,,,:;::,,,:,,,,,,,:;+;;;:;;:,,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::?%%??*??????+;;::::;;;;;;;;;;;;;;;;;;;;;;++
::::::::::::::::::::::::::::::;;;;;:::;;***??********++;;:,,,,,,,,,,,,,:;+**++++;;;;::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*%S??**?????*+;:::::;;;;;;;;;;;;;;;;;;;;;;;+
:::::::::::::::::::::::::::::;;;;;::::::::;+*++***+++++++++;;:,,,,,...,,,:++:,:*******+;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;?S??**?????**+;:::::;;;;;;;;;;;;;;;;;;;;;;;;
::::::,::::::::::::::::::::::;;;;;;:::::::;;;;;;++++;;;;;;;;;::;;;:::::,,,,,,,:;????????+::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*??***??????**;;;:::::;;;;;;;;;;;;;;;;;;;;;;;
:::::::,::::::::::::::::::;;;;;;;;;;;;;;;;;;;;;;+;;;;;;::::::,:;;;;+;;;++;;;:;:;********?+::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;??*?????%??**+;;::::::;;;;;;;;;;;;;;;;;;;;;;;
:::::::,,::::::::::::::::;;;;;++++++;;;;;;;++;;+;;;;;;;;;::;::::;;;++*+*?***++;;+;;;;;;+**+:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::+?*?????%?***+;+;::::::;;;;;;;;;;;;;;;;;;;;;;;
:::::::::::::::::::::::::;;;;;;;;+++++++;;;;;;;;;;;;;;;;;::;;;;;;;;++++;*+**??*+***********;::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*???????**+++++;::::::::;;;;;;;;;;;;;;;;;;;;;;
:::::::::::::::::::::::::::::::::;;;+++;;;;;;;;;;;;;::::::::::::;;::::::++++***++*******??**::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::**?????*+;;+**;:::::::::;;;;;;;;;;;;;;;;;;;;;;
:::::::::::::::::::::::::::,,,,:::;;+++;;;;;;;;;;;;;;;;;;::::::;;;;;;:::;;;;;++++*++*******?+::::::::::::::::::::::::::::::::::::::::::::::::;:::::;;;;;;+**??**+++;+++:::::::::::::;;;;;;;;;;;;;;;;;;;;
::::::::::::::;;;;;::::::,,,,,,,::;;+++;+++;;;;;;;;;;;;;;::::::::::::::::;;;::;;;+;;*******??+::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;++***????*+;;++;;;;::::::::::::::::::;;;;;;;;;;;;;;;;;;
::::::::::::::;;;;;;::::,,,,,,,,::;++++++++++++;;;;;;;;;;;::::::::::::::::;;:::;:;+:;+****????;::::::::::::,:::::::::::::::::::::::;;;;;;;;++***????????*?**+:::::::::::::::::::::::::::::::;;;;;;;;;;;;
:::::::::::::;;;;;;;:::,,,,,,,,::;++++++++++++;;;;;;;;;;;;:::::::::::::::::+;::;;:+;,;*++?????*;:::::::::::::::::::::::::::::::::;;;;;;++**????????????%S%%?*+;:;::::::::::::::::::::::::::::;;;;;;;;;;;
:::::;;;;:;;;;;;;;;;:::,,,,,::::;;;+++++++;;;;;;;;;;++;;;;:::::::::::::::::++;::;:;;::+****?????+:::::::::::::::::::::::::::::::;;;+**??????????????%S####S%?**+;;;;;;::::::::::::::::::::::::;;;;;;;;;;
;;;;;;;;;;;:::;;;;;;::::::::::::;;;;;++++;;:::::;;;;++++;;;:::::::::::::::,;+;;:::;;:::+*+*??????+::::::::::::::::::::::::::::;++**?????????????%S#######S#S%%?*++;;;;;;;:::::::::::::::::::::;;;;;;;;;;
;;;;;;;;;;;:::;::::::::::;;;;;::::;;;;++;;:::::::;;++++++;;;:::::::::::::,,,+++:::;+:::;*++*??????+::::::::::::::::::::::::::;**?????????????%S##@@#######S#SS%?*+;;;;;;;;;::::::::::::::::::::;;;;;;;;;
;+++;;;;::::::::::::::;;;;;;;:::::;;;;+;;:::::::::;;++++;;;;:::::::::::::,,,;++;:;;;::::+*****?????*;:::::::::::::::::::::::+*??????????%SS##@################S%?*+;;;;;;;;;;;;::::::::::::::::;;;;;;;;;
;;;;;:::::::::::::::::::::::::::::;;;;;;::::,,::::;;;;;;;;;::::::::::::,,,,,:+*;;;;+;:::;***+*?????%?;:::::::::::::::::;;;:+?????%??%%%SS################S#SS##S%?*+;;;;;;;;;;:::::::::::::::::;;;;;;;;;
:::::,,,,,,,,,,,,,,,,,,,,,:::::::::;;;;:::::,,,:::::;;;:::::::,,,,,,,,,,,,,,,:++;;++;::::;*****????%%?+;:;;;;;;;;;;;;;;;;;;+?%%%%#%%%%%SS##@##@@@######S?????S##S%%*;;;;;;;;;;;::::::::::::::::;;;;;;;;;
:::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::,,,,,,:::::::::::,,,,,,,,,,,,,,,,,,,;*;;;;;:::::+****?????%%%?+;:;;;;;;;;;;;;;;;;;?%%??%S%%%%SS####@@@@@@@@##?SS%%??%S#S%%+;;;;;;;;;;;:;;:::;;:::::::;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::,,,,,,,,,,::::::::,,,,,,,,,,,,,,,,,,,;++++;;,,,,,:+****????%%%%%?+;;;;;;;;;;;;;;;;;*%%%%%SS%%SSSS######@@@@##SSS#SS%?%SSSS%*;;;;;;;;;;;;;:;:::::::::::;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::,,,,,,,,,,,,,,,,,;;++;:,,,,,,;*****????%%%%%%*+;;;;;;;;;;;;;;;+%%%%%SSSSS%%SSSSSSS##@@##SSSS##%?%SSS#S?;;;;;;;;;;;;;;;:::::::::::;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::::::::,,,,,,,,,,,,;*++;:,,,,:::;****????%%%%%%%?*;;;;;;+++++++;;+%%%%%S%%%%%%SSSSSSS##@##SSSS#%??SSSSSS%+;;;;;;;;;;;;;;;:;:::::::;;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;+++;;;:::::,,,,,,,:**++:::::::::;****???%%%%%%%%%*;;++++++++++++;*%%%%%%?%%%%%S#SSSSS####SSSSS%*%#SSSS%%?+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
,,,,,,,,,,::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;++++++;;;;:::::::::;*+;:;;;;;;;;;+***???%%%%%%%%%?;::;;;+++++++++;?%%%%#%%%SSSS%%%SSSS###SSSSSSS##SSSSS%%*+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
,,,,,,,,,,::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;+++++++++++;;;;;;;;;:;+;:++;++++++;***????%%%%%%%%?++;;;::::::::::;;*?%%SSS###S%%%%SSSSSSSSSSSSS###SSSSSSS?*+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
,,,,,,,,,,,:::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;++++++++++++++;;;;;;;;+;;+++++++++++*?????%%%%%%%%%????**+++++++;;;;;;+*?SSSSS%%%%%SSSSSSSSSSSSSSSSSSSSSSS%*+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
:::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::;;++++++++++++++++++++++++::;+++++++++++*?????%%%%%%%%%%%%%%???????****+++++%%%%%%%?%%%SSSSSSSSSSSSSSSSSSSSSS%*:::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::;;++++++++++++++++++++++++++;:+++++++++++++*????%%%%%%%%%%%%%%%%%%??????????????%%%%??%%%%%SSSSSSSSSSS##SSSSS%%%?;,,,,:;;;;;;;;;;;;;;;;;;;;;;;;;;
::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::;;++********++++++++++++++++++;;;+++++++++++++*?????%%%%%%???????????????????%%%????%S%%??%%%%%%SSSSSSS###SSSSS%%%?;:;;;:::;;;;;;;;;;;;;;;;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;;+*****************++++++****+;;;******++++++++**????%%%?%??????????????????????????SS%????%%%%%SSSSSS##SSSSSSS%??*+**++++++;;:;;;;;;;;;;;;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::;;++****************************+;+;**********+++*************?????????????????????????%%%%S#S??%%%SSSS###SSSSSSS%??*+++;++++;:;;;;:;;;;;;;;;;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;+******************************;;;*******************++++;;;+++++***????????????????????%%%%%%%%%SS#####SSSSS%%%?*+;::::;;;;;;;;++;;;;;;;;;;;;;;;;;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;+*******************************++;*******************+++;;;;;;;;;++++++*******************?*?????%%%?SSSSSSS%%%?*+;;;:,,::;;;+**+++;;;;;;;;;;;;;;;;;
,,,,,,,,,,,,,,,,,,:::;;;;;:::::::,,,,,,,,,,,,::::;+*********************************;;**********+++;;;;+++;;;:::::::;;++++++++;;+++++++++++;;;;+*****+;:+%SSSSS%%??**+;;;:,,,:::;+*%?**?;;;;;;;;;;;;;;;;
,,,,,,,,,,,,::::;;;+++++++++;;;;:::::::::::::::;;+*******************************+++;:+*****+++;;::::::;;;;::::::::::;;;+;;;;;;;;;;;;;++;;;;;;;;****+;:;+?%%%%%???***;;;:,,,:::::;+?SS%%*+;;;;;;;;;;;;;;
,,,,,,,,::::;;;++++++++++++++++;;;;;;;:::::::;;++*****************************++++++;;+++;;;;;:::::::::::::::::::::::;;;;;;;::::::::;;;;;;;;;;;;+++;::;+*?%%%????***+;;;:;;++++;;++?SSSS%**;;;;;;;;;;;;;
,,,:::::;;;;;+++++++++++++++++++;;;;;;;;;;;;+++**??*********+++++++++++++++++++++++++;;;;;;:::::::::::::::::::::::;;;;+++;;:::::::::::;;;;;;;;;;++;:,:++*?????******+;;;*****????***SSSSS?%?;;;;;;;;;;;;
::::;;;;;;;++++++++++++++++++++++;;;:::;;;;;;++****++++++;;;;;;;;;;;;;;;;;;;++++++++;:;;;;;::::::::;;;;;;:::::::;;++***++;;;:::::::::::;;;;;;;;;+;;,,:++????********+;;*****??%SSS%*SSSSS%?S+;;;;;;;;;;;
;;;+;;;;;;++++++++++++++++++++++;;::::::::::;;;;;;;;;;;;;;:::::::::::::::;;;;;;;;+++;:+++;;;;;;;+++++++;;;::::;;++******+++;;::::::::;;;;;;;;++++;:,,:+************++;+?????%SSSS##?SSSSSS?S%;;;;;;;;;;;
;++;;;;;;+++++++++++;;+++++**++;;;::::,,,::::::::::;;;;;;;:::::::::::::::;;:::;;;;+++:+*****++++++++++++++;;;;++++********++;;;::;;;;;+++++++++++:,,:;+***********+*+;*???%%SS#####%%#SSSS%SS*;;;;;;;;;;
;;;;;;;+++++++++++++++++****+++;;;;::::::::::::;;;;;;;++++;;;:::::::::::;;;;;;;;;;+*+:;*****++++++++++++++++++++************++++;+++++*****++++++:,:;++******??******?%%%%SSS#SSS##%?SSS##SSS%*;;;;;;;;;
;;;;;;;++++++++++++++++++*++;;;;;;::::::::::;;;;;;;;++++++;;:::::::::::::;;;;;;;;++*+:;++++;;;;;;+++******************????*****++*************++;,:;+++*****??*********?%%SSSSSSS##%?%#S##SSSS%+;;;;++++
;;;;;+++******++++;;;::::::::::::::::::,,:::;;;;;:::::::::::,,,,,,,,,,,,,,,::::;;;++;;:;::::::::;;++*************???*********++++*********++++++::+*+++*****?*****+;;;+*?%%SSSSSS#S%?%#S##SSSSS*;;;+++++
+;;;+++*??????**+;;:::,,,,,,,,,::::::,,,,,,,,,,::,,,,,:::,,,,,,,,,,,,,,,,,,,,:::::::::,,,:,,::::;;+********???????**++;;;;;;;;;;;;;;;+++****++++;+*+++****????***+;:;;+*??%%SSSS##S%?S#S##SSSSS?;;+++***
++++++*???????**+;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::,,,::,,,:::;;++*?????********++;;;::::::::::::::::;;++******+***++****?????*+;:::;;+*??%%%SSS###%%##SS#S#SS%?+++***??
*++++++**?******+;;:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::,,,:;;;,,::;;++**?????***+++;;::::,,,,,,,,,,,,,,,,:::;++*???%?***++****??????*;:::;;++**??%SSS##@#SS##SS#SS#S??***???%%
?**++++*********++;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::,,,:::::;;++***??????**+++;::,,,,,,,,,,,,,,,,,,,::::;+*??%SS****+******????*;::::;;+;*??%%SS###@#S####S#SS#%?????%%%%%
??**++******+++++;;:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:,,,,,,,,,,,:::::::::;;;;++++****???***+++;::,,,,,,,,,,:::::::::::::;;+**%S?***++*****?????+::::;;;++*??%SSSS##@######SSSSS%????%%%%%%
??**++++++++;;;;:::,,,,,,,,,,,,,,,,,,,...,,,,,,,,,,,,,,,,,,::::;;;;:::,,,,,,,:::::::::;;;;+++++++*******++++;;::::::::::;;;;::::::::::;;++**?***+++*****?????;::::;;;+*+?%SSS###@#########S#S%????%%%%%%
?***+++;;;;::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::;;;+++****+;;::::::::;;;;;;;;;,:;+++++++++;;;;;;:;;;;;;;;+++++++++;;;;:::;::;;;;+++****+*+*****?*??*;;;;;;;+***%%SS###@@@########S#S%????%%%%%%
++++++;;;;:,,,,,,,,,,,,,,,,:::::,,,,,,,,,,,,:::;;;;;+++***************+++++++++**+++++:,:+++++++++;;;;:::;::::::;:;********+++;;;;;;;;:;++******+++****??*??;;;:::;;+**??%SS#S#@@@####S##SSSS%????????%%
;;+++++;;;:,,,,,,,,,,,,,::;:;**+;;:::::::;;+++*****?*?????*???******??*???*???????****;::********++;;;;:;::::::::;:;++*****+++;;;;;;;+++**??***+*++****??*?*;;:::;;++*?%%S####@@@@@####S#SSSS%????%%?%%%
++++++*++++;::,,,,,,,,::;;;;*%%??**++++**????????????***??*????*??????????*???????????*:+???????****+++++;;;;;;;;;+:;;++;;++;;+;::++++*+*******+;+*****??*?*::::;;+**?%%SSS##@@##@@######SSSS%??*????%%%
**?**?*????*+;;:::::::::;;;+*******+*++*++*++++++++++++;++******+***?******************:;******************+++++++++:,;;;;;;;;;;;++++*********++++++*****++;:::;;+**??%S##S###@##@@@####SSSS%%??*???????
+***??*?****+;:::::::::::::::::::::::::::::::::::::::::::::;;:;::;++;+++;;;;;+;++++++++::;++++++++++******+*??**++++;;;;:;;,:;+;;++++*******++;;;;;;+++++;:,::;++**?%%SS##S#@##@@@@@@###SSSS%%??*%??????
;+*****+++;;::::::::::::::::::::::,,,,,,,,,,,,,,,,,,,:,,,,,:::,,:;:;;++;;;;;;;;;;;;;;;;;:;++++++++*++****++*??**+;;;;;;::;::++;;++++**;+*?%+++++******+;:,::;+++**%%%?S#########@@@@@####SSS%%??*?%%%%??
;+****+++;;::::::::;;;;;;;;;;::::::::::,,,,,,,,,,,,,,,,,,,,::,,:::;;++++++;;;;;::::::;;::;*+;;;;++*+++**++;;??**+;;++;;;::+;++;+*;:******?**+*******;:::;;++***?%SSSS%###########@@@@####SSS%%%?+?%%%%??
++*****+;*++++++++*****???****+++++++;:;;::,,,,,,,::::::;;;;;:,;;+++***+;+;;:::::::,::::,,::::,,:::;;++;+**:*%%*+++;+*;;;;++***??*+*;+*;++++*****+:,::;+**???%%SSS#SS###S#########@@@@###SSS%%%?+???????
***?????*?+????%%?%%%%%???*??????*+?*++*+;;:::,,,,:;;+++++++;;,:+++++++;:::::::::,,,,,,,:,,::,,:,,:::;;+++:;*???*:+++*+;+*+**?????*+*%?**+++***;:::;++*?%%%%SSSSSSSS###S#########@#######SSSS%?%*???????
++****????*??%???*********++;;*++*;++++++;;;:::::::;;;;;;:;;::,:;;;;;::::::,::,,,,,,,::;;,;;::;;::::;::;+;++?%?*?*;**;::+%????%?*+;;+**:+***+;:::;+*??%SSSSSSS%%%SS##SSS#################SSSSS%%*?%?????
;;++++++*********++++++;;+;;:;++++;;;;;;;;;;::;;+;;::::::,,:,,,,::::::,::::,,,,,::,:;+;:,:+;::::++::;;;:::;*???*??;;;:;+*?%***?*+;+?******;:::;++*?%SSSSSSSS%%%SS#####SS##################SSSS%%*?%?%?%%
;;;;;+++**+++++;;++++++;;;;;:::;;;;;;;;;;;;;::+++;;::::::::,,,,,,:::::::,,,,,,:::;:;;;::+;::;++;:::;;;;:::::;+??*;;+*?%%??*+;;++;+;+++*;;::;++*?%SS##SSSSS%%SS###S#@@#####################SSSSS%??%?%%%%
+++*****?****+;;:::;++;;;;;::::::;;+;++;+:;;;++++;;;;;;;;;::::::,,:::::,,,,:;+;;;:;**++?+;;*?++;;;+*;:;+;:;;:::;;;+**?%???*;;*?*+*+++;:::+**?%%S###SSSSSSSS#####S?#@########S############SSSSSSS??%%%%%S
??%%%?%S%%%?**++;;+:+++++;:;:::::;;;;;+;;;:;;:::;;;;;:;;;;;;;::;:::,,,,:::;;;+;+?;+*+;+%?+;*+++******;**+;+;;;::;+?%?*+;;++*+**+++;:::;+*?%%SS#SSSS%SSSS####SS%%?*S@##@@@@###@@@@@@@@@###SSSS%SSS%%%SSSS
?*%?%??%??****;++;;;++;;;;;;;::::::::::::::::::::::::::::::::::::::::::++**+**++??**+*?S%*?%+*?%?*?%S?*?*****+;;:::++++++**++++;::;;**??%SSSS%SS%SSSS####S%%?????*%@@@@@@@@@@@@@@@@@@##@@#SSS%%SS%%%SSSS
+;+++++++;;;;;;;;;;:;:::::;::::::::::,,,,,,,::::::,:::::::,,,,,,,:::::+***?*+?%??%%??%?**%SS?%SSS?%%%S????*?%*++++::+**++*+;;:;;+*?*?%%SSSSSSSSS######S%??***?????%@@@@@@@@@@@@@@@@@@@@@@@##SS%%SS%%%%%%
;;;;;;;;;;;;;;;::::,,::::::::::::::::::::::::::::::::;::::,,,,,,,,,:;?%*******%?%%%S#S???%SSS%S#S?%%S#S%SSSS%%?*++;;++++;;;;+*??%%%S%%SSSSSSSS#####S%?***++*?%????%#@@@@@@@@@@@@@@@@@@@@#@#SSS%%SSS%????
;;;;+;;;;;;;++;;;;;:::;;::;::;;;;;;;;;;;;;;;:::;;;;;;;:;;;::::::::;;?%%??%S%S%%?%SS%S####S##SS##SSS###SS####%S%?**+;;:;;+*?%%%S%%SSSSSS######S%%???**?%%%?%SSS%??%%#@@@@@@@@@@@@@@@@@@@##@@#SSS%%SS%**?%
+********+**+++;;;;;;;:::;;;::;;;;;;;;;;;;;;+;;:;;;;;;+;+++;;+++;+++?????%?%%?%SS##%?S##SS#S%S@##S%*++;;;;;;;;:::::;+*??%SSSSSS%SSSS#####SS%?**++*++*???%S##S%%??S%S@@@@@@@@@@@@@@@@@@@##@@@#SSS%SSS??%S
*******+****++++;;;;;;::;;:::::;;;;;;;;;;::;+;;;;;::++++++++;+++++++?%%%?*??%S#S%SSSS#####S%S#S?+;:;++++++;;:::;+**?%S%S%?SSSSSS####S%%%?**+++++++*?%%SS#SSSSSS??S%S@@@@@@@@@@@@@@@@@#%#@@@@###SSSSS%%SS
***********+;;+++;;;;;:::;:::::;;::::;;:::;;;;;;++;;;;*+++++++++++++?%%%%%SS#SSSS####S#@@#S#S*;;*??%%%S???*?***??%%SSSSSSSSSS##S%??*++*?**+++*++**%%S##SSS#S#S?*%%%%@@@@@##S#@@@@@@@@#%#@@@@@##SSSSS%%%%
+++++++++++++;;;;;;;;;;;;;;::::;;::::;;;;;;;;;;;;;;;;;+;;;;++++;;;+;+%%%SS###SS###@@SSS#SS##%?%%SSSS%%%*??????%%%SSS#SS#####%?**+*;;*?%?*+++++**?%SS##S####S%???%#S%#S#######@@@@@@@##%#@@@@@@#SSSSSS%??
+++++;++++++;;;;;;;;;;;;;;;;:::;;;::::;;;;;;;;;;;;;;;;;;;;;+++;;;;+++*?%SS##SS#####SS#S#S##%%S###?*+**?????*%SSS##S+?SS%#%?*++**+?++%%?*++++*???%SSSSSSS%%???**?S#S%SS#@@@@@@@@@#@@@@@@@@@@@@@#SSSSSS?**
++++++++++;;;;;;;;;;+++;;;;;;;;;;;;;;;;;;;;;;;++++;+++*++++*+********+;*??SSSSSSSSSS#######%???*++**??%%SSS%SS####S?%S%**++*****+***?**+;++++;;;+****????????*+?S##S###@@@@@@@@@@@@@@@@@@@@@@@##SSSSS???
***+****++++;;;;;++++++;+;+++;+;++;;;+++;+;++++++++++************+*++*++****?????%S######S%?****?%SSS%SSSS##SS##SS##S%**?*?*+++++++;;;;;+***+++++++*?%SSSSSSSS%%###SS#@@@@@@@@@@@@#@@@@@@@@@@@#S%S#SS%%%
************+++++++++++++++++++++++++++++*+++*+*************++***+;++*****??%%%SS#@@#####SSSSS#####%%%SS#%#####SS##S%?**+**+++++++*******????%%????***%SS############@#@@@@@@@@@@##@@@@@@@@@@@#S%%S#S%%%
????*???????*******++++++++;+++++*+++*+***+++*++*+++********++*+**+*****??S@S%S#S@@@@@@@@@#@@@@@@@#%S##S####S%##S%%%?*???%*????%?????????????%%SS%%%%%%%SSS####@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#SSSS##%??
????????????????***+++++++++++++++++**********+*+**********+************%%%#@##@#@#@@@###S%%S###@@@@@@@#@@@@##@##%%###SSSS%?*?%%S#SSSSS%%%%%%%%%%?%%%%%%###@@##@@@@@##@@@@@@@@@@@@@@@@@@@@@@@#SSSSSSS%??
?????????%??????****************+*****************???????????????+++***?%%?%#@#@##@##S%%%%%%#######@@#@@@@@@@@@#@##@@##@@SS%SSS######@@@#######SSS#####@@@@@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@#S######%%%%
????????????????************????**???????*????????????????%??%?***?%S%%%%%S%S@#@@#@#SS%?%SS#######@####@@#@@@@@@@@@@#S#@@###@@@@@@@@@@@@@@@@##@@@@@@@##@@@@@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@#S####S%%%%%%
????%%%%%%%????????****?*??????***?????????????????????????**?????%SSS%S#SS%S###@#@#%%####S##S######@#@@##@@@@@@@@@@##@@@@##@##@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@####S%%%%%%%%
?%%%%%?%%%%%%%%%%%????????????????????????%?????%%%%%?%%%%%%%%?%S%%S%%S####S##SS@##%%S######@##@@@#@@@@@@@@@@#@@@@@@@##@@#S#@@@@#@@@@#@@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@@##SS%SS%%%%%%SS
%%%%%%%%%%%%%%%%%%%???????%%%%%%%%%%??%%%%%%%%%%%%%%%%S%%%%%%S%SSSSS%####S###S%S@@S%S@#S######@@@@@@@@@@@@@@@@@@@@@@@@@@@##@@@##@@@@@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@###S%%%%SS%%SSSSSS
%%%SSSSSSS%%%%%%%%%SS%%%%%%%%%%%%%%%%%%%%%%%%S%%%%%%SSSSSSSSSSSSSSSS#@##SS##@###@#SS###########@@@@@@@@@@@@#@@@##@@@@@@@@##@@@#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#SSSSSSSSS#SSSSSS%SS
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS%%%%%%%%%SSSSSSSSSSSSSSSSSSSSSS##SS#@@#######@@@@SSSS#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##SSSSSSSSS#S##SSSSSSSS
########SSSSSSSSSSSSSSSSSSSSSSSSSS%SSSSSSSSSSSSSSSSSSSSSSSSSSSS###@@@@##@@@#@@@@#SS##@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##S######SSSSSS#SSS#####
########SSSSS####S##SS####S##########S##SSSSSS#SS##########S###S#@@@@@@@@@@##@@#####@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#SS######SSSSSSSS########
###################################################################@@@@@@@@@@@@#####@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###########################
#####################################################@@@@@@###@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@####@#######@#@#@@@@@@@@@@@@@
################################@####@#######@##@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@
######################@#######???S##S??%##S???#S??%#@@#%??S@@@@S???%@@S?????????%@@@@S?????????%@#???#@@@%??%@@S???????%@@@@@@SSSSSSSS#@#SSS#@@@SSS#@@@@@#SSSS#@@@SSS#@@#SSS#@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@#@@@###@@###@@#######@@###@#:..+@@;..:#@+..;@*..,#@@#,..?@@@#:....%@+.,.......;@@@@?.........,#S...%@@@:..;@@*.......,#@@@@@;:::::::*@S:::S@@@;::?@@@%+::::::?@#;::?@S;::?@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*..:@%....%@:..?@?..,S@@S,..?@@@*..*,.:@###%...?###@@@@###S,..*###@S...?@##;..;@@*..,SSSS#@@@@@@;::*SSSS#@S:::S@@@;::?@@?:::?SS%%#@#;::??::+S@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@S,.,#+.;:.+#,.,#@?...,,,,...?@@S,.;@+..*@@@S...%@@@@@@@@@@@:..*@@@@S...,,,,,..;@@*...,,,:S@@@@@@;::+????@@S:::S@@@+::?@S:::%@@@@@@@#;::;::;#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@;..?,.%*.,?..+@@?..,++++,..?@@;..:*;..,S@@S...%@@@@@@@@@@@:..*@@@@S...;+++,..;@@*..,+***#@@@@@@;:::;;;+#@S:::S@@@;::?@S:::%@@@@@@@#;:::;::+#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*..:.,#S..,..%@@?..,#@@#,..?@?..,;;;:..;@@S...%@@@@@@@@@@@:..*@@@@S...%@@@;..;@@*..,%%%%%#@@@@@;::*@@@@@@#;::*##%:::S@@+::;%##S%#@#;::+#?::;S@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#,,..+@@;..,:#@@?.,,#@@#,,.?#:,,?@@@%,,,%@S,,,%@@@@@@@@@@@:..*@@@@S,,,%@@@;,.+@@?.,,....,S@@@@@;::*@@@@@@@S+::::::;%@@@#?;::::::*@#;::%@@%:::?@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#S###@@#SSS#@@@#SSS@@@@SSS##SSS@@@@@SSS#@@SSS#@@@@@@@@@@@#SS#@@@@@SSS#@@@#SS#@@#SSSSSSSS@@@@@@S%%S@@@@@@@@@#%%%%S@@@@@@@@S%%%%#@@@SSS#@@@#SSS@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@?**%@@@@%****%#@@@@@#**********#@?**%@@@%**?@@S***#@@@S?*+*?S#@@@@@@@@#%?*+*?S@@@?**%@@@S**?#***S@@@?**%@@@@@?***??%S@@@@@@@S?*+*?S@@@@#***S@@?**?@@@%**%@@@@@S?***?S@@@S*+;;+?@@@@@@@@@@
@@@@@@@@@@@@@@@:..+@@%:..,,,.+#@@@@S,,,....,,,S@,..*@@@+..:@@%...S@#+,.,:,.,%@@@@@@#*,..,,,.;#@@:..+@@@*..:@*..:#@?..,S@@@@@:...,,.,:%@@@%:..,,,.,:%@@S...%@@:...+@@+..;@@@?:..,,,.,%@@?:;+:..+@@@@@@@@@
@@@@@@@@@@@@@@@:..+@@;..:%##S@@@@@@@@@@;..;###@#:..+###+..:@@%..,S@S...+S#S#@@@@@@@;..:%#@#S#@@@:..+@@@*..:@@+..+S,.,S@@@@@@:..+@#*,.,%@S,..*#@#+..,S@S,..%@@:.,,.+@*..;@@?..,?#@@S#@@@@@@#;..*@@@@@@@@@
@@@@@@@@@@@@@@@:..+@@S;,..,;*%@@@@@@@@@;..;@@@@#:...,.,...:@@%..,S@@*,...:;?#@@@@@S...%@S;;;;*@@:..+@@@?..:@@@+.,:.,%@@@@@@@:..+@@@:..+@*..,#@@@#,..?@S,..%@@:.,*,.*?..;@@:..+@@;;;;+@@@@?,.:S@@@@@@@@@@
@@@@@@@@@@@@@@@:..+@@@@#%*;...?@@@@@@@@;..;@@@@#:..;?**:..:@@%..,S@@@#S?+:..:#@@@@S,..*@#+:..;@@;..+@@@*..;@@@@;..,%@@@@@@@@:..+@@S,..*@?..,S@@@S,..%@S,..%@@:..%%,.;,.;@@:..;@@+;..,#@@@*++#@@@@@@@@@@@
@@@@@@@@@@@@@@@:..+@@%;+?%?,..*@@@@@@@@;..;@@@@@:..*@@@+..:@@%...S@#+;*%%+..,#@@@@@*,..+?%+..;@@?..,*%*,..?@@@@?..,#@@@@@@@@:..;?*:..;#@#;..:?%*,..;@@S...%@@:..?@%,...;@@%,..;?%?,.,#@@#;:;S@@@@@@@@@@@
@@@@@@@@@@@@@@@;,,+@@*:,...,;?@@@@@@@@@+,,+@@@@@:,,*@@@+,,;@@%,,,S@S;:,..,:+S@@@@@@@S+:,..,,;%@@@%;,...,;%@@@@@?,,:#@@@@@@@#:,,,,,:+?#@@@@?;,...,;?@@@S,,,%@@;,,?@@?,,,;@@@#*;,...,:*@@@S,.,%@@@@@@@@@@@
@@@@@@@@@@@@@@@###@@@@@#####@@@@@@@@@@@@###@@@@@###@@@@@###@@@###@@@@@#SS##@@@@@@@@@@@@#SS##@@@@@@@#SSS#@@@@@@@####@@@@@@@@@######@@@@@@@@@@#SSS#@@@@@@###@@@###@@@@####@@@@@@##S##@@@@@@@##@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
;;;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;;;:::::::::::::::::::::;;;;;;;;;;:::::::::::::;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;++++
::::::::::::::::;S*.......+%:,....,*%,......,S+,,:;*%+:,..........,:*S##+.......+#SS:.......?@*.............%S:....;%;.....,%?%?,.....*%+?*:,,........,,:;?*,+S,......,S#?.......;S;....................
:::;;;::::::::::+S*.....,.+S;,,...,*%,......:S?;+*%S;......:?*,......+#@%,......:##S......,,S@*.......,,,,::%#?;,..,*%:.,...*#S;...,.;S*%*,.....,*%;......,%?*S,......,S#?.......;S;....................
::::::::::::::::+S*.......+S;,,...,*%,......:#%???#?.......+@@;......,%@#;......,%@*.......;##*.......+#%%%%%%%?+,..,?%,.,..:#S,....:S?*%:.,....,S@?.,.....+S?S,......,S#?.......;S;....................
;;;;;;;;:::;;;::+S*.......+S;,....,*%,......:#S??%#?.......+@#:.......%##*,.....,%@+......,?##*.......*#S%%%???%%*:,.:%*...,,?+....,%?:*%,......,S#*.,.....+S?S,......,S#?.......;S;....................
;;;;;;;;;;;;;;::+S*.......+S;,...,,?S,......:#S%%%#?.......+@@:.......%##S,......*#:......,SS#*......,:;;;;+S%??%%?:.,+S;...,,,....*S:,*S,......,S#*.......+S?S,......,S#?.......;S;....................
;;;;;;;;;;;;;;::+S*.......+S;,,,,,:?S,......:#S%%%#?.......+@@:.......%#S#;......;#:......;#S#*............:#%????%%;,,*S:.,......;S+,,*S,......,S#*.......+S?S,......,S#?,......;S;....................
;;;;;;;;;;;;;;::+S*.......+S;,,,:;+%S,......:#S%%%#?.......+@@:.......%#%#?......:*,......?#%#*.......:++++*S??????%%+,:%?,......:%*,.,*%,......,S#*.......+S?S,......,S@?.......;S;....................
;;;;;;;;;;;;;;::+S*.......+S;::;+*?SS,......:#S??%#?.......+@@:.......%#?%S:.....,+......:SS%#*......,*#%???****????%%*:;S;......*S:..,*S,......,S#*.......+S?S,......,S@?.......;S;....................
;;;;;;;;;;;;;;::+S*.......+S;:+???%#S,......:##%%%#?...,...+@@;......,%#?%#+.....,,......+#??#*.......+#%%%??****????%%?*S;......*%:..,*%,......,#@*.......+S?S,......,S@?.......;S;....................
;;;;;;;;;;;;;;::+S*.......+S*?%%?%%#S,.....,,:;::+#S:..,,.,:%%:..,,..;#%??#%,............?#??#*.......,:;;;;*S?****????%S#;......*%:...;S+......,?S+.,....,%?+%+.....,,?S+,.....,*%:....................
;;;;;;;;;;;;;;:;+S*.......+#%%%%%%S#S,...........:##%;,............,+S%?*?%#;...........:#S??#*.............+#?*****????S#;......*S:...,+%*:,...........,:??:,+%+:,...........,:*?;,....................
;;;;;;;;;::;;;::+%?;;;;;;;?#S%%%SSS#S;;;;;;;;;;;;*S%%SS?+;;::::;;*?%S?*****S?;;;;;;;;;;;*S%??%?;;;;;;;;;;;;;*S?******???%S*;;;;;;*?,....,:+**+;;:::::;+***;,..,:+**++;;::::;;+**;,......................
:::::;;;;:;;;;:;;;+++++*%SSS%%%SSSSS%S##SS%%%%%SS%??%%%%%SSSSS%%%%???****+**??????%%???%?++*?**????%%%***????*********???%%SS?+;;:,,.......,,:;++++++;;:,........,,:;;++++++;:,,........................
;;;;;;;;;::;;;;;;::,::;?%%%S%SSSSSS%SSSS%?????%%???%%???%%%%%%??%??%%*****??****+++*+++*?+++*?*++++*?*+;;;++***********??????*;,........................................................................
;;;;;;;;;;;;;;;;:::::+?%SSSSSSSSSS%SS#SS%%???%S%?%S%%?%%%%%%???%?*?%%***????????**???***??***??*****???*++;+**************+;:;++:,......................................................................
;;:;;;;;;;;;;;;:::;;+%SSSSSSSSSSSSS###SSS%%%%S%?%SS%%%%%%%???**??**%%?*???%?????????%?**?%?**?%?*?***%?***+;+*******++;:,,,,::;;+;,.....................................................................
;;;;;;;;;;;;;;:::++*%SSSSSSSSS##SS#S#SSSS%%%S%%%SS%%%%%%????*:++?**%%?????%%?%%%%%??%????%????%%????*?%?***;;++;;;::,,,..,,,,::;;+;:....................................................................
::;;;;;;;;;;;::;+*?%SSSSSS######S####SSSS%%SS%%%%%%%SS%??%?+,,*;?**?%%????%%?%%%%%%%%%???%????%%??????S%?**+:,,,,........,.,,,:::;++:,..................................................................
;;;;;;;;;;;::;+*?%%S###SS############SSSS%%#S%%%%SSSS%%?*+;:::*;????%%???%%%%?%%%%%%%%%??%????%%%?????%%???*;,.............,,,,,::;;+;,.................................................................
;;;;;;;;;;::+*?%%SS##################SSSS%S#S%%%SSSS%?*;:,.,,,*;+%%%%S%???%%%%%%%%%%%%%??%%???%%%%????%S%??*;:...............,,,,::;;++:,...............................................................
;;;;;;;;;;+++*SS%SS#################SSSSSSS#S%%%SSSS?*+;;::,,,:;:*S%SSS%??%%%S%?%%%?%%S%?%%????%S%????%S%??*;:...............,,,,,:::;++:,,,............................................................
;;;;;;;+**+;+?SS%SS#################SSSSSSS#S%%%S#S%S###SSS?+;::::*%SSSS%%%%%%S%?%%??%%%?%%????%S%????%S%%?*;:................,,,,,:::;;+;,.............................................................
++++++******?S##SS##################SSSSSSS#S%%SSS+;S#SS######%*;::;?SSSS%%%%%%S%%%%??%%%%%????%SS????SS%%?*;:,.................,,,,,::;;++:,...........................................................
******??????%S##SS##################SS#SSSS#SS%SS%:;%?%SSS#SS?*?%+:::+%%SSS%SS%%SS%%%%%%%%%????%SS???%SSS%?*;:...................,,,,,:::;++;,..........................................................
?????????????S##SS##################SS#SSSS##S%SS?::++;++?%?;:::+;:,,,:+??%SSSS%%%SSSS%%S%%???%SSS???%SS%??+;:....................,,,,,:::;;+;:.........................................................
%????????????%##SS###################S#SSSS##S%SS?;::;++;;::,:::,:,,,,,,;+++??%SS%?%SSS%SS%???%S#S%??SSS%?*:,,......................,,,,,::;;++:,.......................................................
%%%%%%%%?????%S######################SS#SSS##SSSS?;:::::::::,:,,,,,,,,,,,:;;+?SS##S%%SSS%%%??%S##S??%SSS%?+,,........................,,,,,::;;++;,......................................................
????%%SSSSSSSSSS#####################SS#SSSS#SSSS%;::::::::::::::,,,,,,,,,,+%S%SSS%+:;?#SS%?%S###%??S%SS%?;,,.........................,,,,,:::;;+;:.....................................................
????????%%%SSSS#######################SSSSSSSSSSSS*:::::::::::::::,,:::::::++++++;:::;***%%?%S##S%%%%*S%%?:,..........................,,,,,,:::;;++:,...................................................
?????????????%%%SSSSS##################SSSSSSSSSSSS;,::::::::::::::::::::::;;;:::,,,:+*%SS%%S###S%%%*%?%?:,..............................,,,,,:::;+++:..................................................
????????????????%%?%%SSSSS#SS##########SS#SSSS#SSS%*:::::::::::::::::::::::::::;:::;*S##S%%S####S%%?%*+;,.................................,,,,::::;*%?;,,...............................................
??????????????????%??%%%%%%%%#######%%####SSSS###SS*+;:::::::::::::::::::::::::::;?S####SS######SS%S*,,...................................,,,,,,:;*?%%%+,,,.............................................
%%%%%%%%%%%?%??%???%%?%%%%%?%S#S%%%%%?S####SSS%S###S+:;::::::::::::::::::::::::;?S#####%S#######S?*;,......................................,,,,;+*???%%%?;,.............................................
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S#S%???%??%####SSS%S###S+::::::::::::::::::::;;+?%######S?%#####S%+:,.......................................,,::++*??????%%%%+,............................................
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%S%%%%%%%%%S#####SS%SS##S*;:::::::;;;;;++**?%SS########%*%#####?:.....................................,,,,::;++******?????%%%%*:,,.........................................
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%SSS#####S%%%S##S%*++**?++**%SSS############S?*%####?:,..................................,,,::;;++***********??????%%%%;,.........................................
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%SSSSSSSSSS%%S###S%%??%S#S%?%%%%%*??*SSSSS##########?+?###?:............................,,,,,,:::;++++*****************??????%%%*:........................................
%%%%%%??%???????%%%%%%%%SSS########SSSSSSS%SS###S%%???%SS%???%%%+%%?S%%%#########?+%#S?:,.....................,,,,,,:::;;;+++++++********************???????%%%?;,,.....................................
%??????????????%%%SSS#################SSSSSSS####S%%%%%%SS%%%%%%?*%????%########%*%?;:,.......,,,,,,,,,,,::::;;;;+++++++++++++++++*+++*****************??????%%%%+,.....................................
????????????%%SSSSSSSSS%%%%%%%%%%%SSSS###SSSSS#S###SS%%%%S#S%??*?**?%??S####S%SS??*;;;;;;;;;;;;;;;;+++++++++++++++++++++++++++++++++++++****************???????%%%?;,...................................
???????%%%%SSSSS%%%%%%%%%%%%%%%%%%%%%%%SS%???%%%?%%S%?****%#%+;+*?*??%?%###S?*?********************+*++++++++++++++++++++++++++++++++++++****************????????%%%+,..................................
?%%%%%SSSSSSSS%%????%%%%%%%%%%%%%%%%%%%%%*++++++++*?%%?*+;+%#%+++??*???%##S???*?**************+++++++++++++++++++++++++++++++++++++++++****+***************???????%%%*:.................................
+*?%%SSSSSSS%%%?????%%%%%%%%%%%%%%%%%%%%?+;;;;;;+++++**???**%#*;;+%***?S##%???*?**************+++++++++++++++++++++++++++++++++++++++++****+***************????????%%%?;,...............................
;++*%SS%%S%%???%???????%%%%%%%%%%%%%%%%%?+;;;;;:;;;;;;;;;;;;+S*;:;??*+?#S%??????**************++++++++++++++++++++++++++++++++++++++++++++*+*****************??????%%%%%*:,.............................
;+*%S%%%%%%%????%%%%%%%%%%%%%%%%%%%%%%%%?+;;;;;;;;:::::;;;;;;?*;++*?*+*#S???????**************++++++++++++++++++++++++++++++++++++++++++++*+******************????????%%%?;,...................,,,,,,:::
;+%%%%%%?????????????%%%%%%SSS%%%%%%%%%%%*;;;;;;;;;;;::::::::+;;;;+??**S%???????***************+++++++++++++++++++++++++++++++++++++++++++*+********************???????%%%?;,........,,,,,,:::;;++++++**
:?%%%%%%%%%%?????????%%%%%%%%%%SSSSS%%%?%?+;;;:;;;;;;;::::::;;:::::;?*+%S%???????**************++*+++++++++++++++++++++++++++++++++++++++++++*++******************????????*++:,,:::;;;+++++*************
;%%%%%%%%%??????**????????%%%%%%%%%%SSSSSS*++;;;:;;;+;;:::::::::::::;?*?%%??????***************++++++++++++++++++++++++++++++++++++++++++++++*++*******************??????+;;+++++*************+*********
+%%%%%%%%%%???********???????????%%%%%%%%S%*+;++;;:;;+;::::::::::::::+??%%?????******************++*++++++++++++++++++++++++++++++++++++++++++++*********************??*;::;;;+*************++++********
?%%%%%%%%%%?*******?????%%%%%?***??????%%%%%*;;;;;;;;;;;::::::::::::::*?%%?????******************++*++++++++++++++++++++++++++++++++++++++++++++**********************;:,:::;;;++***********+*++********
%%%%%%%%%%%?********??????%SSSS%??****?????%%?+;;;;;;;;;::::::::::::::;?%%?????********************++++++++++++++++++++++++++++++++++++++++++++++*****************++:,,,,,::::;;++**********************
%%%%%%%%%%%%?*******????????%SS#S%%???***?*?%%*+++;;;;;;::::::::::::::;?%%?????********************+++++++++++++++++++++++++++++++++++++++++++++***************++;:,,,,,,,,,:::;;++*********************
%%%??%%S%%%%??*****????????????%S##SS%%?????%S%+++;;+;;:::::::::::::::;*%%?????********************+++++++++++++++++++++++++++++++++++++++++++++***********++;:,,,...,,,,,,,,:::;;;++*******************
%%%???%SS%%%%??****??????????????%S###SS%%?%SS%+++;;;;;::::::::;;;;;::;*%%???????*****************+**++++++++++++++++++++++++++++++++++++++++++++******++;::,,..........,,,,,,,:::;;;+******************
??????%SS%%%%%??*****???????????????%S###S%SSS%+++;+++;:::::::::;;;;::;*%%??????********************++++++++++++++++++++++++++++++++++++++++++*+**+;::::,,,,,,,,........,,,,,,,::::;;;++****************
???????%SS%%%%%???***??????????????????%S####S?+;++++;::::::::::;;;;::;*%%?????***********************++++++++++++++++++++++++++****++++++********?*;:..,.,,,,,,,,,.......,,,,,,,::::;;++**********++***
????????%SS%%%%%??****????????????????????%SSS?++*++;:::::::::::;;;;::;;+**?????***********************++++++++++++++++++++++*?????%??*************???;,,.,,....,,,,,,,,....,,,,,,,:::;;;++********+++*+
?????????SSS%%%%%??*****?????????????????????%%?*+++;::::::::::;;;;;::;;;;:;++*******************+++++*+++++++++++***********?%%%%??%%?**************??+,,,.....,,,,,,:,,...,,,,,,,,::::;;++*?*+***++++*
?????????%SSS%%%%%???******????????????????????%?++;:::::::::::::;;;::;;;;:::,,,::;;++++++***+*****+****+++++****************?%S%%????%?*************???+,......,,,,,,,,,,,,,..,,,,,,::::;;;+??**+*++++*
%?????????%SSS%%%%%%???*******????????????????????+:::::::::::::::;;::;;;;:::,,,,,,,,,,,,,,,:::::::::::::;+**??***************%S%%%????%??????????????%??;....,,,,,,,,,,,:::::,,,,,,,,,:::;;+?%?***+**++
%%???????*?%S#S%%%%%%%??***************????????????+::;;;;;::::::::::::;;;:::,,,,,,.,,..............,:;+***?*****************?%S%%%?????%%%%????????????%*,.,,,,:::::::,:::;;;;:,,,,,,,,::::+?%%??*+*+++
%%%??????**?S##S%%%%%%%???*************************?*+;;;++;:::::::::::;;;:::,,,,,,............,,:;+*???*?******************?%%%%%%?????%%%%?*****???????*:,,,,,,,,,:::::::::;;;:,,,,,,,,,::*??%%%?***++
?%%%????**?%%SS#S%%%%%%%????***********************???*;;+;;;::;;;;;++;;+;:::,,,,,,.........,,;+*????????%%%%????**********?%%%%%??***?%%%%%?*******?????*;;;:::,,,,::::;;:::::::,,,.,,,,,:+?????%%?**++
??%%%????%??*?SS#SS%%%%%%%???**********************???%*++;;;;+++++++++++++;:,,,,,,.......,:+*????????%%%%%%%%%%%%????????%%%????****??%%%%%%?******??*+;:,,,......,,,,,:::::,,...,.....,;**?????%%%?***
S??%%%%%%??????SS##S%%%%%%%?????******************??%SSS%??*+++++++++++;;;++:,,,,,,.....,;*???????????????%%%%%%%%%%%%%??%????******???%%%%%%????*+;:,,..............................,,:+*??????????%?*+
%%??%SS%????????S###S%%%%%%%????***************?%%SSSS%%%%?????*++++++;:;++**+;,,,,..,:*??????????????????%%%%%??%%%%%%??????******?%????%%%?+;:,,.................................,,:+********???????*+
%??*%%%%%????????%S##S%%%%%%%???***********??%%S%%%%%???%SS%?***?**+++;+**???%%?*+::;*%%?????????????????%%%%%%%%%%%%?????????****????????*;,....................................,:;+***********??????*+
;;*?????%%%???????%S##S%%%%%%%?******?????%%%%?????????%%##S??***?????????%%??%%SSSSS%??????????????????%%%%%%%%%%%%%??????????**?????%??+,..................................,,,:;+****************??**+
;;+??????%%%%??????%S##SS%%%%%%?***??????????????????%%%%###%???***?????%SS%?%%SS#S%????????????????????%%%%%%%?????%??????????????%??*;:,,...............................,,,:;+**********************++
;;;**??????%%%%?????%S###S%%%%%????????????????????%%%%%%###S%????????%SSS%??%S#S%?????????????????????%%%%%%%?????????????????????*;:,..............................,,,,:;++************************+++
;;;++??????%%%S%??????%S##S%%%%%%%%%?????????%??%%%%%%%%S###%%%%%%%?%S###S%%%SSS%?????????????????????%%%%%%%%???????????????%%%?;,,..............................,,::;+++***************************+++
;;+++**?????%%%SS%?????%S##SS%%%%%%%%?%%%%%%%%%%%%%%%%%%S##S%%%%%%%%S####SSSSS%???????%%%????????????%%%%%%%?????????????%%%?*+:,...........................,,,,:;;+++***++************************+++++
+++++***???%%%%%%SS%%????%S##S%%%%%%%??%%%%%%%%%%%%%%%%%S##%%%%%%%%S####SSS%%????????%SS%??????????%%%%%%%%%?????????%%%??*;,,........................,,,,::;;++++***+++*+++*********************+++++++
****?*?*??%?%%%%%%SSS%%???%S###S%%%%%%??%%%%%%%%%%%%%%%S###%%%%%%%S####SS%%?????????%SSS%??????????%%%%%%%??????%%???*+;:,.....................,,,,,::;;++++++++++++++++****+******************+++++++++
***++++;;+*??%%%%%%SSSSS%???%S###S%%%%%%?%%%%%%%%%%%%%%S##S%%%%%%S####S%???????????%SSS%%?????????%%%%%%%????%?*+;:,,.................,,,,,:::;;;++++++++++++++++++++++++++*+++*************++++++++*+++
;;;::;;;;;;+*??%%%%%%SSSSS%???S###S%%%%%%%%%%%%%%%%%%%%S##S%%%%%S###S%????????????%SSS%%%????????%%%%%??????*+:,...,,,,,,,,,,,,:::::;;;;+++++++++++++++++++++++++++++++++++*++***+*******+++++++++++++++
:::;;;;;;;+++**???%%%%%%SSSS%%?%S###S%%%%%%?%%%%%%%%%%%##S%%%%%%S##S%????????????%SSS%%%????????%%%%%????*+;;;;;;;;;;;;;;+++++++++++++++++++++++++++++++++++++++++++++++++++++***+++++++++++++++++++++++
:::;;;++****+++++*???%%%%%%SSSS%%%S###S%%%%%%%%%%%%%%%S##S%%%%%S#S%????????????%%SSS%%%????????%?%%%%??**++*****++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
;;++*****+++;;+++++**???%%%%SSS#SS%SS##SS%%%%%%%%%%%%%S#S%%%%%%SS%????????????%SSS%%%%?????????%%???**+****++*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+***++++;;;;;;;++++++++***??%%%SS##SS####S%%%%%%%%%%%SSSS%%%%%%%?????????????%%%%%%%????????????***++++*****++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++;;;++;;;;;;;;+++++++++++++***??%%SS######S%%%%%%%%%SS%%%%%%%%????????????%%%%%%%??????????*****************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
;;;;;;+++;;;;;+++++++++*************??%%SS###S%%%%%%%%%%%%%%%%???????????%%%%%%%%???????*******************+**++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++;;++++++++++
;;;;;;;++++;;++++++++++++++++***********??%SS##SS%%%%%%%%%%%%??????%%%%%%%%%%%%??%%%%??******************++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++;;;;+;+++++++++++
;;;;;;;;;;+++++++++++++++++;;;;;++***?%%%%%%%%S%%%%%%%%%%%%%%%%%%%%%%%%%%?%??????????????????********************+*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++;+;+;;++++++++++++++
;;;+++;;;;;+++++++++++++++*****??%%%%%???****++++++**??%%%%%%%%%%%%%%%%???**++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++;;;;+++++++++++++++++++
;;;;;;;;;;;;;++++++++++**????%%%??***+++;;;;;;;;;::;;;;;+++****????***++;;;;;:::;;;;::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;+;;;+++++++++++++++++++++++++++++++++;;;;;;;;;++++++++++++++++++
;;;;;;++++++;;;;+++**?????%??*++;;;;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;+++++++++++++++++++;;;;;;;;;;;;;;;++++;+++++++++++++
;++++++++++++++**?????%??*+;;;;:::::::::::::::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::::::::::::::::::;;;;++++++++;;;;;;;;;;;;;;;;;;+;;;;++++++++++*+***
;;;++++;;+++*??????%%?*+;;::::::::::,,:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::;;;;;+++++;;;;;;;;;;;;;;;+++++*********???
+++++;;+**??????%%?*;;:::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::::::::::::;;;;+++;+++++++*****?????????????
++;++*???????%%?*;:::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::::::::::::::::::::::::::::::::::::::::::;+****??????????????????????
;;+*??????%%?*+;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::::::::::::::::::::::::;*????????????????????????
+???????%%?+::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::::::::::::::::::::::::::::::;*??????????????????????
??????%%*;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::,,,:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::,,,,,,,:::::::::+*?????????????*****++
?%??%?+;:::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;:::,,,,,,,,,,:::::::::;+??****++;;;::,,,,,,
%?%?+::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;::;;;;;;;;;;;;;;;++;;;;;;;;;::::,,,,,,,,,,,,,,,,,,,::::::::+:,,,,,............
?%*;:::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;+++++++++;;;:::::,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::;,.................
%+::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;++++++++++;;;::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::;,.................
*:::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;+++++++++++;;;:::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::;:..................
:::,,,,,,,,,,,:,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;+++++++****++;::::::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::;;,..................
:::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;;;;+++++++****++;;::::::,::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;,...................
::,,,,,,,,,,,,,,,:,,,,,:,,,,:::::::::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;;;;;;;+++++++*****++;::::::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::,,....................
,,,,,,,,,,,,,,,,,,,,,::::::,,:,:::::::::::::::::::::::::::::::::::::::::::::;;;;;;;;;;;;;;;;;;;;;;++++++********+;:::::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::;;:,......................
:::::,,,::::::,,:::::,::::::::::::::::::::::::::::::::::::;;;;;:::;;;;;;;;;;;;;;;;;;;;;;;;;;;+++++*****???***+;::::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:,,,,,:::::;;;;:,,......................
******++******?******+;:::+**?****?**;::::::;**?????**+***????*****???????*??????????????*+*????%%%%??%?????***+:,,,,,:+**********+::+******+:,,,:+***************++******????*****+++++********++:,....
,,,,,*##;,,,,,S+,,,,;S*:+??;:,,,,,,:+??+:::;?%:,,,,,,%#S:,,,,,,?#S,,,,,,,,,S#;,,,,,,,,::;?SS%,,,,,*S?S*,,,,,,,;S+:,,,,+S;,,,,,,,::;?%S:,,,,+S;,,:*S:,,,,,,,?#:,,,:S#?,,,,?@;,,,,,,,,*@?,,,,,,,,::;?*:...
,....;@S,....;#;....:S*;%?,..,,%?,...,%%;::;?S,......+@?.......?@S,....:+++S#;....:?+....,S@S,....*S%S:..,:,..,%%:,,,,+S;....:?:...:##:....;S+,,;%?,..,:,..;@%,..,%@;...;##;....,++;*#?.....*?,...,%*,..
+....:#?,....*@;....:S*+S+....,#S.....*S+::;?S,...,,.:S;.,:....?@S,....*@S%%#;....:@%.....?@%,....*SS?,..,;:.,.+S+,,,,+S;....;#;...,##:....;S+,:+S;...,+,..,%@*...+%,..:%%S;....:#S*+%?.....%@,....%?,..
%,...,S*....,S@;....:S*+S*....,SS+++++??;::;?S,...+;.,+,.:+....?@S,....,;:+##;....:#?.....?@S,....*#S+..,,%*.,,,%?:,,,+S;....:+,...:##:....;S+::?%,...;S:,,.+##+..,:,.,%?+S;....,:::%#?.....;;,,,:+%;,..
#;....+;....;##;....:S*+S*....,SS%%%%%*+;::;?S,...+*..,,.+*....?@S,...,:;:+##;....:#?.....?@S,....*#S:...,S?,.,.+S;,,,+#;....,,::;+?SS:....;S+:;S*....+@;.,.,%SS:.....*%:;S;....,:::%#?.....;;,,,;?%;...
#*....;:....*##;....:#*+S+....,SS,,,,,*%;;:;?S,...+%,...,%*....?@S,....*#?*?S;....:@?.....?@%,....*@?,...,++,.,.,S*:,,+S;....:S%**+;*S:....;#*;*S;....;*:..,.*SS*....:S+,;S;....;#%+;%?.....%#,...,%?,..
SS,...,,...,SS#;....:??*#*....,S%.....?%;:;;%S,...+#;.,.:#*.,..?@S,....+%?*?#;.,..:S*.....?#%,....*@+...,,::,....?%:,,+S;....:S+:,,:*S:....;%?*S%,...,:::,...:##?....:S+,;S;....:??*+S?.....%#,....%?,..
%#+........+#S#;.......,S#+,...::..,:*S?+++*SS,...+@*...;@*....?@%,........+@;....,,,....:%S%,....*S,....*##+....;S+,,+S;....:S+::::*S:.......,#*....,S#%,...,?@?....:S;.;S;........:#?.....%#,....%?,..
%SS********%#S#?********S##S?*++++*?SS%?????%S****?#S***S#%****%SS*********?#?*********??%?*%*****%S*****%%%?*****%*;;+%?****?%*;+;+*S?********#?****?S%%*****%#S*****%+:;%?*********S%*****%S*****%*:::
*/
void setIO(string s = ""){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
if (!s.empty()){
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
}
const int N = 501;
bool adj[N][N];
int dp[N][N][2], dp1[N][N][2], nx[N][2];
void calc(int u, int v, int dir){
if (adj[u][v]){
dp[u][v][dir] = 1;
dp1[u][v][dir] = 1+dp1[v][nx[u][dir]][dir^1];
} else {
dp[u][v][dir] = dp1[u][v][dir] = -N;
}
for (int k = nx[u][dir]; k != v; k = nx[k][dir]){
dp[u][v][dir] = max(dp[u][v][dir], dp[u][k][dir] + dp[k][v][dir]);
dp1[u][v][dir] = max(dp1[u][v][dir], dp[u][k][dir] + dp1[k][v][dir]);
}
dp1[u][v][dir] = max(dp1[u][v][dir], dp1[u][nx[v][dir^1]][dir]);
}
int main(){
setIO();
int n, cross;
cin >> n >> cross;
memset(adj, 0, sizeof adj);
for (int i = 0; i < n; i++){
int x;
for (;;){
cin >> x;
if (!x) break;
adj[i][--x] = 1;
}
nx[i][0] = (i+1)%n;
nx[i][1] = (i+n-1)%n;
}
for (int len = 1; len < n; len++){
for (int i = 0, j = (i+len)%n; i < n; i++, j = nx[j][0]){
calc(i, j, 0);
calc(j, i, 1);
}
}
pair<int, int> ans = {0, -1};
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
for (int k = 0; k < 2; k++){
ans = max(ans, make_pair(dp1[i][j][k], i+1));
}
}
}
if (cross){
for (int b = 0; b < n; b++){
for (int c = 0; c < n; c++){
for (int dir = 0; dir < 2; dir++){
int a = nx[c][dir];
while (a!=b && !adj[a][b]) a = nx[a][dir];
if (a == b) continue;
for (int d = nx[a][dir]; d != b; d=nx[d][dir]){
int tmp = max(dp1[d][nx[a][dir]][dir^1], dp1[d][nx[b][dir^1]][dir]);
ans = max(ans, make_pair(2+tmp+dp[b][c][dir], a+1));
}
}
}
}
}
cout << ans.ff << '\n' << ans.ss;
}
Compilation message
race.cpp: In function 'void setIO(std::string)':
race.cpp:265:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
265 | freopen((s+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:266:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
266 | freopen((s+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
860 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
1116 KB |
Output isn't correct |
| 7 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 8 |
Incorrect |
3 ms |
2908 KB |
Output isn't correct |
| 9 |
Correct |
3 ms |
3044 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1372 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1372 KB |
Output is correct |
| 12 |
Correct |
48 ms |
3460 KB |
Output is correct |
| 13 |
Incorrect |
155 ms |
3672 KB |
Output isn't correct |
| 14 |
Correct |
203 ms |
3672 KB |
Output is correct |
| 15 |
Incorrect |
779 ms |
4700 KB |
Output isn't correct |
| 16 |
Incorrect |
738 ms |
4700 KB |
Output isn't correct |
| 17 |
Incorrect |
735 ms |
4720 KB |
Output isn't correct |
| 18 |
Correct |
395 ms |
4444 KB |
Output is correct |
| 19 |
Incorrect |
790 ms |
4780 KB |
Output isn't correct |
| 20 |
Incorrect |
790 ms |
4700 KB |
Output isn't correct |
