#pragma once
#include<cstdio>
#include<cstdlib>classfastio{staticconstintread_size=1<<26;staticconstintwrite_size=1<<26;char*read_data,*write_data;char*rb,*wb;chartemp[100];public:fastio(){read_data=(char*)std::malloc(read_size);write_data=(char*)std::malloc(write_size);fread(read_data,1,read_size,stdin);rb=read_data;wb=write_data;}~fastio(){fwrite(write_data,1,wb-write_data,stdout);std::free(read_data);std::free(write_data);}template<typenameT>inlineTread_int(){Tret=0;boolneg=false;while((*rb<'0'or*rb>'9')and*rb!='-')++rb;if(*rb=='-'){neg=true;++rb;}while('0'<=*rband*rb<='9'){ret=ret*10+(*rb-'0');++rb;}if(neg)ret=-ret;returnret;}template<typenameT>inlinevoidwrite_int(Tx){if(x==0){write_char('0');return;}if(x<0){write_char('-');x=-x;}char*t=temp;while(x){autoy=x/10;*t=(char)('0'+x-y*10);++t;x=y;}while(t!=temp)write_char(*(--t));}inlinevoidwrite_char(charc){*wb=c;++wb;}};