inline void read(__int128 &x) {
    x=0;
    int f=1;//判断正负 
    char ch=getchar();//读入字符
    while(ch<'0'||ch>'9') {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {//是数字就读
        x=x*10+ch-'0';//之前结果乘10，加现在读入的
        ch=getchar();
    }
    x=x*f;//添上符号返回
}
inline void write(__int128 x) {
    if(x<0) {
        putchar('-');//输出符号
        x=-x;
    }
    if(x>9)write(x/10);//递归输出
    putchar(x%10+'0');//输出个位
}