inline __int128 read(){
	__int128 x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
	return x*f;
}
inline void print(__int128 x){
	if(x>9) print(x/10);
	putchar((char)(x%10+'0'));
}