#include<iostream>classFastIO{private:intsiz=100000;char*buf,*p1,*p2;public:inlinecharnc(void){returnp1==p2&&(p2=(p1=buf)+fread(buf,1,siz,stdin),p1==p2)?EOF:*p1++;}FastIO(void){buf=(char*)malloc(siz);}FastIO(intn):siz(n){buf=(char*)malloc(siz);}// n characters.~FastIO(void){free(buf);}inlinevoidresize(intn){siz=n;buf=(char*)realloc(buf,siz);}}__buf;inlinevoidreset_size(intsiz){__buf.resize(siz);}template<classT>inlinevoidfast_read(T&x){x=0;staticcharc=__buf.nc();while(c<'0'||c>'9')c=__buf.nc();while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48),c=__buf.nc();}}template<classT>inlinevoidwrite(Tx){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar((x%10)^48);}template<classT>inlinevoidwriteln(Tx){write(x),puts("");}template<typenameT,typename...V>inlinevoidfast_read(T&t,V&...v){fast_read(t),fast_read(v...);}
#line 1 "src/alfred/config/fast-io.hpp"
#include<iostream>classFastIO{private:intsiz=100000;char*buf,*p1,*p2;public:inlinecharnc(void){returnp1==p2&&(p2=(p1=buf)+fread(buf,1,siz,stdin),p1==p2)?EOF:*p1++;}FastIO(void){buf=(char*)malloc(siz);}FastIO(intn):siz(n){buf=(char*)malloc(siz);}// n characters.~FastIO(void){free(buf);}inlinevoidresize(intn){siz=n;buf=(char*)realloc(buf,siz);}}__buf;inlinevoidreset_size(intsiz){__buf.resize(siz);}template<classT>inlinevoidfast_read(T&x){x=0;staticcharc=__buf.nc();while(c<'0'||c>'9')c=__buf.nc();while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48),c=__buf.nc();}}template<classT>inlinevoidwrite(Tx){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar((x%10)^48);}template<classT>inlinevoidwriteln(Tx){write(x),puts("");}template<typenameT,typename...V>inlinevoidfast_read(T&t,V&...v){fast_read(t),fast_read(v...);}