//set many funcs template //Ver.20190820 #include #include #include #include #include #define inf 1072114514 #define llinf 4154118101919364364 #define mod 1000000007 #define pi 3.1415926535897932384 int max(int a,int b){if(a>b){return a;}return b;} int min(int a,int b){if(a= b){return (a/b)+1;}return a/b;} int ceil(int a,int b){if(a%b==0){return a/b;}return (a/b)+1;} int gcd(int a,int b){int c;while(b!=0){c=a%b;a=b;b=c;}return a;} int lcm(int a,int b){int c=gcd(a,b);a/=c;return a*b;} int nCr(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;} int nHr(int a,int b){return nCr(a+b-1,b);} int fact(int a){int i,r=1;for(i=1;i<=a;i++){r*=i;}return r;} int pow(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;} int dsum(int x){int r=0;while(x){r+=(x%10);x/=10;}return r;} int dsumb(int x,int b){int r=0;while(x){r+=(x%b);x/=b;}return r;} int sankaku(int x){return ((1+x)*x)/2;} void swap(int *a,int *b){int c;c=(*a);(*a)=(*b);(*b)=c;} long long llmax(long long a,long long b){if(a>b){return a;}return b;} long long llmin(long long a,long long b){if(a= b){return (a/b)+1;}return a/b;} long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;} long long llgcd(long long a,long long b){long long c;while(b!=0){c=a%b;a=b;b=c;}return a;} long long lllcm(long long a,long long b){long long c=llgcd(a,b);a/=c;return a*b;} long long llnCr(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;} long long llnHr(long long a,long long b){return llnCr(a+b-1,b);} long long llfact(long long a){long long i,r=1;for(i=1;i<=a;i++){r*=i;}return r;} long long llpow(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=a;}return r;} long long lldsum(long long x){long long r=0;while(x){r+=(x%10);x/=10;}return r;} long long lldsumb(long long x,long long b){long long r=0;while(x){r+=(x%b);x/=b;}return r;} long long llsankaku(long long x){return ((1+x)*x)/2;} void llswap(long long *a,long long *b){long long c;c=(*a);(*a)=(*b);(*b)=c;} double dbmax(double a,double b){if(a>b){return a;}return b;} double dbmin(double a,double b){if(a*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;} int sortfnckj(const void *a,const void *b){if(*(int *)a<*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;} int llsortfncsj(const void *a,const void *b){if(*(long long *)a>*(long long *)b){return 1;}if(*(long long *)a==*(long long *)b){return 0;}return -1;} int llsortfnckj(const void *a,const void *b){if(*(long long *)a<*(long long *)b){return 1;}if(*(long long *)a==*(long long *)b){return 0;}return -1;} int dbsortfncsj(const void *a,const void *b){if(*(double *)a>*(double *)b){return 1;}if(*(double *)a==*(double *)b){return 0;}return -1;} int dbsortfnckj(const void *a,const void *b){if(*(double *)a<*(double *)b){return 1;}if(*(double *)a==*(double *)b){return 0;}return -1;} int strsortfncsj(const void *a,const void *b){return strcmp((char *)a,(char *)b);} int strsortfnckj(const void *a,const void *b){return strcmp((char *)b,(char *)a);} int chsortfncsj(const void *a,const void *b){if(*(char *)a>*(char *)b){return 1;}if(*(char *)a==*(char *)b){return 0;}return -1;} int chsortfnckj(const void *a,const void *b){if(*(char *)a<*(char *)b){return 1;}if(*(char *)a==*(char *)b){return 0;}return -1;} void shuffledget(int x[],int n){ int i,b[524288],p,c; for(i=0;i=1;i--){ p=rand()%i; c=b[i-1];b[i-1]=b[p];b[p]=c; } for(i=0;i=1;i--){ p=rand()%(i+1); swap(&a[p],&a[i]); } } typedef struct{ int val; int node; }sd; int sdsortfnc(const void *a,const void *b){ if(((sd*)a)->val < ((sd*)b)->val){return -1;} if(((sd*)a)->val > ((sd*)b)->val){return 1;} return 0; } void coordinate_comp(int a[],int n){ int i,c=0; sd dat[524288]; for(i=0;i