int getin(){

     int ans=;char tmp;bool sign=;

     while(!isdigit(tmp=getchar()) && tmp!='-');

     if(tmp=='-')sign=,tmp=getchar();

     do ans=(ans<<)+(ans<<)+tmp-'';

     while(isdigit(tmp=getchar()));

     return  sign?-ans:ans;

 }

 inline int read(){

     int p,data=;

     char ch=;

     while ((ch!='-') && ch<'' || ch>'') ch=getchar();

     if (ch=='-')

     {

         p=-;

         ch=getchar();

     } else p=;

     while (ch>='' && ch<='') data=data*+ch-'',ch=getchar();

     return data*p;

 }

 namespace fastIO{

     #define BUF_SIZE 100000

     #define OUT_SIZE 100000

     #define ll long long

     //fread->read

     bool IOerror=;

     inline char nc(){

         static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;

         if (p1==pend){

             p1=buf; pend=buf+fread(buf,,BUF_SIZE,stdin);

             if (pend==p1){IOerror=;return -;}

             //{printf("IO error!\n");system("pause");for (;;);exit(0);}

         }

         return *p1++;

     }

     inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}

     inline void read(int &x){

         bool sign=; char ch=nc(); x=;

         for (;blank(ch);ch=nc());

         if (IOerror)return;

         if (ch=='-')sign=,ch=nc();

         for (;ch>=''&&ch<='';ch=nc())x=x*+ch-'';

         if (sign)x=-x;

     }

     inline void read(ll &x){

         bool sign=; char ch=nc(); x=;

         for (;blank(ch);ch=nc());

         if (IOerror)return;

         if (ch=='-')sign=,ch=nc();

         for (;ch>=''&&ch<='';ch=nc())x=x*+ch-'';

         if (sign)x=-x;

     }

     inline void read(double &x){

         bool sign=; char ch=nc(); x=;

         for (;blank(ch);ch=nc());

         if (IOerror)return;

         if (ch=='-')sign=,ch=nc();

         for (;ch>=''&&ch<='';ch=nc())x=x*+ch-'';

         if (ch=='.'){

             double tmp=; ch=nc();

             for (;ch>=''&&ch<='';ch=nc())tmp/=10.0,x+=tmp*(ch-'');

         }

         if (sign)x=-x;

     }

     inline void read(char *s){

         char ch=nc();

         for (;blank(ch);ch=nc());

         if (IOerror)return;

         for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;

         *s=;

     }

     inline void read(char &c){

         for (c=nc();blank(c);c=nc());

         if (IOerror){c=-;return;}

     }

     //getchar->read

     inline void read1(int &x){

         char ch;int bo=;x=;

         for (ch=getchar();ch<''||ch>'';ch=getchar())if (ch=='-')bo=;

         for (;ch>=''&&ch<='';x=x*+ch-'',ch=getchar());

         if (bo)x=-x;

     }

     inline void read1(ll &x){

         char ch;int bo=;x=;

         for (ch=getchar();ch<''||ch>'';ch=getchar())if (ch=='-')bo=;

         for (;ch>=''&&ch<='';x=x*+ch-'',ch=getchar());

         if (bo)x=-x;

     }

     inline void read1(double &x){

         char ch;int bo=;x=;

         for (ch=getchar();ch<''||ch>'';ch=getchar())if (ch=='-')bo=;

         for (;ch>=''&&ch<='';x=x*+ch-'',ch=getchar());

         if (ch=='.'){

             double tmp=;

             for (ch=getchar();ch>=''&&ch<='';tmp/=10.0,x+=tmp*(ch-''),ch=getchar());

         }

         if (bo)x=-x;

     }

     inline void read1(char *s){

         char ch=getchar();

         for (;blank(ch);ch=getchar());

         for (;!blank(ch);ch=getchar())*s++=ch;

         *s=;

     }

     inline void read1(char &c){for (c=getchar();blank(c);c=getchar());}

     //scanf->read

     inline void read2(int &x){scanf("%d",&x);}

     inline void read2(ll &x){

         #ifdef _WIN32

             scanf("%I64d",&x);

         #else

         #ifdef __linux

             scanf("%lld",&x);

         #else

             puts("error:can't recognize the system!");

         #endif

         #endif

     }

     inline void read2(double &x){scanf("%lf",&x);}

     inline void read2(char *s){scanf("%s",s);}

     inline void read2(char &c){scanf(" %c",&c);}

     inline void readln2(char *s){gets(s);}

     //fwrite->write

     struct Ostream_fwrite{

         char *buf,*p1,*pend;

         Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}

         void out(char ch){

             if (p1==pend){

                 fwrite(buf,,BUF_SIZE,stdout);p1=buf;

             }

             *p1++=ch;

         }

         void print(int x){

             static char s[],*s1;s1=s;

             if (!x)*s1++='';if (x<)out('-'),x=-x;

             while(x)*s1++=x%+'',x/=;

             while(s1--!=s)out(*s1);

         }

         void println(int x){

             static char s[],*s1;s1=s;

             if (!x)*s1++='';if (x<)out('-'),x=-x;

             while(x)*s1++=x%+'',x/=;

             while(s1--!=s)out(*s1); out('\n');

         }

         void print(ll x){

             static char s[],*s1;s1=s;

             if (!x)*s1++='';if (x<)out('-'),x=-x;

             while(x)*s1++=x%+'',x/=;

             while(s1--!=s)out(*s1);

         }

         void println(ll x){

             static char s[],*s1;s1=s;

             if (!x)*s1++='';if (x<)out('-'),x=-x;

             while(x)*s1++=x%+'',x/=;

             while(s1--!=s)out(*s1); out('\n');

         }

         void print(double x,int y){

             static ll mul[]={,,,,,,,,,

                 ,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,

                 100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};

             if (x<-1e-)out('-'),x=-x;x*=mul[y];

             ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;

             ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);

             if (y>){out('.'); for (size_t i=;i<y&&x3*mul[i]<mul[y];out(''),++i); print(x3);}

         }

         void println(double x,int y){print(x,y);out('\n');}

         void print(char *s){while (*s)out(*s++);}

         void println(char *s){while (*s)out(*s++);out('\n');}

         void flush(){if (p1!=buf){fwrite(buf,,p1-buf,stdout);p1=buf;}}

         ~Ostream_fwrite(){flush();}

     }Ostream;

     inline void print(int x){Ostream.print(x);}

     inline void println(int x){Ostream.println(x);}

     inline void print(char x){Ostream.out(x);}

     inline void println(char x){Ostream.out(x);Ostream.out('\n');}

     inline void print(ll x){Ostream.print(x);}

     inline void println(ll x){Ostream.println(x);}

     inline void print(double x,int y){Ostream.print(x,y);}

     inline void println(double x,int y){Ostream.println(x,y);}

     inline void print(char *s){Ostream.print(s);}

     inline void println(char *s){Ostream.println(s);}

     inline void println(){Ostream.out('\n');}

     inline void flush(){Ostream.flush();}

     //puts->write

     char Out[OUT_SIZE],*o=Out;

     inline void print1(int x){

         static char buf[];

         char *p1=buf;if (!x)*p1++='';if (x<)*o++='-',x=-x;

         while(x)*p1++=x%+'',x/=;

         while(p1--!=buf)*o++=*p1;

     }

     inline void println1(int x){print1(x);*o++='\n';}

     inline void print1(ll x){

         static char buf[];

         char *p1=buf;if (!x)*p1++='';if (x<)*o++='-',x=-x;

         while(x)*p1++=x%+'',x/=;

         while(p1--!=buf)*o++=*p1;

     }

     inline void println1(ll x){print1(x);*o++='\n';}

     inline void print1(char c){*o++=c;}

     inline void println1(char c){*o++=c;*o++='\n';}

     inline void print1(char *s){while (*s)*o++=*s++;}

     inline void println1(char *s){print1(s);*o++='\n';}

     inline void println1(){*o++='\n';}

     inline void flush1(){if (o!=Out){if (*(o-)=='\n')*--o=;puts(Out);}}

     struct puts_write{

         ~puts_write(){flush1();}

     }_puts;

     inline void print2(int x){printf("%d",x);}

     inline void println2(int x){printf("%d\n",x);}

     inline void print2(char x){printf("%c",x);}

     inline void println2(char x){printf("%c\n",x);}

     inline void print2(ll x){

         #ifdef _WIN32

             printf("%I64d",x);

         #else

         #ifdef __linux

             printf("%lld",x);

         #else

             puts("error:can't recognize the system!");

         #endif

         #endif

     }

     inline void println2(ll x){print2(x);printf("\n");}

     inline void println2(){printf("\n");}

     #undef ll

     #undef OUT_SIZE

     #undef BUF_SIZE

 };

 using namespace fastIO;