//int型
inline int read()
{
int s=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') {s=s*10+ch-'0';ch=getchar();}
return s;
}
//double型
inline bool read2(double &ret){
int sgn;
double bit=0.1;
char c;
c=getchar();
if(c==EOF)return true;
while(c!='-'&&c!='.'&&(c<'0'||c>'9'))c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while((c=getchar())>='0'&&c<='9')ret=ret*10+(c-'0');
if(c==' '||c=='
'){ret*=sgn;return true;}
while((c=getchar())>='0'&&c<='9')ret+=(c-'0')*bit,bit/=10;
ret*=sgn;
return false;
}