//💭💡🎈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');
    }
};