#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // istringstream buffer(myString); #include #include #include #include #include #include using namespace std; typedef unsigned long long int ull; typedef long long int ll; typedef pair pi; typedef pair pl; typedef vector vi; typedef vector vvi; typedef vector vpi; struct dbg_ {template dbg_ & operator ,(const T & x) { cerr << x << ' '; return *this;}} dbg_t; struct cin_ {template cin_ & operator ,(T & x) { cin >> x; return *this;}} cin_; template static inline ostream & operator<<(ostream & os, std::pair const& p) { os << "{" << p.first << ", " << p.second << "}";return os; } int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; #define sync ios_base::sync_with_stdio(0) //to synchronize the input of cin and scanf #define inf 2000000007 #define eps 1e-9 #define popcnt __builtin_popcount #define gcd __gcd #define rep(i,n) for(int i=0, _##i=(n); i<_##i; ++i) #define dwn(i,n) for(int i=(n); --i>=0; ) #define repr(i,l,r) for(int i=(l), _##i=(r); i<_##i; ++i) #define dwnr(i,l,r) for(int i=(r), _##i=(l); --i>=_##i; ) #define fora(i,a) for(auto i : a) #define rd(args...) { cin_,args; } #define mp make_pair #define pb push_back #define x first #define y second #define prio(q) priority_queue,greater> q; #define priot(q,t) priority_queue,greater> q; #define opl(T) bool operator<(const T & a, const T & b) #define opg(T) bool operator>(const T & a, const T & b) #define qtop(q) ((tmp=q.front()),q.pop(),tmp) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define has(a,b) ((a).find(b) != (a).end()) #define index(a,x) (lower_bound(all(a),x)-arr.begin()) #define fill(a,v) memset(a, v, sizeof(a)) #define nfill(a,n,v) rep(i,n)a[i]=v; #define clr(a) memset(a, 0, sizeof(a)) #define rda(a,n) rep(i,n){cin>>a[i];} #define sz(a) ((int)(a.size())) #define e(a) ((int)1e##a+7) #define _ << " " << #define in(i,l,r) (l<=i&&i(b)){a=b;ai=bi;}}while(0) #define remin2(a,b,ai,bi) do{if((a)<(b)){a=b;ai=bi;}}while(0) #define ifmax(a,b) if((a)>(b)&&(1||a=b)) #define ifmin(a,b) if((a)<(b)&&(1||a=b)) #define checkbit(n,b) ((n >> b) & 1) #ifdef SLONICHOBOT #define tu cerr << "#line: " << __LINE__ << endl #define dbg(args ...) { cerr << "|" << __LINE__ << "| "; dbg_t,args;cerr << endl; } #define dbgg(X) cerr << #X ": " << X << endl #define debug(args...) do {cerr << #args << ": "; dbg_t,args; cerr << endl;} while(0) #define dbga(a,n) rep(i,n)cerr<