#pragma once
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>usingnamespacestd;usingnamespace__gnu_pbds;usingll=longlong;usingdb=longdouble;usingvi=vector<int>;usingvl=vector<ll>;usingvd=vector<db>;usingpii=pair<int,int>;usingpll=pair<ll,ll>;usingpdd=pair<db,db>;constintINF=0x3fffffff;constllLINF=0x1fffffffffffffff;constdbDINF=numeric_limits<db>::infinity();constdbEPS=1e-9;constdbPI=acos(db(-1));template<classT>usingordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;mt19937rng(chrono::steady_clock::now().time_since_epoch().count());mt19937_64rng64(chrono::steady_clock::now().time_since_epoch().count());