int input(){ //long long input(){
    char c=getchar();
    bool t=false;
    while(c<'0'||c>'9'){
    	t=false;
        if(c=='-') t=true;
        c=getchar();
    }
    int ans=0; //long long ans=0;
    while(c>='0'&&c<='9'){
    ans=ans*10+c-'0';
    c=getchar();
    }
    if(t) ans=-ans;
    return ans;
}