inline long long read() { long long x=0ll; long long f=1ll; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;} for(; isdigit(ch);ch=getchar()) {x = x*10ll+ch-'0';} return x*f; }