//==================================== //====================================== // // Bismillahir-Rahmanir-Rahim // // ========================================================================== #include #define ll long long int #define FOR(x,y,z) for(int x=y;x #define pll pair #define CLR(a) memset(a,0,sizeof(a)) #define SET(a) memset(a,-1,sizeof(a)) #define N 200010 #define M 1000000007 #define pi acos(-1.0) #define ff first #define ss second #define pb push_back #define inf (1e9)+1000 #define eps 1e-9 #define ALL(x) x.begin(),x.end() using namespace std; int dx[]={0,0,1,-1,-1,-1,1,1}; int dy[]={1,-1,0,0,-1,1,1,-1}; template < class T> inline T biton(T n,T pos){return n |((T)1< inline T bitoff(T n,T pos){return n & ~((T)1< inline T ison(T n,T pos){return (bool)(n & ((T)1< inline T gcd(T a, T b){while(b){a%=b;swap(a,b);}return a;} template string NumberToString ( T Number ) { ostringstream ss; ss << Number; return ss.str(); } inline int nxt(){int aaa;scanf("%d",&aaa);return aaa;} inline ll lxt(){ll aaa;scanf("%lld",&aaa);return aaa;} inline long double dxt(){long double aaa;scanf("%lf",&aaa);return aaa;} template inline T bigmod(T p,T e,T m){T ret = 1; for(; e > 0; e >>= 1){ if(e & 1) ret = (ret * p) % m;p = (p * p) % m; } return (T)ret;} #ifdef sayed #define debug(...) __f(#__VA_ARGS__, __VA_ARGS__) template < typename Arg1 > void __f(const char* name, Arg1&& arg1){ cerr << name << " is " << arg1 << std::endl; } template < typename Arg1, typename... Args> void __f(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names+1, ','); cerr.write(names, comma - names) << " is " << arg1 <