#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FAST_IO ios_base::sync_with_stdio(false);cin.tie(NULL); #define open freopen("input.txt","r",stdin) #define close freopen ("output.txt","w",stdout) #define db double #define ll long long #define lll unsigned long long #define loop(i,a,n) for(int i=a;i<=n;i++) #define sz size() #define sf scanf #define sf1(a) sf("%d",&a) #define sf2(a,b) sf("%d %d",&a,&b) #define sf3(a,b,c) sf("%d %d %d",&a,&b,&c) #define sf4(a,b,c,d) sf("%d %d %d %d",&a,&b,&c,&d) #define sfd(a) sf("%lf",&a) #define sfd2(a,b) sf("%lf %lf",&a,&b) #define sfd3(a,b,c) sf("%lf %lf %lf",&a,&b,&c) #define sfl1(a) sf("%lld",&a) #define sfl2(a,b) sf("%lld %lld",&a,&b) #define sfl3(a,b,c) sf("%lld %lld %lld",&a,&b,&c) #define pii pair #define pll pair #define pf printf #define pfi(x) pf("%d",x) #define pfl(x) pf("%lld",x) #define pf1(x) pf("%d\n",x) #define pf2(x,y) pf("%d %d\n",x,y) #define pf3(x,y,z) pf("%d %d %d\n",x,y,z) #define pfl1(x) pf("%lld\n",x) #define pfl2(x,y) pf("%lld %lld\n",x,y) #define pfl3(x,y,z) pf("%lld %lld %lld\n",x,y,z) #define NL puts("") #define bug(x) cerr<<"Check it "< inline T bigmod(T p,T e,T M) { ll ret = 1; for(; e > 0; e >>= 1){ if(e & 1) ret = (ret * p) % M; p = (p * p) % M; } return (T)ret; } template inline T gcd(T a,T b){ if(b==0)return a; return gcd(b,a%b); } template inline T lcm(T a,T b){ return (a/gcd(a,b))*b; } template inline T modinverse(T a,T M){ return bigmod(a,M-2,M); } // M is prime} template inline T bpow(T p,T e){ ll ret = 1; for(; e > 0; e >>= 1) { if(e & 1) ret = (ret * p); p = (p * p); } return (T)ret; } //inline ll toint(string s){ll sum=0; for(int i=0;i0){ // sum+=bit[id]; // id-=id&-id; // } // return sum; // } //int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction //int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction //int dx[]={0,1,0,-1};int dy[]={1,0,-1,0}; //4 Direction #define eps 1e-6 #define ub upper_bound // return the right most index of x