/* __----~~~~~~~~~~~------___ . . ~~//====...... __--~ ~~ -. \_|// |||\ ~~~~~~::::... /~ ___-==_ _-~o~ / ||| \ _/~~- __---~~~.==~||=_ -_--~/_-~|- |\ \ _/~ _-~~ .=~ | \-_ '-~7 /- / || / .~ .~ | \ -_ / /- / || / / ____ / | \ ~-_/ /|- _/ .|| / |~~ ~~|--~~~~--_ ~==-/ | ~--===~~ . ' ~-| /| |-~~~ __--~~ |-~~-_/ | | ~\_ _-~ / / \__ /~ \__ _--~ _/ | .-~~____--~-/ ~~==. ((->/~ '.|||' -_| ~~-/ , . _|| -_ ~ ~~---l__i__i__i--~~_/ _-~-__ ~) --______________--~~ //.-~~~-~_--~- |-------~~~~~~~~ //.-~~~-- */ #define _CRT_SECURE_NO_WARNINGS #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<bitset> #include<cassert> #include<cctype> #include<cmath> #include<cstdlib> #include<ctime> #include<deque> #include<iomanip> #include<list> #include<map> #include<queue> #include<set> #include<stack> #include<vector> #define lt k << 1 #define rt k << 1 | 1 #define lowbit(x) x & (-x) #define lson l, mid, lt #define rson mid+1, r, rt using namespace std; typedef long long ll; typedef long double ld; #define fin freopen("in.txt", "r", stdin); #define fout freopen("out.txt", "w", stdout); #define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define mem(a, b) memset(a, b, sizeof(a)) //#define int ll const double pi = acos(-1.0); const double eps = 1e-8; const ll mod = 1e9 + 7; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; const int maxn = 2e5 + 500;