[技巧]读入优化
int read()
{
int sign = 1, n = 0; char c = getchar();
while(c < '0' || c > '9'){ if(c == '-') sign = -1; c = getchar(); }
while(c >= '0' && c <= '9') { n = n*10 + c-'0'; c = getchar(); }
return sign*n;
} 
int read()
{
int sign = 1, n = 0; char c = getchar();
while(c < '0' || c > '9'){ if(c == '-') sign = -1; c = getchar(); }
while(c >= '0' && c <= '9') { n = n*10 + c-'0'; c = getchar(); }
return sign*n;
}