快速IO

namespace IO {
#define gc() (iSiT?(iT=(iS=ibuff)+fread(ibuff,1,SIZ,stdin),(iSiT?EOF:iS++)):iS++)
const int SIZ = 1 << 21 | 1;
char iS,iT,ibuff[SIZ],obuff[SIZ],oS = obuff,oT=oS+SIZ-1,fu[110],c;int fr;
inline void out() {
fwrite(obuff,1,oS-obuff,stdout);
oS=obuff;
}
template
inline void read(Type &x) {
x=0;Type y=1;
for(c=gc();(c>'9'||c<'0')&&c!='-';c=gc());
c'-'?y=-1:x=(c&15);
for(c=gc();c>='0'&&c<='9';c = gc())x = x * 10 + (c & 15);
x*=y;
}
template
inline void write(Type x) {
if(x<0) oS++='-',x=-1;
if(x0) *oS++='0';
while(x) fu[++fr]=x%10+'0',x/=10;
while(fr) *oS++=fu[fr--];
*oS++=' ';
out();
}
}