char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)//提交时使用
//#define GC getchar()//getchar()用于调试，要慢很多

inline ll read_64(){ll X=0,w=0; char ch=0;while(!isdigit(ch)) {w|=ch=='-';ch=GC;}while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=GC;return w?-X:X;}//read_64读long long

inline int read_32(){int X=0,w=0; char ch=0;while(!isdigit(ch)) {w|=ch=='-';ch=GC;}while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=GC;return w?-X:X;}//read_32读int