#include<bits/stdc++.h>
#define ll long long
using namespace std;
int readin(){int x=0,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';ch=getchar();}return x*f;}
ll lreadin(){ll x=0,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';ch=getchar();}return x*f;}
ll qmod(ll a,ll b,ll mod){ll r=1;while(b){if(b&1)r=r*a%mod;a=a*a%mod;b>>=1;}return r;}
ll exgcd(ll a,ll b,ll &x,ll &y){if(a==0&&b==0)return -1;if(b==0){x=1;y=0;return a;}ll d=exgcd(b,a%b,y,x);y-=a/b*x;return d;}
ll niyuan(ll a,ll n){ll x,y;ll d=exgcd(a,n,x,y);if(d==1)return (x%n+n)%n;return -1;}
ll rd(){ll stp=rand()%2;return ((rand()<<16)|(rand()<<1)+stp);}