Here is my template for CP (might change) ~~~~~ //>w< //>w< //>w< //>w< //>w< //>w< //>w< //>w< //>w< //>w< //>w< //>w< //>w< //>w< //>w< //>w< //O.o //owo //OwO
pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")
include <bits/stdc++.h>
include <ext/pb_ds/assoc_container.hpp>
include
define ll long long
define ld long double
define namein "input.txt"
define nameout "output.txt"
define all(x) x.begin(),x.end()
define fi first
define se second
define pb push_back
define matrix vector<vector>
define query pair<ll, pair<ll, ll>>
define fr(i, j, n) for (ll i = j; i <= n; i++)
using namespace std; using namespace std::chrono; using namespace __gnu_pbds; const ll mod = 1e9 + 7; const ll inf = 7e18; const int linf = 2e9; typedef tree<ll, null_type, less_equal, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
void boost(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
void file(){ if (fopen(namein, "r")){ freopen(namein, "r", stdin); freopen(nameout, "w", stdout); } }
const bool track_time = 0; const ll N = 1e6 + 5;
define NO cout << "YES\n"
define YES cout << "NO\n"
void ans(){
}
int main(){ boost(); file(); auto start = high_resolution_clock::now(); ans(); auto stop = high_resolution_clock::now(); auto duration = duration_cast(stop — start); if (track_time) cout << "Runtime: " << (ld)duration.count()/1000 << " ms"; }
//waifusinanotherrealm //waifusinanotherrealm //waifusinanotherrealm //waifusinanotherrealm //waifusinanotherrealm //waifusinanotherrealm //waifusinanotherrealm //waifusinanotherrealm //waifusinanotherrealm //waifusinanotherrealm //waifusinanotherrealm //waifusinanotherrealm //waifusinanotherrealm
/*
++++++***#@*--------------------------=---------------------------------------=----------------==----=--%+++++++++*#***++++++++*# %@@@%##+---------------------------#----------------------------------------+=-=-------------=+----+--%+++++++++++++++++++#
******+-:-------------------------=----------------------------=--------------+-*-------------=+--::=-=*#+++++++++++++++++**
++++++++=-:--------------------------#-------------------------------+------------+=*--------------+--::=-+++++++++++++++++++*#%% +++++++*-:--------------------------=+---------------------------------=+----------=**-------------=+--::=-+++++++++++++++++**#%# ++****%-:---------------------------=-------------------------------------+=----::---**--------=----==---:-#++++++++++++++**#%#*+ ++***%--:-+=------------------------+---------------------------------------==---::---=+---::---+----=---::-=*++++++++****#%%%*== ++**#=-:--+---==--------------------+-:----------------------------------------=---:::--+----:---+----*--:::::-+**++**#%%%%##*+== +*+*#-:--=----+----------------------:-------------------:--:----------:--+------*---:::-+---::--=+----=--:::::::--=+*#*#%%%%%##+ #-::-----=*-------*-------------:::-------------------::-::::::::::::--#=--:--+*=--::-==-:::--++---+=--::::::----=*%@@@@@@@%% **+#-:---+---++------==--------------::------------------:--:::::--:::::::--+=-::-=++*--::--=-::--++=---++--:::::::=%@@@@@@@#*+++ #=::--%=---*+------%-----=---------+:-----:-------------:::--::-----::::--*++-::-=+++*--::-=-::-=++---##++--:::::::--=+++++*=== #-:--=@=--=*+-----++----*----------=------:----------==--::-=--::-=--::::-===+-:--+#+++*--:-=::-=++=---++#++=---:::::::---++=== #-:-=%@=*-+*+----=#=----=-----------=------:-----::---*+--:--*--::-+=-:::--=-=+---=++++++=----:--+++---#++++*#++=========*++=== *#+-:-=@@===+----+#=---+------------*------=-----:::--=*+--:--#--:--+=---+*#*++*--=*#*#*+*+--+---+++=--#==============++*++==== #=::-+#@+==---=*%----#-----+-------#------=---:::::--==---=*=---#*#=---+:::=+--=#-=++*=+--=--++++--++=======+++++%*++++==== %#=::-##@#===--=*#----*-----+=------%---:--=---:-::::--+**+---+++#+=#+=--:=::::==--*--+++=-+=+--++++--++==+%##%%@%**%+++===+++ @%---=@*@#==***=--=*#----+-----+#--::--%*--::--+--:::::::--++#*---#=+--=**---=:::::+--#::-%++--+===++++--*+===+%@@@@*++++++=+++++ #---=%#@#=+**+--=*#----*--:--=#---:--@*=-:::--*--:::::::--++*+-==-==--+#=-+-::.::-*-%:::-*+---*+=+*++--%*+==++**%#+++++++++++++ +#=--=***%=+++**=-=*#=--+*-----=#*--:--#+#------+*--:::::::--+*++--*-*--*-*-=:::.:::*-=::::#*-::=+++*#+-=*--=#@@@%%**++++++++++++ --+%@@=++++*+===--**=--+-=+%=----++=+=+******---::::::--+#=+==--+-*-%*+=----=+#*=-::--%-::-=+*+*+=**::-#@@**#@#+++++++++++# #--+%@=++++++==***--#*=--*+==##=--=*#===----=*=#-::::::::--+#=++=--#++#**@@@%%%%@@@@@+==*-::-++*+*+#+=::-#@#+++%@++++++++++++ @##=-++**@==++++++=++%==##+--=%==**#*=--%--==----+=-=-:--:::::-=**=+*--*#+@@%=--::-=----=*@*=-:-=+#++*#++-:::*==----------------- @@@*=+@**#+=+#+++++++*==**#=--*#+#%=+---==::+-----#+--*:----:::--*%-#::-##=--::::::::::::--+=--=+*+++#++*-:::#==--------------==- @@@@++@###+=+#*+++++++%==*#+--*#%=*+--*--#:::+==--=+::::#--+---:---*=::::::::::::::::::-:-*%=-+#==++++++#-::-#*****+======+**+=== %%%%*=@#*+#=++#*+++++++*=#+#=-#+=*=#-::*-=-:::+=+--+-::::=*-%+-------=*=::::::::-:-:-:--+#*=+#+--=+++++++-::-#++====----------=== ====*=#+++#==+#*+++++++++#++*==#=-++=:::-*+---*#+%==#=#::::-**=++--=%#*+-:::-:--:---:--==#+*-+---=+++++*=-:::*-**+==---------=++* ====+%*#@@@*=++#**+++++++**++*=*=---%-:::-+%#@@@@%%*=#-::::::-+%=--=====-:--:--:---:-:==--:::=:--++++++#--:::*--++======+**#*==-- ++++*%%@@#**-=+#%*+++++++*@*++*+*-:::*-:-+@@%*=---=+-+%-::::::::--*+-::::::--::::::::::::::::+---++++++#-::::*::-*+++**#@@@@#+++= @@@@@%@%##*=+-=*#%*++++++++%*++##-::::-+#@*--::::::::::::::::::::::::::::-:::::::::::::::::::+--=+++++*+-:::-+-::-#%@@@@@@@@@@@@@ @@@@@@@@@%%##==+#+%*++++++++****#*-:::=@@=-::::::::::::::::::::::::::::::::::::::::::::::::::+--=+++++*--:::-+=::-+@@@@@@@@@@@@@@ +%@@@@@@@@@@==*%++*++++++++++*#*%---#@=-:.:::--::---=::-::::-=*-:::::::::::::::::::::::::::+--++++++%--:::-+==::-*@@@@@@@@@@@@@ %*+=+%@@@@@@@@%==#--=#+++++++++++#*+#+=-----------------=:::::-+*+-::::::::::::::::::::::::::=--+++++*+--:::-=-=-::=@@@@@@@@@@@@@ @@@*+*#@@@@@@@@%-+*--+*#++++#*++++*#*++*%%##%=-----=--:--:::::-#*#-::::::::::::::::::::::::::=--+++++*--:::-=*--+::-*@@@@@@@@@@@@ @@@@@@@@@@#*+==-+=++++++*##***##*+***#%**+=--------:::::::::::--%+-:::::::::::::::::::::::::-=-=*++++%--:::-+*+=-+:-=@@@@@@@@@@@@ @@@@@@@@%%###%%%==#**++++++*####*#%#****%#+==----:::::::::::::::::::::::::::::::::::::::::::-+-=++++**--:::-***+--+--*@@@@@@@@@@@ %%%#***+*@#**++++*+#****+*+*+=++*****=*===--::::::::::::::::::::::::::::::::::::::::::::::::-=-=++++*=-::::-****=-=--=@@@@@@@@@@@ +==--------=*#*******##*#*#=-=+++++**--*+-::::::::::::::::::::::::::::::::::---=::::::::::::-=-=*+++%--::::-#*+++=-*-=%@@@@@@@@@@ --::::::::-============%+%+--+*++++**--+*%-::::::::::::::::::::::::::-----=#@%%-::::::::::::==-=*++#=--:::--#+++++===-+@@@@@@@@@@ -:::::--==-----------=%#==*--+*******--=**#+-::::::::::::::::::::--+#%%%#****#--:::::::::::-%+-=***#--::--=-*++++++-+-=@@@@@@@@@@ ----===-----------=-=*===-*--+*******--=****#-::::::::::::::::::-+@%#*++++=++-:::::::::::-=##+-=***+--:--=-=*++++++==+=%@@@@@@@@@ =++=----------============#--+*******--=****##+-::::::::::::::::::--=#*++**-::::::::::::-#++*+-=**#=-----*-+*+++++++=+=+@@@@@@@@@ ==-------=================#-=+*+*****--=*+**##*#=-::::::::::::::::::::--------::::::::-=#+++*+-=***-----=*-***+++++++=*=%%@@@@@%# =----================--===#-=********--=*+**%#***#=-:::::::::::::::::::=##**-::::::::-%+++++++-=+#=-----*+=%#**++++++=+-#======== --------=====-------------#-=********--=*+**%***+**#*=--::::::::::::::::---::::::::-+*++++++++--**-----=*==##**+++++*+=*----:::-- ==---------==========-----%-=+*******--+****%*++++*****##---:::::::::::::::::::::-=%++++++++++=-*-----=**==**#*++++++*=+-*-:::::- =============+====++#+====%--+******+--+*+**#*+++++****=---=#*=--:::::::::::::::-#+++++++++++*==*-----+**-=**%*+++++**+=**--::--- ======+*+++=++=======+#@*+#--+*****#=--+*+**#*++++++**#=----=#++*%+=---:::::::-**++++++++++++*=*-----=**+=***%**+++****=*==:::::: ===========+++=========+++#--=*****#=--+****#*+++++++*%=----==%*++++**#*-----**++++++++++++++*=*-----+**==%***#*+++****+=+*------ =============++++=========#--=******=--+****#*++++++++%==-=+#++#*++++++++++++++++++++++++++++#*=----=***==%#**#**++****+=%*=+%@@@ ===========+*#@%+=========#--=******---+***#**+++++++*#+#@*+++++%++++++++++++++++++++++++++++%+----=+***=+*+*%%*********=+=+=++++ ++*##*++**#@@@*+==========#--=*#**+=---****#**++*****%*#+++++++++#+++++++++++++++++++++++++++*=----=#**=-%++++**%#******==*#----- @@%%@@@@@@@@@#+=--===++#@#%---*#**=---=****%****#@%+++@++++++++++**+++++++++++++++++++++++++%=----=+***==#+++++++**%%***+=%*-:::: @@@%%%%@@@@@@+==-==+%%%%@@@=-=+%**=---=****%##**#*+++%+++++++++++*#+++++++++++++++++++++++++*=----=#**+=*++++++++++#++=#*+*==:::: @@@@%%%%%@@@*+==+*@@@@@@@**--=+%*+=---=****#***%*+++%++++++++++++*#++++++++++++++++++++++++%=----=****==@+++++++++#*====#++*#+=-- @@@@@@%%%%@@%###%@@@@@%=--=--=+%*=---=+***%##*%*+=+*+++++++++++++##++++++++++++++++++++++++*=---=+##*+==*+*++++++#*+*%%@@@@@@@%%@ @@@@@@@@@@@@@@@@@@@@@=-:::-=-=+%*=---=****%####++=+*#+++++++++++*#*+++++++++++++++++++++**%==---=*##*==#***+++++#*#@@@@@@@@@@@%%% @@@@@@@@@@@@@@@@@@@%=::.::-+-=+%+=---=****%##%++==++%*++++++++++*%*+++++++++++++++++++++*+#=---=+###+==%***++++#%@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@%@#-::.::-*#==**==--==***#*#%#++++++*#*++++++++++++++++++++++++++++++++***+=--==*###=-****+==#%@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@#-::::::-#%==#+==--==#**@+=*++++++++%****++++++++++++++++++++++++++++***#+=--=+###*--%=--==%@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@%%%%*#-::::::--+*+=*+=====+####==+=-=+++++*@%#**+++++++++++++++++++++++++++***@==-==####=-=---=#@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@%%#*+++*=-::::::-*+++=*======+###*===+:::-++++*#*#%****+++++++++*****+****++*****#====*###*--#-=%+@@@@@@@@@@@@@@@@@@@@@@@ @@@%%%%%*+====+*-:::--+--%=+#++======*##%+===*-::::-=++%****##****************************====####=-=#+=*@@@@@@@@@@@@@@@@@@@@@@@@ %%#*+++#+=====#---:---*--#++#*=======*##@+===*+---::::-+@*****%*****************##%@%#***+===*###*--=-=*@@@@@@@@@@@@@@@@@@@@@@@@@ ========*+===++-------*-=+++*#======+###%+++*#@@@#=-:::--%*****%#***********%##*******+=#===+####=--+=+@@@@@@@@@@@@@@@@@@@@@@@@@@ ============+#=-------#-=++++@======+##*#*#@@@@@@@*=::::--#+****%*********##********+===%===+####=-==+@@@@@@@@@@@@@@@@@@@@@@@@@@@ ==========+++*--------%==++++%=====+*###*#@@@@@@@@#=-::::--#+#***********@******#*===-==@=++####*--*+@@@@@@@@@@@@@@@@@@@@@@@@@@@@ ===+++++****%=--------#==++++%=====+###%*#@@@@@@@@%+=-::----++**********#*****#*+====*#*%+++####=-=+%@@@@@@@@@@@@@@@@@@@@@@@@@@@@ ===+++++++++#=-------=#++++++%=====+###@#%@@@@%@@@@@#=-------=#*###*******###++==+%+---=#++*###*=-**@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ ====+++++++*+=-------=#%+*+++#+===++###@@@@@@@@@@@@@@+---------+#*########*+##*=-------=#++####+=+%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/ ~~~~~



