//double快读
inline void Readouble(double &ans)
{
	ans=0;
	double y=1.0;
	bool flag=0;
	char ch=getchar();
	while(!isdigit(ch) && ~ch)
	{
		flag|=(ch=='-');
		ch=getchar();
	}
	while(isdigit(ch) && ~ch)
	{
		ans=ans*10+(ch^48);
		ch=getchar();
	}
	ch=getchar();
	while(isdigit(ch) && ~ch)
	{
		y/=10;
		ans+=y*(ch^48);
		ch=getchar();
	}
	if(flag) ans=-ans;
}

//整形快读
#define ll __int128
inline void Read(ll &ans)
{
	ans=0;
	bool flag=0;
	char ch=getchar();
	while(!isdigit(ch) && ~ch)
	{
		flag|=(ch=='-');
		ch=getchar();
	}
	while(isdigit(ch) && ~ch)
	{
		ans=ans*10+(ch^48);
		ch=getchar();
	}
	if(flag) ans=-ans;
}

//整形快写
char c[105];
inline void Write(ll x)
{
	int len=0;
	if(x<0) putchar('-'),x=-x;
	while(x) 
	{
		c[++len]=x%10;
		x/=10;
	}
	while(len)
	{
		putchar(c[len]^48);
		len--;
	}
}