//💭💡🎈fold
#include<bits/stdc++.h>
#define fi first
#define sf scanf
#define se second
#define pf printf
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(x,y) memset((x),(y),sizeof(x))
#define fup(i,x,y) for(int i=(x);i<=(y);++i)
#define fdn(i,x,y) for(int i=(x);i>=(y);--i)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
using namespace std;
扩栈
register char *_sp __asm__("rsp");
int main()
{
const int size=64*1024*256;
static char *sys,*mine(new char[size]+size-4096);
sys=_sp;
_sp=mine;
// solve();
_sp=sys;
return 0;
}
STL
//stack
template<class T>
struct Stack
{
T s[__];int idx;
Stack():idx(0) {}
void pop(){--idx;}
void clear(){idx=0;}
T& top(){return s[idx];}
bool empty(){return !idx;}
void push(T x){s[++idx]=x;}
};
//deque (without push_front())
template<class T>
struct Deque
{
T q[__];int l,r;
Deque():l(1),r(0) {}
void clear(){l=1,r=0;}
T& back(){return q[r];}
T& front(){return q[l];}
bool empty(){return l>r;}
void pop_back(){l<=r?--r:0;}
void pop_front(){l<=r?++l:0;}
void push_back(T x){q[++r]=x;}
};
integer array
template<int __>
struct ia
{
int a[__],n;
ia(int n=0):n(n) {}
void rev(){reverse(a+1,a+n+1);}
void hp(){make_heap(a+1,a+n+1);}
int& operator[](int x){return a[x];}
void sf(){fup(i,1,n)scanf("%d",a+i);}
void mem(int x){memset(a,x,sizeof(a));}
void sup(){sort(a+1,a+n+1,less<int>());}
void sdn(){sort(a+1,a+n+1,greater<int>());}
void uq(){this->sup(),n=unique(a+1,a+n+1)-a-1;}
bool nexp(){return next_permutation(a+1,a+n+1);}
int lb(int x){return lower_bound(a+1,a+n+1,x)-a;}
int ub(int x){return upper_bound(a+1,a+n+1,x)-a;}
void pf(){fup(i,1,n)printf("%d%c",a[i],i==n?'\n':' ');}
};
long modular
struct lm
{
static const ll mod=1e9+7;
static ll phi;
ll n;
lm(ll n=0){this->n=init(n);}
lm inv(){return this->qpow(phi-1);}
lm operator+(const lm& b){return lm(n+b.n);}
lm operator+(const ll b){return lm(n+b%mod);}
lm operator-(const lm& b){return lm(n-b.n);}
lm operator-(const ll b){return lm(n-b%mod);}
lm operator*(const lm& b){return lm(n*b.n);}
lm operator*(const ll b){return lm(b%mod*n);}
lm operator/(lm b){return (*this)*b.qpow(phi-1);}
lm operator/(const ll b){return (*this)*lm(b).qpow(phi-1);}
lm qmul(ll y)
{
ll res=0;
for(ll x=n;y;y>>=1,x<<=1)
if(y&1)res=(res+x)%mod;
return lm(res);
}
lm qpow(ll y)
{
ll res=1;
for(ll x=n;y;y>>=1,x=x*x%mod)
if(y&1)res=res*x%mod;
return lm(res);
}
static ll get_phi()
{
ll x=mod,p=mod;
for(ll i=2;i*i<=mod;i++)
if(x%i==0)for(p=p/i*(i-1);x%i==0;x/=i);
if(x!=1)p=p/x*(x-1);
return p;
}
static lm fac(ll x)
{
lm res;res.n=1;
fup(i,1,x)res=res*i;
return res;
}
static lm c(ll n,ll k){return fac(n)/(fac(k)*fac(n-k));}
static ll init(ll x)
{if(x<=-mod)x%=mod;if(x<0)x+=mod;if(x>=mod)x%=mod;return x;}
};
ll lm::phi=lm::get_phi();
matrix
struct matrix
{
int n,m;
ll a[15][15];
matrix(int n,int m):n(n),m(m) {memset(a,0,sizeof(a));}
matrix operator+(const matrix& b)
{
matrix c(n,m);
fup(i,1,n)fup(j,1,m)c.a[i][j]=a[i][j]+b.a[i][j];
return c;
}
matrix operator-(const matrix& b)
{
matrix c(n,m);
fup(i,1,n)fup(j,1,m)c.a[i][j]=a[i][j]-b.a[i][j];
return c;
}
matrix operator*(const matrix& b)
{
matrix c(n,b.m);
fup(i,1,n)fup(j,1,b.m)fup(k,1,m)
c.a[i][j]=c.a[i][j]+a[i][k]*b.a[k][j];
return c;
}
bool operator==(const matrix& b)
{
fup(i,1,n)fup(j,1,m)if(a[i][j]!=b.a[i][j])return false;
return true;
}
matrix qpow(ll y)
{
matrix x(n,m),c(n,m);
fup(i,1,n){c.a[i][i]=1;fup(j,1,m)x.a[i][j]=a[i][j];}
for(;y;y>>=1,x=x*x)if(y&1)c=c*x;
return c;
}
void sf(){fup(i,1,n)fup(j,1,m)scanf("%lld",&a[i][j]);}
void pf(){fup(i,1,n)fup(j,1,m)
printf("%lld%c",a[i][j],(j==m)?'\n':' ');}
};
fraction
struct frac
{
ll fz,fm;
frac() {}
frac(ll x,ll y):fz(x),fm(y) {simpfy();}
frac(char* s)
{
fz=0,fm=1;
if(s[0]=='-')s++,fm=-1;
int len=strlen(s);
bool p=false;
for(int i=0;i<len;i++)
{
if(p)fm*=10;
if(s[i]!='.')fz=fz*10+s[i]-'0';
else p=true;
}
simpfy();
}
void simpfy()
{
ll d=__gcd(fz,fm);
if(d!=1 && d!=-1)fz/=d,fm/=d;
if(fm<0)fz=-fz,fm=-fm;
}
frac operator+(const frac& b){return frac(fz*b.fm+fm*b.fz,fm*b.fm);}
frac operator-(const frac& b){return frac(fz*b.fm-fm*b.fz,fm*b.fm);}
frac operator*(const frac& b){return frac(fz*b.fz,fm*b.fm);}
frac operator/(const frac& b){return frac(fz*b.fm,fm*b.fz);}
void print(){printf("%lld/%lld\n",fz,fm);}
void print(int x)
{
if(!x)return void(printf("%lld\n",fz/fm));
ll z=fz,m=fm;
if(z<0)z=-z,printf("-");
printf("%lld.",z/m);
for(z%=m;x--;z=z*10%m)
printf("%lld",z*10/m);
printf("\n");
}
};
Polynomial
struct Polynomial
{
static const int __=2e5+5;
ll a[__];int n;
Polynomial() {}
Polynomial(int n):n(n)
{
for(int i=0;i<=n;++i)
a[i]=0;
}
Polynomial(ll b[],int _n) {set(b,_n);}
void set(ll b[],int _n)
{
n=_n;
for(int i=0;i<=n;++i)
a[i]=b[i];
}
ll& operator[](int x){return a[x];}
Polynomial operator+(const Polynomial &b)
{
Polynomial c(max(n,b.n));
for(int i=0;i<=c.n;++i)
c[i]=(i<=n?a[i]:0)+(i<=b.n?b.a[i]:0);
return c;
}
Polynomial operator*(const Polynomial &b)
{
Polynomial c(n+b.n);
for(int i=0;i<=n;++i)
for(int j=0;j<=b.n;++j)
c[i+j]+=a[i]*b.a[j];
return c;
}
void print()
{
for(int i=0;i<=n;++i)
pf("%+lldx^%d",a[i],i);
putchar('\n');
}
};
