#include #include #include #include #include #include #include #include #include #include // #include #include #define int long long #define inf 1000000007 #define pa pair #define ll long long #define pal pair #define ppa pair #define ppap pair #define ssa pair #define mp make_pair #define pb push_back #define EPS (1e-10) #define equals(a,b) (fabs((a)-(b))b) return gcd(b,v); if(v==b) return b; if(b%v==0) return v; return gcd(v,b%v); } double distans(double x1,double y1,double x2,double y2){ double rr=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2); return sqrt(rr); } /* int pr[100010]; //int inv[100010]; */ int beki(int wa,int rr,int warukazu){ if(rr==0) return 1ll; if(rr==1) return wa%warukazu; if(rr%2==1) return (beki(wa,rr-1,warukazu)*wa)%warukazu; int zx=beki(wa,rr/2,warukazu); return (zx*zx)%warukazu; } /* void gya(){ pr[0]=1; for(int i=1;i<100010;i++){ pr[i]=(pr[i-1]*i)%inf; } for(int i=0;i<100010;i++) inv[i]=beki(pr[i],inf-2); } */ //sort(ve.begin(),ve.end(),greater()); //----------------kokomade tenpure------------ //vector ans(100000000),ans2(100000000); /* int par[200100],ranks[200100],kosuu[200100]; void shoki(int n){ for(int i=0;i>n; for(int i=0;i>k; if(k==1) ans++; } // n^=m; if(ans%2==1) cout<<"A"<