/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=99824LL;
vector<ll> fat,ifat;
ll Mo_bucket; //sqrt(arr.size())

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

struct hash_pair 
{ 
    template <class T1, class T2> 
    size_t operator() (pair<T1, T2> p) const
    {
        size_t hash1 = hash<T1>()(p.first); 
        size_t hash2 = hash<T2>()(p.second); 
        return (hash1 ^ hash2); 
    }
};

template <class A, class B, class C>
pair<A,B> operator *(pair<A,B> a, C c) {a.ff*=c; a.ss*=c; return a;}

template<class A,class B>
pair<A,B> operator + (pair<A,B> a, pair<A,B> b) {return mp(a.ff+b.ff,a.ss+b.ss);}

template<class A,class B>
pair<A,B> operator - (pair<A,B> a, pair<A,B> b) {return mp(a.ff-b.ff,a.ss-b.ss);}

template<class T=ll>
bool cmp(T A, T B) {return (A<B);}

template<class T=double>
bool eq(T a, T b) {return(abs(a-b)<EPS);}

class complex
{
    public:
    double re; double im;
    
    complex() {re=0.0; im=0.0;}
    complex(double r, double i) {re=r; im=i;}
    complex(double r) {re=r; im=0.0;}
    
    complex operator !() //conjugate
    {
        complex ans(re,-im); return ans;
    }
    
    complex operator + (complex z) {complex ans(re+z.re,im+z.im); return ans;}
    complex operator - (complex z) {complex ans(re-z.re,im-z.im); return ans;}
    void operator += (complex z) {re+=z.re; im+=z.im;}
    void operator -= (complex z) {re-=z.re; im-=z.im;}
    complex operator * (complex z) {complex ans(re*z.re-im*z.im,re*z.im+z.re*im); return ans;}
    void operator *= (complex z) {complex ans=(*this)*z; *this=ans;}
    double norm() {double ans = sqrt(re*re+im*im); return ans;}
    complex operator / (complex z) {double n = z.norm(); n=n*n; complex ans=!z; ans.re/=n; ans.im/=n; ans*=(*this); return ans;}
    void operator /= (complex z) {complex ans=(*this)/z; *this=ans;}
    bool operator == (complex z) {if(eq(re,z.re) && eq(im,z.im)) {return true;} else {return false;}}
    bool operator < (complex z) {if(re<z.re) {return true;} else if(eq(re,z.re)) {return (im<z.im);} else {return false;}}
    bool operator <= (complex z) {return (((*this)<z) || ((*this)==z));}
    bool operator > (complex z) {return (z<(*this));}
    bool operator >= (complex z) {return (z<=(*this));}
    
    double arg()
    {
        if(re==0 && im>=0) {return (pi/2.0);}
        if(re==0 && im<0) {return (3.0*pi/2.0);}
        double val = im/re;
        double ans = atan(val);
        if(re<0) {ans=pi+ans;}
        else if(im<0) {ans=2.0*pi+ans;}
        return ans;
    }
};

struct hash_complex
{
    size_t operator() (complex z) const
    {
        return (2*sizeof(double));
    }
};

complex polar(double len, double angle) //angle in radians
{
    complex ans(cos(angle),sin(angle)); ans*=((complex) len);
    return ans;
}

class segment
{
    public:
    complex a,b; //open in a, closed in b
    
    segment() {a=0; b=0;}
    segment(complex x) {a=0; b=x;}
    segment(complex x, complex y) {a=x; b=y;}
    
    bool belong(complex z)
    {
        if(z==a) {return false;}
        if(z==b) {return true;}
        complex w = (b-a)/(b-z);
        if(!eq(w.im,0.0)) {return false;}
        if(w.re>1.0) {return true;}
        else {return false;}
    }
};

class line
{
    public:
    complex a,b; //sometimes directed line a->b
    
    line() {a=0; b=0;}
    line(complex x, complex y) {a=x; b=y;}
    line(segment s) {a=s.a; b=s.b;}
    
    bool belong(complex z)
    {
        if(z==a || z==b) {return true;}
        complex w = (b-a)/(b-z);
        if(!eq(w.im,0.0)) {return false;}
        else {return true;}
    }
    
    ld slope()
    {
        ld ans;
        if(a.re!=b.re) {ans= (a.im-b.im)/(a.re-b.re);}
        else {ans=(ld) INF;}
        return ans;
    }
};

bool parallel(line l, line r)
{
    complex z1=l.a-l.b; complex z2=r.a-r.b;
    complex z = z1/z2;
    if(eq(z.im,0.0)) {return true;}
    else {return false;}
}

complex intersection(line l, line r)
{
    complex z1,z2,z3,z;
    z1=(l.a-l.b)*((r.a*(!r.b))-(r.b*(!r.a)));
    z2=(r.a-r.b)*((l.a*(!l.b))-(l.b*(!l.a)));
    z3=((l.a-l.b)*(!r.a-!r.b))-((r.a-r.b)*(!l.a-!l.b));
    z=(z2-z1)/z3;
    return z;
}

bool intersect(line l, segment s)
{
    line r(s);
    complex z = intersection(l,r);
    return s.belong(z);
}

bool intersect(segment s, segment t)
{
    line l(s); line r(t);
    return (intersect(l,t) && intersect(r,s));
}

bool concurrent(line l1,line l2, line l3)
{
    complex z1 = intersection(l1,l2);
    complex z2 = intersection(l2,l3);
    complex z3 = intersection(l3,l1);
    if(z1==z2 && z2==z3) {return true;}
    else {return false;}
}

complex reflection(complex z, line l)
{
    return ((((l.a-l.b)*(!z))+((!l.a)*l.b)-(l.a*(!l.b)))/((!l.a)-(!l.b)));
}

complex projection(complex z, line l) 
{
    return ((complex) (0.5)*(z+reflection(z,l)));
}

bool prependicular(line l, line r)
{
    complex z = ((l.a-l.b)/(r.a-r.b));
    if(eq(z.re,0.0)) {return true;}
    else {return false;}
}

double distance(complex z, line l)
{
    complex r = reflection(z,l);
    complex ans=z-r;
    return ans.norm();
}

class Triangle
{
    public:
    complex a, b, c;
    complex *circumcentre_ptr;
    
    Triangle() {a=0.0; b=0.0; c=0.0; circumcentre_ptr=nullptr;}
    Triangle(complex x,complex y,complex z) {a=x; b=y; c=z; circumcentre_ptr=nullptr;}
    
    Triangle operator !()
    {
        Triangle ANS(!a,!b,!c); return ANS;
    }
    
    double Area() //!!SIGNED AREA, is positive if, given point in interior, vertexes of triangle are in counterclockwise order.
    {
        complex ans;
        complex z; z.im=0.25;
        complex z1 = a*((!b)-(!c));
        complex z2 = b*((!c)-(!a));
        complex z3 = c*((!a)-(!b));
        ans = z*(z1+z2+z3);
        return ans.re;
    }
    
    complex centroid () 
    {
        complex z;
        z.re=1.0/3.0;
        return (z*(a+b+c));
    }
    
    complex circumcentre()
    {
        if(circumcentre_ptr!=nullptr) {return *circumcentre_ptr;}
        complex *ans=new complex();
        complex c1,c2,c3,z1,z2;
        c1=a*(!a)*(b-c);
        c2=b*(!b)*(c-a);
        c3=c*(!c)*(a-b);
        z1=c1+c2+c3;
        c1=(!a)*(b-c);
        c2=(!b)*(c-a);
        c3=(!c)*(a-b);
        z2=c1+c2+c3;
        *ans=z1/z2;
        circumcentre_ptr=ans;
        return (*ans);
    }
    
    complex orthocentre()
    {
        complex h = a+b+c-(complex) 2.0*circumcentre();
        return h;
    }
};

bool similar(Triangle S, Triangle T) //ATTENTION: Directly similar. For reversely similar, try !S,T
{
    complex z1,z2,z3;
    z1=S.a*(T.b-T.c);
    z2=S.b*(T.c-T.a);
    z3=S.c*(T.a-T.b);
    complex ans = z1+z2+z3;
    if(ans==(complex) 0.0) {return true;}
    else {return false;}
}

class Quadrilateral
{
    public:
    complex a,b,c,d;
    
    Quadrilateral() {a=0; b=0; c=0; d=0;}
    Quadrilateral(complex x, complex y, complex w, complex z) {a=x; b=y; c=w; d=z;}
    
    bool concyclic()
    {
        complex z = ((b-a)*(c-d))/((c-a)*(b-d));
        if(z.im==0.0) {return true;}
        else {return false;}   
    }
    
    double Area()
    {
        Triangle T1(a,b,c); Triangle T2(a,c,d);
        return (T1.Area()+T2.Area());
    }
    
    complex MiquelPoint()
    {
        complex ans = ((a*c)-(b*d))/(a+c-b-d);
        return ans;
    }
};

class Polygon
{
    public:
    ll N; 
    vector<complex> v;
    double *area_ptr;
    bool *cyclic_ptr;
    
    Polygon() {N=0LL; area_ptr=nullptr; cyclic_ptr=nullptr;}
    Polygon(vector<complex> vertex) {v=vertex; N=v.size(); area_ptr=nullptr; cyclic_ptr=nullptr;}
    
    double Area()
    {
        if(area_ptr!=nullptr) {return *area_ptr;}
        double *ans = new double();
        (*ans)=0.0;
        REP(i,1,v.size()-1) 
        {
            Triangle T(v[0],v[i],v[i+1]);
            (*ans)+=T.Area();
        }
        area_ptr=ans;
        return abs(*ans);
    }
    
    bool concylic()
    {
        if(cyclic_ptr!=nullptr) {return *cyclic_ptr;}
        bool ans;
        REP(i,3,v.size())
        {
            Quadrilateral Q(v[0],v[1],v[2],v[i]);
            if(!Q.concyclic()) {ans=false;cyclic_ptr=&ans; return false;}
        }
        ans=true;
        cyclic_ptr=&ans;
        return true;
    }
    
    bool inside(complex z)
    {
        segment l(z,z+(complex) (INF));
        ll intersections=0LL;
        REP(i,0,N)
        {
            segment s(v[i],v[(i+1)%N]);
            if(intersect(l,s)) {intersections++;}
        }
        if(intersections%2==0) {return false;}
        else {return true;}
    }
};

vector<ll> SweepSort(line l, vector<complex> v) //ans[i]=j means, in the sweep sorted point array, position i is v[j]
{
    vector<pl> s; 
    REP(i,0,v.size()) 
    {
        Triangle T(v[i],l.b,l.a);
        s.pb(mp(T.Area(),i));
    }
    sort(whole(s));
    vector<ll> ans; REP(i,0,v.size()) {ans.pb(s[i].ss);}
    return ans;
}

vector<ll> ArgSort(vector<complex> v, complex centre) //angles related to horizontal directed line through centre, angles from 0 to 360. ans[i]=j means, in the sweep sorted point array, position i is v[j]
{
    vector<pl> angles; vector<ll> ans;
    REP(i,0,v.size()) {complex z = v[i]-centre; angles.pb(mp(z.arg(),i));}
    sort(whole(angles));
    REP(i,0,v.size()) {ans.pb(angles[i].ss);}
    return ans;
}

bool cmp_com(complex a, complex b) {return (a<b);}

bool cmp_pcomll(pair<complex,ll> a, pair<complex,ll> b) {if(a.ff<b.ff) {return true;} else if(a.ff>b.ff) {return false;} else {return (a.ss<b.ss);}}

pl ClosestPair(vector<complex> v) //returns (ind1,ind2) pair of indexes, ind1<ind2
{
    ll N = v.size();
    vector<complex> z = v; sort(whole(z),cmp_com);
    pair<complex,complex> ans; 
    ld mind=(ld) INF;
    set<pair<double,double> > s; s.insert(mp(z[0].im,z[0].re));
    ll ind=0LL;
    set<pair<double,double> >::iterator it;
    REP(i,1,N)
    {
        while(z[i].re-z[ind].re>mind) 
        {
            s.erase(mp(z[ind].im,z[ind].re));
            ind++;
        }
        it=s.lower_bound(mp(z[i].im-mind,-INF));
        while(it!=s.end() && it->ff<=z[i].im+mind)
        {
            complex x(it->ss,it->ff);
            complex y = z[i]-x;
            if(y.norm()<mind) {mind=y.norm(); ans.ff=x; ans.ss=z[i];}
            it++;
        }
        s.insert(mp(z[i].im,z[i].re));
    }
    pl f_ans;
    REP(i,0,N) 
    {
        if(v[i]==ans.ff) {f_ans.ff=i;}
        if(v[i]==ans.ss) {f_ans.ss=i;}
    }
    if(f_ans.ff>f_ans.ss) {swap(f_ans.ff,f_ans.ss);}
    return f_ans;
}

vector<ll> ConvexHull(vector<complex> v, bool sorted=false) //returns vector of indexes of the convex hull
{
    ll N=v.size(); 
    vector<pair<complex,ll> > z; REP(i,0,N) {z.pb(mp(v[i],i));}
    if(!sorted) {sort(whole(z),cmp_pcomll);}
    vector<ll> ans,f_ans;
    REP(i,0,N)
    {
        ans.pb(i);
        if(i==0) {continue;}
        while(ans.size()>2)
        {
            line l1(z[ans[ans.size()-3]].ff,z[ans[ans.size()-2]].ff);
            line l2(z[ans[ans.size()-2]].ff,z[i].ff);
            if(l1.slope()<l2.slope())
            {
                ans.erase(ans.end()-2);
            }
            else
            {
                break;
            }
        }
    }
    REP(i,0,ans.size()) {f_ans.pb(z[ans[i]].ss);}
    ans.clear();
    REP(i,0,N)
    {
        ans.pb(i);
        if(i==0) {continue;}
        while(ans.size()>2)
        {
            line l1(z[ans[ans.size()-3]].ff,z[ans[ans.size()-2]].ff);
            line l2(z[ans[ans.size()-2]].ff,z[i].ff);
            if(l1.slope()>l2.slope())
            {
                ans.erase(ans.end()-2);
            }
            else
            {
                break;
            }
        }
    }
    REP(i,1,ans.size()-1) {f_ans.pb(z[ans[i]].ss);}
    sort(whole(f_ans));
    return f_ans;
}

ll gcd(ll a,ll b)
{
    if(a>b) {swap(a,b);}
    if(a==0) {return b;}
    else {return gcd(a,b%a);}
}

pl ExtEuclid(ll a, ll b) //return pair x,y: ax+by=(a,b)
{
    if(a==0) {return mp(0LL,1LL);}
    if(b==0) {return mp(1LL,0LL);}
    bool swapped=false;
    if(a<b) {swap(a,b); swapped=true;}
    ll red=a%b; if(red<0) {red+=b;}
    ll k=(a-red)/b;
    pl nxt=ExtEuclid(red,b);
    pl ans; ans.ff=nxt.ff; ans.ss=nxt.ss-k*nxt.ff;
    if(swapped) {swap(ans.ff,ans.ss);}
    return ans;
}

bool IsPrime(ll s)
{
    if(s==1LL) {return false;}
    if(s==2LL) {return true;}
    REP(i,2LL,sqrt(s)+1LL)
    {
        if(s%i==0LL) {return false;}
    }
    return true;
}

vector<pl> PF(ll s)
{
    vector<pl> pf; 
    if(s==2LL) {pf.pb(mp(2LL,1LL)); return pf;}
    ll d=2LL;
    while(d<=sqrt(s)+1LL)
    {
        if(s%d==0LL)
        {
            ll exp=0LL;
            while(s%d==0LL)
            {
                exp++; s/=d;
            }
            pf.pb(mp(d,exp));
        }
        d++;
    }
    if(s>1LL) 
    {
        pf.pb(mp(s,1LL));    
    }
    return pf;
}

vector<ll> Sieve(ll N) //O(NloglogN)
{
    vector<bool> valid; REP(i,0,N+1) {valid.pb(true);}
    vector<ll> primes;
    REP(i,2,N+1)
    {
        if(!valid[i]) {continue;}
        ll cur=i; primes.pb(cur);
        while(cur<=N) {valid[cur]=false; cur+=i;}
    }
    return primes;
}

ll phi(ll x)
{
    ll n=x;
    vector<pl> pri=PF(x); 
    ll ans=1;
    REP(i,0,pri.size())
    {
        ans*=(ll) ((pow(pri[i].ff,pri[i].ss-(ld) 1)));
        ans*=(pri[i].ff-1);
    }
    return ans;
}

ll ord(ll a, ll m)
{
    ll cur=a; ll ans=1;
    while((cur-1LL)%m!=0LL)
    {
        cur*=a; ans++; cur%=m;
    }
    return ans;
}

ll fastexp(ll a,ll e) 
{
    if(e==0) {return 1LL;}
    if(e%2LL==0)
    {
        ll v=fastexp(a,(ll) e/2LL); return (v*v)%mod;
    }
    else
    {
        ll v=fastexp(a,(ll) e/2LL); return (((v*v)%mod)*a)%mod;
    }
}

ll fastexp(ll a, ll e, ll m)
{
    if(e==0) {return 1LL;}
    if(e%2LL==0)
    {
        ll v=fastexp(a,(ll) e/2LL, m); return (v*v)%m;
    }
    else
    {
        ll v=fastexp(a,(ll) e/2LL, m); return (((v*v)%m)*a)%m;
    }
}

ll fac(ll n, ll m)
{
    ll ans=1LL; REP(i,1LL,n+1LL) {ans*=i; ans%=m;}
    if(ans<0) {ans+=m;}
    return ans;
}

ll inv(ll s)
{
    return fastexp(s,mod-2LL);
}

ll inv(ll s, ll m)
{
    return fastexp(s,phi(m)-1LL,m);
}

ll bin(ll n, ll k) //binomial coefficient
{
    if(k<0LL || k>n) {return 0LL;}
    ll ans=(((ifat[k]*ifat[n-k])%mod)*fat[n])%mod;
    return ans;
}

ll bin(ll n, ll k, ll m)
{
    if(k<0LL || k>n) {return 0LL;}
    ll ans=fac(n,m);
    ans*=inv(fac(k,m),m); ans%=m; ans*=inv(fac(n-k,m),m); ans%=m;
    if(ans<0) {ans+=m;}
    return ans;
}

void Calcfat(ll n) 
{
    
    ll ans=1LL; fat.pb(ans);
    REP(i,1LL,n+1LL) {ans*=i; ans%=mod; fat.pb(ans);}
    REP(i,0,n+1) {ifat.pb(inv(fat[i]));}
}

ll CRT(vector<pl> a) //a[i].ff=ai, a[i].ss=mi
{
    REP(i,0,a.size()) {a[i].ff%=a[i].ss;}
    ll ans=0LL; vector<ll> X; ll p=1LL; REP(i,0,a.size()) {p*=a[i].ss;} 
    REP(i,0,a.size()) {X.pb(p/a[i].ss);}
    ll val;
    REP(i,0,a.size())
    {
        val=a[i].ff*X[i]*inv(X[i],a[i].ss); val%=p; ans+=val; ans%=p;
    }
    if(ans<0) {ans+=p;}
    return ans;
}

class ModInt
{
    public:
    ll a; ll m;
    ModInt() {a=0LL; m=mod;}
    ModInt(ll val) {a=val; m=mod; a%=m; a+=m; a%=m;}
    
    ModInt operator + (ModInt b) {ModInt ans(a+b.a); return ans;}
    ModInt operator - (ModInt b) {ModInt ans(a-b.a); return ans;}
    ModInt operator * (ModInt b) {ModInt ans(a*b.a); return ans;}
    ModInt operator / (ModInt b) {ModInt ans(a*inv(b.a)); return ans;}
    void operator ++() {a++; a%=m; a+=m; a%=m;}
    void operator --() {a--; a%=m; a+=m; a%=m;}
    void operator +=(ModInt b) {ModInt ans=(*(this)) + b; a=ans.a;}
    void operator -=(ModInt b) {ModInt ans=(*(this)) - b; a=ans.a;}
    void operator *=(ModInt b) {ModInt ans=(*(this))*b; a=ans.a;}
    void operator /=(ModInt b) {ModInt ans=(*(this))/b; a=ans.a;}
    bool operator ==(ModInt b) {if((a-b.a)%m==0) {return true;} else {return false;}}
};

ostream & operator << (ostream &out, ModInt &M) {cout<<M.a; return out;}
istream & operator >> (istream &in, ModInt &M) {ll a; cin>>a; ModInt ans(a); M=a; return in;}

class Matrix
{
    public:
    ll N,M; 
    vector<vector<double> > a;
    ll rank; 
    Matrix *Red, *Inv, *Trans; double det;
    vector<bool> pivot;
    
    Matrix() {N=0LL; M=0LL; Red=nullptr; Inv=nullptr; Trans=nullptr;}
    Matrix (vector<vector<double> > x)
    {
        N=x.size(); M=x[0].size(); a=x; rank=0LL; REP(i,0,M) {pivot.pb(false);}
        Red=nullptr; Inv=nullptr; Trans=nullptr;
    }
    
    Matrix operator + (Matrix B) //O(NM)
    {
        if((*this).N!=B.N || (*this).M!=B.M) {Matrix ANS; return ANS;}
        vector<vector<double> > ans; vector<double> xx; REP(i,0,(*this).M) {xx.pb(0.0);} REP(i,0,(*this).N) {ans.pb(xx);}
        REP(i,0,(*this).N) {REP(j,0,(*this).M) {ans[i][j]=(*this).a[i][j]+B.a[i][j];}}
        Matrix ANS(ans); return ANS;
    }
    
    Matrix operator * (Matrix B) //O(N^3)
    {
        if(M!=B.N) {Matrix ANS; return ANS;}
        vector<vector<double> > d; vector<double> xx; REP(i,0,B.M) {xx.pb(0.0);} REP(i,0,N) {d.pb(xx);}
        REP(i,0,N)
        {
            REP(j,0,B.M)
            {
                double sum=0.0; REP(z,0,M) {sum+=(a[i][z]*B.a[z][j]);}
                d[i][j]=sum;
            }
        }
        Matrix ANS(d);
        return ANS;
    }
    
    Matrix operator * (double c) //O(NM)
    {
        Matrix ANS = (*this); REP(i,0,N) {REP(j,0,M) {ANS.a[i][j]*=c;}}
        return ANS;
    }
    
    Matrix operator - (Matrix B)
    {
        return ((*this)+B*(-1.0));
    }
    
    bool operator ==(Matrix B)
    {
        return ((*this).a==B.a);
    }
    
    bool operator !=(Matrix B)
    {
        if((*this)==B) {return false;}
        else {return true;}
    }
    
    void operator +=(Matrix B) {*this=(*this)+B;}
    
    void operator -=(Matrix B) {*this=(*this)-B;}
    
    void operator *=(Matrix B) {*this=(*this)*B;}
    
    void operator *=(double c) {*this=(*this)*c;}
    
    void operator /=(double c) {*this=(*this)*(1.0/c);}
    
    void operator /=(Matrix B) {B.RRE(); *this=(*this)*(*(B.Inv));}
    
    Matrix operator ~() 
    {
        if(Trans!=nullptr) {return *Trans;} 
        vector<double> xx; REP(i,0,N) {xx.pb(0.0);} 
        vector<vector<double> > ans; REP(i,0,M) {ans.pb(xx);}
        REP(i,0,M) {REP(j,0,N) {ans[i][j]=a[j][i];}}
        Matrix *RESULT = new Matrix(ans); Trans=RESULT;
        return *RESULT;
    }
    
    void disp()
    {
        REP(i,0,N) {REP(j,0,M) {cout<<a[i][j]<<" ";} cout<<endl;}
    }
    
    void Inp() 
    {
        ll NN,MM; cin>>NN>>MM; N=NN; M=MM; 
        vector<double> xx; REP(i,0,M) {xx.pb(0.0);} REP(i,0,N) {a.pb(xx);}
        double c; REP(i,0,N) {REP(j,0,M) {cin>>c; a[i][j]=c;}}
        REP(i,0,M) {pivot.pb(false);}
    }
    
    Matrix RRE() //Reduced Row Echelon Form, O(N*M^2), also builds "inverse" matrix up
    {
        if(Red!=nullptr) {return *Red;}
        det=1.0;
        rank=0LL;
        Matrix *A= new Matrix(); *A=*this;
        Matrix *Inverse = new Matrix();
        vector<double> xx; REP(i,0,N) {xx.pb(0.0);} REP(i,0,N) {(*Inverse).a.pb(xx);}
        (*Inverse).N=N; (*Inverse).M=N; REP(i,0,N) {(*Inverse).a[i][i]=1.0;}
        vector<bool> v; REP(i,0,N) {v.pb(true);}
        REP(ind,0,M)
        {
            ll line=0LL;
            while(line<N)
            {
                if(!v[line]) {line++; continue;}
                if((*A).a[line][ind]!=0.0) {break;}
                line++;
            }
            if(line==N) {continue;}
            pivot[ind]=true;
            double c=(*A).a[line][ind]; det*=c; 
            REP(i,0,M) {(*A).a[line][i]/=c;}
            REP(i,0,N) {(*Inverse).a[line][i]/=c;}
            v[line]=false; rank++;
            REP(i,0,N)
            {
                if(i==line) {continue;}
                double c=(*A).a[i][ind];
                if(c==0.0) {continue;}
                REP(j,0,M) {(*A).a[i][j]-=((*A).a[line][j]*c);}
                REP(j,0,N) {(*Inverse).a[i][j]-=((*Inverse).a[line][j]*c);}
            }
        }
        vector<pair<pair<vector<double> ,vector<double> >, ll > > ToOrder; REP(i,0,N) {ToOrder.pb(mp(mp((*A).a[i],(*Inverse).a[i]),i));}
        sort(ToOrder.begin(),ToOrder.end());
        reverse(ToOrder.begin(),ToOrder.end()); 
        (*A).a.clear(); REP(i,0,N) {(*A).a.pb(ToOrder[i].ff.ff);}
        (*Inverse).a.clear(); REP(i,0,N) {(*Inverse).a.pb(ToOrder[i].ff.ss);}
        Red=A; Inv=Inverse;
        if(rank!=N || rank!=M) {det=(double) 0.0;}
        ll inversions=0LL;
        REP(i,0,N) {REP(j,i+1,M) {if(ToOrder[i].ss>ToOrder[j].ss) {inversions++;}}}
        if(inversions%2!=0) {det*=(-1.0);} 
        return *Red;
    }
    
    vector<double> Gauss(vector<double> b) //gives one possible solution if there is one to Ax=b in O(N^2)
    {
        Matrix A=RRE(); Matrix B=*Inv;
        vector<double> ans; REP(i,0,M) {ans.pb(0.0);}
        double val; ll piv=0LL;
        REP(i,0,N)
        {
            val=0.0; REP(j,0,N) {val+=B.a[i][j]*b[j];}
            while(!pivot[piv] && piv<M) {piv++;}
            if(piv<M) {ans[piv]=val;}
            else if(val!=0.0) {ans.clear(); return ans;}
            piv++;
        }
        return ans;
    }
};

Matrix fastexp(Matrix A, ll e) //O(N^3loge)
{
    if(A.N!=A.M) {Matrix ANS; return ANS;}
    if(e<0) {A.RRE();if(A.rank==0) {e=0LL;} else {return fastexp(*(A.Inv),-e);}}
    if(e==0) 
    {Matrix ANS=A; REP(i,0,A.N) {REP(j,0,A.N) {if(i!=j) {ANS.a[i][j]=0.0;} else {ANS.a[i][j]=1.0;}}} return ANS;}
    if(e%2LL==0)
    {
        Matrix V =fastexp(A,(ll) e/2LL); return (V*V);
    }
    else
    {
        Matrix V=fastexp(A,(ll) e/2LL); return (V*V*A);
    }
}

template<class T=ll>
class SparseTable //Range Minimum Queries
{
    public:
    ll N; 
    vector<T> a;
    vector<vector<T> > v;
    
    SparseTable() {N=0LL;}
    SparseTable(vector<T> b)
    {
        a=b; N=a.size();
        ll lo=(ll) floor((double) log2(N)) +1LL;
        vector<T> xx; 
        REP(i,0,lo) {xx.pb(mp(INF,INF));} REP(i,0,N) {v.pb(xx);}
        REP(step,0LL,lo)
        {
            REP(i,0,N-(1LL<<step)+1LL)
            {
                if(step==0) {v[i][0]=a[i];}
                else {v[i][step]=min(v[i][step-1],v[i+(1LL<<(step-1))][step-1]);}
            }
        }
    }
    
    T query(ll l, ll r)
    {
        ll step=(ll) floor((double) log2(r-l+1LL));
        return min(v[l][step],v[r-(1LL<<step)+1LL][step]);
    }
};

class DSU
{
    public:
    ll N;
    vector<ll> p,siz;
    
    DSU(ll n)
    {
        N=n; REP(i,0,N) {p.pb(i); siz.pb(1);}
    }
    
    ll find(ll x)
    {
        if(p[x]==x) {return x;}
        ll ans=find(p[x]);
        p[x]=ans; 
        return ans;
    }
    
    void unionn(ll a, ll b)
    {
        a=find(a); b=find(b);
        if(siz[a]>siz[b]) {swap(a,b);}
        p[a]=b; siz[b]+=siz[a];
    }
};

class SucPath
{
    public:
    ll N;
    vector<ll> fo;
    vector<vector<ll> > f2; //sparse table of steps powers of 2
    ll ms; //max_steps
    
    SucPath() {N=0LL;}
    SucPath(vector<ll> x, ll max_steps) 
    {
        N=x.size(); fo=x; ms=max_steps;
        vector<ll> xx;
        REP(i,0,(ll) (floor(log2(ms)))+1LL) {xx.pb(0LL);}
        REP(i,0,N) {f2.pb(xx);}
        Conf2(0);
    }
    
    void Conf2(ll e) //O(NlogN)
    {
        if((1LL<<e)>ms) {return;}
        if(e==0) {REP(i,0,N) {f2[i][e]=fo[i];} Conf2(e+1);}
        else 
        {
            REP(i,0,N) 
            {
                f2[i][e]=f2[f2[i][e-1]][e-1];
            }
        }
        Conf2(e+1);
    }
    
    ll f(ll x,ll s) //O(logN)
    {
        ll ind=0; 
        while(s>0) 
        {
            if(s%2!=0) {x=f2[x][ind];}
            s/=2; ind++;
        }
        return x;
    }
    
    pl cycle() //Floyd's Algorithm, O(N) time, O(1) memory, return <element of cycle,length od cycle>
    {
        ll a=fo[0]; ll b=fo[fo[0]];
        while(a!=b) {a=fo[a]; b=fo[fo[b]];}
        ll l=1; b=fo[a];
        while(b!=a) {b=fo[b]; l++;}
        return mp(a,l);
    }
};

class FT
{
    public:
    ll N;
    vector<ll> a, f;
    FT(vector<ll> z)
    {
        N = z.size(); a = z; ll sum = 0;
        vector<ll> ps; ps.pb(0); REP(i,0,N) {sum+=a[i]; ps.pb(sum);}
        REP(i,0,N+1)
        {
            f.pb(ps[i] - ps[i-(i&(-i))]);
        }
    }
    
    ll sum(ll s)
    {
        if(s<0) {return 0;}
        ll cur = s+1; 
        ll ans = 0;
        while(cur>0) 
        {
            ans+=f[cur];
            cur-=(cur&(-cur));
        }
        return ans;
    }
    
    void update(ll s, ll dif)
    {
        ll cur = s+1;
        a[s]+=dif;
        while(cur<=N)
        {
            f[cur]+=dif;
            cur+=(cur&(-cur));
        }
    }
};

class ST
{
    public:
    ll N;
    
    class SV //seg value
    {
        public:
        ll a; 
        SV() {a=0LL;}
        SV(ll x) {a=x;}
        
        SV operator & (SV X) {SV ANS(a+X.a); return ANS;}
    };
      
    class LV //lazy value
    {
        public:
        ll a;
        LV() {a=0LL;}
        LV(ll x) {a=x;}
        
        LV operator & (LV X) {LV ANS(a+X.a); return ANS;}
    };
    
    SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node
    {
        SV X(p[c].a+(range[c].ss-range[c].ff+1)*lazy[c].a);
        return X;
    }
    
    SV neuts; LV neutl;
    
    vector<SV> p;
    vector<LV> lazy;
    vector<pl> range;
    
    ST() {N=0LL;}
    ST(vector<ll> arr)
    {
        N = (ll) 1<<(ll) ceil(log2(arr.size()));
        REP(i,0,2*N) {range.pb(mp(0LL,0LL));}
        REP(i,0,N) {p.pb(neuts);}
        REP(i,0,arr.size()) {SV X(arr[i]); p.pb(X); range[i+N]=mp(i,i);}
        REP(i,arr.size(),N) {p.pb(neuts); range[i+N]=mp(i,i);}
        ll cur = N-1;
        while(cur>0)
        {
            p[cur]=p[2*cur]&p[2*cur+1];
            range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss);
            cur--;
        }
        REP(i,0,2*N) {lazy.pb(neutl);}
    }
    
    void prop(ll c) //how lazy values propagate
    {
        p[c]=upval(c);
        lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1];
        lazy[c]=neutl;
    }
    
    SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b,1)
    {
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return neuts;}
        if(x>=a && y<=b) {return upval(c);}
        prop(c);
        SV ans = query(a,b,2*c)&query(a,b,2*c+1);
        return ans;
    }
    
    void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b,1,0,S.N-1)
    {
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return ;}
        if(x>=a && y<=b) 
        {
            lazy[c]=s&lazy[c]; 
            return;
        }
        update(s,a,b,2*c); update(s,a,b,2*c+1);
        p[c]=upval(2*c)&upval(2*c+1);
    }
};

class DynamicST
{
    public:
    ll N; 
    
    class SV //seg value
    {
        public:
        ll a; 
        SV() {a=0LL;}
        SV(ll x) {a=x;}
        
        SV operator & (SV X) {SV ANS(a+X.a); return ANS;}
    };
      
    class LV //lazy value
    {
        public:
        ll a;
        LV() {a=0LL;}
        LV(ll x) {a=x;}
        
        LV operator & (LV X) {LV ANS(a+X.a); return ANS;}
    };
    
    SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node
    {
        SV X((m[c]->sv).a+(m[c]->r-m[c]->l+1)*(m[c]->lv).a);
        return X;
    }
    
    SV neuts; LV neutl;
    
    class node
    {
        public:
        ll ind;
        SV sv; LV lv;
        ll l,r; //range
        
        node * par, *lson, *rson;
        
        node(ll ind2, SV sv2, LV lv2, unordered_map<ll,node *> *m) 
        {
            ind=ind2; sv=sv2; lv=lv2; lson=nullptr; rson=nullptr;
            if(ind==1) {l=0LL;par=nullptr;}
            else
            {
                node * X = (*m)[ind/2];
                par=X;
                if(ind%2==0) 
                {
                    par->lson=this;
                    l=X->l; r=(X->l+X->r)/2LL;
                }
                else 
                {
                    par->rson=this;
                    l=(X->l+X->r+1)/2; r=X->r;
                }
            }
        }
    };
    
    unordered_map<ll,node *> m; 
    node *root;
    
    DynamicST(ll n)
    {
        N = (ll) 1<<(ll) ceil(log2(n));
        node *X = new node(1,neuts,neutl,&m);
        root=X; root->r=N-1LL;
    }
    
    void prop(ll c) //how lazy values propagate
    {
        m[c]->sv=upval(c);
        if(m[c]->lson==nullptr) {node *X=new node(2*c,neuts,neutl,&m);}
        if(m[c]->rson==nullptr) {node *X=new node(2*c+1,neuts,neutl,&m);}
        m[2*c]->lv=m[c]->lv&m[2*c]->lv; m[2*c+1]->lv=m[c]->lv&m[2*c+1]->lv;
        m[c]->lv=neutl;
        if(2*c>=N) 
        {
            m[2*c]->sv=upval(2*c); m[2*c+1]->sv=upval(2*c+1);
            m[2*c]->lv=neutl; m[2*c+1]->lv=neutl;
        }
    }
    
    SV query(ll a,ll b, ll c) //range [a,b], current node. initially: query(a,b,1)
    {
        ll x=m[c]->l; ll y=m[c]->r;
        if(y<a || x>b) {return neuts;}
        if(x>=a && y<=b) {return upval(c);}
        prop(c);
        SV ans = query(a,b,2*c)&query(a,b,2*c+1);
        return ans;
    }
    
    void update(LV s, ll a, ll b, ll c) //update LV, range [a,b], current node, current range. initially: update(s,a,b,1,0,S.N-1)
    {
        ll x=m[c]->l; ll y=m[c]->r;
        if(y<a || x>b) {return ;}
        if(x>=a && y<=b) 
        {
            m[c]->lv=s&m[c]->lv; 
            if(c>=N) {m[c]->sv=upval(c); m[c]->lv=neutl;}
            return;
        }
        if(m[c]->lson==nullptr) {node *X=new node(2*c,neuts,neutl,&m);}
        if(m[c]->rson==nullptr) {node *X=new node(2*c+1,neuts,neutl,&m);}
        update(s,a,b,2*c); update(s,a,b,2*c+1);
        m[c]->sv=upval(2*c)&upval(2*c+1);
    }
};

class PersistentST
{
    public:
    ll N; 
    
    class SV //seg value
    {
        public:
        ll a; 
        SV() {a=0LL;}
        SV(ll x) {a=x;}
        
        SV operator & (SV X) {SV ANS(a+X.a); return ANS;}
    };
      
    class LV //lazy value
    {
        public:
        ll a;
        LV() {a=0LL;}
        LV(ll x) {a=x;}
        
        LV operator & (LV X) {LV ANS(a+X.a); return ANS;}
    };
    
    SV neuts; LV neutl;
    
    class node
    {
        public:
        ll ind;
        SV sv; LV lv;
        ll l,r; //range
        ll rootind; //x: this node is root[x]
        
        node *lson, *rson;
        
        node(ll ind,node *par, SV sv2, LV lv2, ll rootindex=-1LL) 
        {
            rootind=rootindex;
            sv=sv2; lv=lv2; lson=nullptr; rson=nullptr;
            if(par==nullptr) {l=0LL;}
            else
            {
                if(ind%2==0) 
                {
                    par->lson=this;
                    l=par->l; r=(par->l+par->r)/2LL;
                }
                else 
                {
                    par->rson=this;
                    l=(par->l+par->r+1)/2; r=par->r;
                }
            }
        }
    };
    
    SV upval(node *X) //how lazy values modify a seg value inside a node, c=current node
    {
        SV ANS((X->sv).a+(X->r-X->l+1)*(X->lv).a);
        return ANS;
    }
    
    vector<node*> root;
    vector<ll> anc; //ancestor of a seg tree copy
    unordered_map<ll,node*> m; //stores current update
    
    PersistentST(ll n)
    {
        N = (ll) 1<<(ll) ceil(log2(n));
        node *X = new node(1LL,nullptr,neuts,neutl,0LL);
        X->r=N-1LL;
        root.pb(X);
        anc.pb(0LL);
        m[0]=nullptr;
    }
    
    void Build(node *cur) //goes from dynamic to fixed (except for persistence). init: Build(root[x])
    {
        if(cur->ind>=N) {return;}
        node *X = new node(2*cur->ind,cur,neuts,neutl);
        node *Y = new node(2*cur->ind+1,cur,neuts,neutl);
        Build(X);
        Build(Y);
    }
    
    void prop(node *cur) //how lazy values propagate
    {
        cur->sv=upval(cur);
        if(cur->lson==nullptr) {node *X=new node(2*cur->ind,cur,neuts,neutl);}
        if(cur->rson==nullptr) {node *X=new node(2*cur->ind+1,cur,neuts,neutl);}
        node *X=cur->lson; node *Y=cur->rson;
        X->lv=cur->lv&X->lv; Y->lv=cur->lv&Y->lv;
        cur->lv=neutl;
        if(2*cur->ind>=N) 
        {
            X->sv=upval(X); Y->sv=upval(Y);
            X->lv=neutl; Y->lv=neutl;
        }
    }
    
    SV query(ll a,ll b, node *cur) //range [a,b], current node. initially: query(a,b,root[x]) for a query in seg tree number x
    {
        ll x=cur->l; ll y=cur->r;
        if(y<a || x>b) {return neuts;}
        if(x>=a && y<=b) {return upval(cur);}
        prop(cur);
        SV ans = query(a,b,cur->lson)&query(a,b,cur->rson);
        return ans;
    }
    
    void CreateCopy(node *cur)
    {
        node *X = new node(cur->ind,m[cur->ind/2],cur->sv,cur->lv); 
        X->lson=cur->lson; X->rson=cur->rson;
        m[cur->ind]=X;
        if(cur->ind==1) {X->rootind=root.size(); root.pb(X); anc.pb(cur->rootind);}
    }
    
    void update(LV s, ll a, ll b, node *cur) //update LV, range [a,b], current node, current range. initially: update(s,a,b,0,S.N-1,root[x]). This will create a new seg tree version.
    {
        ll x=cur->l; ll y=cur->r;
        if(y<a || x>b) {return;}
        CreateCopy(cur);
        node *X=m[cur->ind];
        if(x>=a && y<=b) 
        {
            X->lv=s&X->lv; 
            if(X->ind>=N) {X->sv=upval(X); X->lv=neutl;}
            return;
        }
        if(cur->lson==nullptr) {node *Z=new node(2*cur->ind,cur,neuts,neutl);}
        if(cur->rson==nullptr) {node *Z=new node(2*cur->ind+1,cur,neuts,neutl);}
        update(s,a,b,cur->lson); update(s,a,b,cur->rson);
        X->sv=upval(cur->lson)&upval(cur->rson);
    }
};

class WDiGraph
{
    public:
    ll N;
    vector<vector<pl> > adj; 
    vector<bool> visited;
    vector<ll> current; //for CC
    vector<bool> c; //for Bip
    bool bip; //for Bip
    vector<ll> TS;//Top Sort
    vector<ll> SCC; //Attributes a number to each node
    vector<vector<pl> > adjK; //reverse graph, for Kosaraju
    vector<bool> pr; //for Djikstra
    vector<ll> nv; //for Floyd
    vector<bool> deleted; //dynamic graph
    vector<unordered_set<ll> > adjs,adjr; //dynamic graph
    unordered_map<pl,ll,hash_pair> we; //dynamic graph 
    vector<vector<pl> > adjFlow; //MaxFlow
    unordered_map<pl,ll,hash_pair> m; //MaxFlow, m[(a,b)]=index of adjFlow[a] where b is stored, works for adj as well
    unordered_map<pl,bool,hash_pair> exist; //maxFlow
    ll src,ter; //MaxFlow, source and terminator/sink
    bool reached; //MaxFlow
    ll pathflow; //MaxFlow
    vector<ll> lev; //Layered_Network,MaxFlow
    vector<ll> nxted; //Dinics
    Matrix Madj;
    
    WDiGraph(vector<vector<pl> > ad)
    {
        adj=ad; N=adj.size(); REP(i,0,N) {pr.pb(false); nv.pb(0); visited.pb(false); c.pb(-1); SCC.pb(-1LL);}
        vector<pl> xx; REP(i,0,N) {adjK.pb(xx);}
        REP(i,0,adj.size())
        {
            REP(j,0,adj[i].size()) {adjK[adj[i][j].ff].pb(mp(i,adj[i][j].ss));}
        }
        unordered_set<ll> em; REP(i,0,N) {adjs.pb(em); adjr.pb(em);}
        REP(i,0,N)
        {
            REP(j,0,adj[i].size())
            {
                adjs[i].insert(adj[i][j].ff);
                adjr[adj[i][j].ff].insert(i);
                we[mp(i,adj[i][j].ff)]=adj[i][j].ss;
            }
        }
        REP(i,0,N) {deleted.pb(false);}
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
        current.clear();
        unordered_set<ll>::iterator it;
        REP(i,0,N) {adj[i].clear();it=adjs[i].begin(); while(it!=adjs[i].end()) {adj[i].pb(mp(*it,we[mp(i,*it)])); it++;}}
    }
    
    void DFS(ll s) 
    {
        if(visited[s]) {return;}
        visited[s]=true;
        REP(i,0,adj[s].size())
        {
            if(!visited[adj[s][i].ff]) {c[adj[s][i].ff]=(c[s]+1)%2; DFS(adj[s][i].ff);}
            else if(c[adj[s][i].ff]==c[s]) {bip=false;}
        }
        current.pb(s); //only needed for Kosaraju
        return;
    }
    
    vector<ll> BFS(ll s) 
    {
        vector<ll> distance; REP(i,0,N) {distance.pb(INF);}
        REP(i,0,N) {visited[i]=false;}
        distance[s]=0; visited[s]=true;
        deque<ll> d; d.pb(s); ll cur;
        while(!d.empty())
        {
            cur=d.front(); d.pop_front();
            REP(i,0,adj[cur].size())
            {
                if(!visited[adj[cur][i].ff]) 
                {
                    visited[adj[cur][i].ff]=true; 
                    d.pb(adj[cur][i].ff); 
                    distance[adj[cur][i].ff]=distance[cur]+1;
                }
            }
        }
        return distance;
    }
    
    bool Bip()
    {
        c[0]=0; 
        bip=true;
        DFS(0);
        if(bip) {return true;}
        else {return false;}
    }
    
    void DFSTS(ll s)
    {
        REP(i,0,adj[s].size()) 
        {
            if(!visited[adj[s][i].ff]) {DFSTS(adj[s][i].ff);}
        }
        visited[s]=true;
    }
    
    void TopSort()
    {
        Reset();
        REP(i,0,N)
        {
            if(visited[i]) {continue;}
            DFSTS(i);
        }
        reverse(TS.begin(),TS.end());
    }
    
    void DFSK(ll s) 
    {
        if(visited[s]) {return;}
        visited[s]=true;
        REP(i,0,adjK[s].size())
        {
            if(!visited[adjK[s][i].ff]) {DFSK(adjK[s][i].ff);}
        }
        current.pb(s); //only needed for Kosaraju
        return;
    }
    
    void Kosaraju()
    {
        if(SCC[0]!=-1) {return;}
        Reset();
        REP(i,0,N) 
        {
            if(visited[i]) {continue;}
            DFS(i);
        }
        vector<ll> List=current;
        Reset();
        ll c=0LL;
        for(ll i=N-1LL;i>=0LL;i--)
        {
            ll node=List[i];
            if(visited[node]) {continue;}
            DFSK(node);
            REP(j,0,current.size()) {SCC[current[j]]=c;}
            c++;
            current.clear();
        }
    }
    
    WDiGraph SCCGraph()
    {
        Kosaraju();
        set<pair<pl,ll> > ed;
        REP(i,0,adj.size())
        {
            REP(j,0,adj[i].size())
            {
                ed.insert(mp(mp(SCC[i],SCC[adj[i][j].ff]),adj[i][j].ss));
            }
        }
        vector<vector<pl> > a; vector<pl> xx;
        ll nscc=-INF; REP(i,0,N) {nscc=max(nscc,SCC[i]+1LL);}
        REP(i,0,nscc) {a.pb(xx);}
        set<pair<pl,ll> >::iterator it=ed.begin();
        pair<pl,ll> cur; pl last=mp(-1,-1);
        while(it!=ed.end())
        {
            cur=*it;
            if(cur.ff!=last && cur.ff.ff!=cur.ff.ss) {a[cur.ff.ff].pb(mp(cur.ff.ss,cur.ss)); } //only shortes paths are relevant
            last=cur.ff;
            it++;
        }
        WDiGraph ans(a);
        return ans;
    }
    
    vector<ll> Djikstra(ll s)
    {
        Reset();
        vector<ll> d; REP(i,0,N) {d.pb(INF);}
        d[s]=0;
        priority_queue<pl> q;
        q.push(mp(0,s));
        ll cur;
        while(!q.empty())
        {
            cur=q.top().ss; q.pop();
            if(pr[cur]) {continue;}
            pr[cur]=true; 
            REP(i,0,adj[cur].size())
            {
                if(d[adj[cur][i].ff]>d[cur]+adj[cur][i].ss)
                {
                    d[adj[cur][i].ff]=d[cur]+adj[cur][i].ss;
                    q.push(mp(-d[adj[cur][i].ff],adj[cur][i].ff));
                }
            }
        }
        return d;
    }
    
    vector<pl> Djikstra_MS(vector<ll> sn) //Djikstra Multi-sourced, ans[i].ff=d(i,sn), ans[i].ss=member of sn closest to i
    {
        Reset();
        ll K=sn.size();
        vector<pl> d; REP(i,0,N) {d.pb(mp(INF,-1LL));}
        REP(i,0,K) {d[sn[i]]=mp(0LL,sn[i]);}
        priority_queue<pl> q;
        REP(i,0,K) {q.push(mp(0,sn[i]));}
        ll cur;
        while(!q.empty())
        {
            cur=q.top().ss; q.pop();
            if(pr[cur]) {continue;}
            pr[cur]=true; 
            REP(i,0,adj[cur].size())
            {
                if(d[adj[cur][i].ff].ff>d[cur].ff+adj[cur][i].ss)
                {
                    d[adj[cur][i].ff].ff=d[cur].ff+adj[cur][i].ss;
                    d[adj[cur][i].ff].ss=d[cur].ss;
                    q.push(mp(-d[adj[cur][i].ff].ff,adj[cur][i].ff));
                }
            }
        }
        return d;
    }
    
    vector<ll> SPFA(ll s)
    {
        Reset();
        vector<ll> d; REP(i,0,N) {d.pb(INF);}
        d[s]=0;
        deque<ll> tv; tv.pb(s); pr[s]=true;
        ll cur; ll mv=0;
        while(!tv.empty())
        {
            cur=tv.front(); tv.pop_front(); pr[cur]=false;
            nv[cur]++; mv=max(mv,nv[cur]);
            REP(i,0,adj[cur].size())
            {
                if(d[adj[cur][i].ff]>d[cur]+adj[cur][i].ss)
                {
                    d[adj[cur][i].ff]=d[cur]+adj[cur][i].ss;
                    if(!pr[adj[cur][i].ff]) {tv.pb(adj[cur][i].ff);}
                    pr[adj[cur][i].ff]=true;
                }
            }
            if(mv>=N) {d.clear(); break;} //negative cycle
        }
        return d;
    }
    
    vector<pl> SPFA_MS(vector<ll> sn)
    {
        ll K=sn.size();
        Reset();
        vector<pl> d; REP(i,0,N) {d.pb(mp(INF,-1LL));}
        REP(i,0,K) {d[sn[i]]=mp(0LL,sn[i]);}
        deque<ll> tv; REP(i,0,K) {tv.pb(sn[i]); pr[sn[i]]=true;}
        ll cur; ll mv=0;
        while(!tv.empty())
        {
            cur=tv.front(); tv.pop_front(); pr[cur]=false;
            nv[cur]++; mv=max(mv,nv[cur]);
            REP(i,0,adj[cur].size())
            {
                if(d[adj[cur][i].ff].ff>d[cur].ff+adj[cur][i].ss)
                {
                    d[adj[cur][i].ff].ff=d[cur].ff+adj[cur][i].ss;
                    d[adj[cur][i].ff].ss=d[cur].ss;
                    if(!pr[adj[cur][i].ff]) {tv.pb(adj[cur][i].ff);}
                    pr[adj[cur][i].ff]=true;
                }
            }
            if(mv>=N) {d.clear(); break;} //negative cycle
        }
        return d;
    }
    
    vector<vector<ll> > Floyd() //assumes there is no neg cycle
    {
        Reset();
        vector<vector<ll> > d; vector<ll> xx; REP(i,0,N) {xx.pb(INF);} REP(i,0,N) {d.pb(xx);}
        REP(i,0,N) 
        {
            d[i][i]=0;
            REP(j,0,adj[i].size())
            {
                d[i][adj[i][j].ff]=adj[i][j].ss;
            }
        }
        REP(i,0,N)
        {
            REP(q1,0,N) 
            {
                REP(q2,0,N)
                {
                    if(q1==q2) {continue;}
                    d[q1][q2]=min(d[q1][q2],d[q1][i]+d[i][q2]);
                }
            }
        }
        return d;
    }
    
    void erase_edge(pl edge)
    {
        adjs[edge.ff].erase(edge.ss); adjr[edge.ss].erase(edge.ff);
    }
    
    void add_edge(pair<pl,ll> edge)
    {
        if(adjs[edge.ff.ff].find(edge.ff.ss)==adjs[edge.ff.ff].end()) 
        {
            we[edge.ff]=edge.ss; 
            adjs[edge.ff.ff].insert(edge.ff.ss); adjr[edge.ff.ss].insert(edge.ff.ff);
        }
        else
        {
            we[edge.ff]+=edge.ss;
        }
    }
    
    void erase_node(ll s)
    {
        deleted[s]=true; 
        unordered_set<ll>::iterator it; it=adjs[s].begin(); vector<pl> e;
        while(it!=adjs[s].end())
        {
            e.pb(mp(s,*it));
            it++;
        }
        REP(i,0,e.size()) {erase_edge(e[i]);}
    }
    
    void add_node(vector<pl> in, vector<pl> out) // adds node with adjacency list con, and index N
    {
        N++; pr.pb(false); nv.pb(0); deleted.pb(false); unordered_set<ll> em; vector<pl> emm; adjs.pb(em); adj.pb(emm);
        REP(i,0,in.size()) {add_edge(mp(mp(in[i].ff,N-1),in[i].ss));}
        REP(i,0,out.size()) {add_edge(mp(mp(N-1,out[i].ff),out[i].ss));}
    }
    
    void RGConstructor(ll source, ll terminator) //Constructs Residual Grap, adjFlow, map m
    {
        src=source; ter=terminator;
        adjFlow=adj;
        REP(i,0,N) 
        {
            REP(j,0,adj[i].size()) {m[mp(i,adj[i][j].ff)]=j; exist[mp(i,adj[i][j].ff)]=true;}
        }
        REP(i,0,N)
        {
            REP(j,0,adj[i].size()) 
            {
                if(!exist[mp(adj[i][j].ff,i)]) {adjFlow[adj[i][j].ff].pb(mp(i,0LL)); m[mp(adj[i][j].ff,i)]=adjFlow[adj[i][j].ff].size()-1;}
            }
        }
        REP(i,0,N) {lev.pb(-1); nxted.pb(0LL);}
    }
    
    void ResetFlow()
    {
        REP(i,0,N) {visited[i]=false;}
        pathflow=0LL; reached=false;
    }
    
    void BFSFlow(ll s) //builds Layered Network
    {
        Reset();
        REP(i,0,N) {lev[i]=INF;}
        REP(i,0,N) {visited[i]=false;}
        lev[s]=0; visited[s]=true;
        deque<ll> d; d.pb(s); ll cur;
        while(!d.empty())
        {
            cur=d.front(); d.pop_front();
            REP(i,0,adjFlow[cur].size())
            {
                ll node=adjFlow[cur][i].ff;
                if(!visited[node] && adjFlow[cur][i].ss>0LL) 
                {
                    visited[node]=true; 
                    d.pb(node); 
                    lev[node]=lev[cur]+1;
                }
            }
        }
    }
    
    void DFSFlow1(ll s, ll flow, ll D) //Scaling
    {
        if(reached) {return;}
        if(visited[s]) {return;}
        ll node,we;
        if(s==ter) {reached=true; pathflow=flow; return;}
        visited[s]=true;
        REP(i,0,adjFlow[s].size())
        {
            node=adjFlow[s][i].ff; we=adjFlow[s][i].ss;
            if(visited[node]) {continue;}
            if(we<D) {continue;}
            DFSFlow1(node,min(flow,we),D);
            if(reached) 
            {
                adjFlow[s][i].ss-=pathflow; 
                adjFlow[node][m[mp(node,s)]].ss+=pathflow;
                break;
            }
        }
        return;
    }
    
    void DFSFlow2(ll s, ll flow) //Dinics
    {
        if(reached) {return;}
        if(visited[s]) {return;}
        ll node,we;
        if(s==ter) {reached=true; pathflow=flow; return;}
        visited[s]=true;
        REP(i,nxted[s],adjFlow[s].size())
        {
            node=adjFlow[s][i].ff; we=adjFlow[s][i].ss;
            if(visited[node]) {continue;}
            if(we==0) {continue;}
            if(lev[node]<=lev[s]) {nxted[s]++;continue;}
            DFSFlow2(node,min(flow,we));
            if(reached) 
            {
                adjFlow[s][i].ss-=pathflow; 
                if(adjFlow[s][i].ss==0) {nxted[s]++;}
                adjFlow[node][m[mp(node,s)]].ss+=pathflow;
                break;
            }
            nxted[s]++;
        }
        return;
    }
    
    ll MF_Scaling(ll source, ll terminator) //min(O(E*MaxFlow),O(E^2*log(Emax))), prefered choice for weighted 
    {
        RGConstructor(source,terminator);
        ll flow=0LL; ll D=0LL; REP(i,0,N) {REP(j,0,adjFlow[i].size()) {D=max(D,adjFlow[i][j].ss);}}
        while(D>0LL)
        {
            ResetFlow(); DFSFlow1(src,INF,D);
            if(reached) {flow+=pathflow;}
            else {D=D/2LL;}
        }
        return flow;
    }
    
    ll MF_Dinic(ll source, ll terminator) //O(EV^2), specil case unweighted graph: min(O(EV^2/3),O(E^3/2)), special case unit network: O(EV^1/2)
    {
        RGConstructor(source,terminator);
        ll flow=0LL; bool al=true;
        while(1>0)
        {
            ResetFlow(); DFSFlow2(src,INF);
            if(reached) {al=true; flow+=pathflow;}
            else if(!al) {break;}
            else {REP(i,0,N) {nxted[i]=0LL;} al=false; BFSFlow(src);}
        }
        return flow;
    }
    
    vector<pl> MinCut(ll source, ll terminator)
    {
        MF_Dinic(source, terminator);
        ResetFlow(); DFSFlow1(src,INF,1);
        vector<pl> ans;
        REP(i,0,N)
        {
            REP(j,0,adj[i].size())
            {
                if(visited[i] && !visited[adj[i][j].ff]) {ans.pb(mp(i,adj[i][j].ff));}
            }
        }
        return ans;
    }
    
    Matrix SMul(Matrix A, Matrix B)
    {
        if(A.M!=B.N) {Matrix ANS; return ANS;}
        vector<double> xx; vector<vector<double> > ans; REP(i,0,B.M) {xx.pb((double) (INF));} REP(i,0,A.N) {ans.pb(xx);}
        REP(i,0,A.N)
        {
            REP(j,0,B.M)
            {
                double val=(double) INF;
                REP(k,0,A.M) {val=min(val,A.a[i][k]+B.a[k][j]);}
                ans[i][j]=val;
            }
        }
        Matrix ANS(ans); return ANS;
    }
    
    Matrix fastexpS(Matrix A, ll e) //O(N^3loge)
    {
        if(A.N!=A.M) {Matrix ANS; return ANS;}
        if(e<0) {A.RRE();if(A.rank==0) {e=0LL;} else {return fastexpS(*(A.Inv),-e);}}
        if(e==0) 
        {Matrix ANS=A; REP(i,0,A.N) {REP(j,0,A.N) {if(i!=j) {ANS.a[i][j]=(double) INF;} else {ANS.a[i][j]=0.0;}}} return ANS;}
        if(e%2LL==0)
        {
            Matrix V =fastexpS(A,(ll) e/2LL); return SMul(V,V);
        }
        else
        {
            Matrix V=fastexpS(A,(ll) e/2LL); return SMul(SMul(V,V),A);
        }
    }
    
    void Build_Madj() 
    {
        if(Madj.N!=0LL) {return;}
        vector<vector<double> > madj; vector<double> xx; REP(i,0,N) {xx.pb((double) (INF));} REP(i,0,N) {madj.pb(xx);}
        REP(i,0,N) {REP(j,0,adj[i].size()) {madj[i][adj[i][j].ff]=(double) (adj[i][j].ss);}}
        Matrix B(madj); Madj=B;
    }
    
    double SP(ll a, ll b, ll length) //shortest path between a,b with fixed length, O(N^3loglength)
    {
        Build_Madj(); 
        return (fastexpS(Madj,length).a[a][b]);
    }
};

class Graph
{
    public:
    ll N;
    vector<vector<ll> > adj; 
    vector<ll> visited; //for DFS/BFS
    vector<ll> current; //for CC
    vector<bool> c; //for Bip
    bool bip; //for Bip
    unordered_map<pair<vector<bool>,ll>,vector<ll>,hash_pair> mH; //for Hamiltonian
    vector<list<ll> > ad; //for Hierholzer
    unordered_map<pl,bool,hash_pair> valid; //for Hierholzer
    Matrix Madj;
    vector<ll> og; //node i points to value og[i]
    vector<vector<ll> > dfs_tree;
    
    Graph() {ll N=0LL;}
    
    Graph(vector<vector<ll> > ad)
    {
        adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false); c.pb(-1);}
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
        current.clear();
    }
    
    void DFS(ll s) 
    {
        if(visited[s]) {return;}
        visited[s]=true;
        current.pb(s); //only needed for CC
        REP(i,0,adj[s].size())
        {
            if(!visited[adj[s][i]]) {c[adj[s][i]]=(c[s]+1)%2; DFS(adj[s][i]);}
            else if(c[adj[s][i]]==c[s]) {bip=false;}
        }
        return;
    }
    
    void DFS_Tree(ll s)
    {
        if(visited[s]) {return;}
        visited[s]=true;
        REP(i,0,adj[s].size())
        {
            if(!visited[adj[s][i]]) {dfs_tree[s].pb(adj[s][i]); dfs_tree[adj[s][i]].pb(s); DFS_Tree(adj[s][i]);}
        }
        return;
    }
    
    bool Connected()
    {
        Reset();
        DFS(0);
        REP(i,0,N) {if(!visited[i]) {return false;}}
        return true;
    }
    
    vector<ll> BFS(ll s)
    {
        Reset();
        vector<ll> distance; REP(i,0,N) {distance.pb(INF);}
        REP(i,0,N) {visited[i]=false;}
        distance[s]=0; visited[s]=true;
        deque<ll> d; d.pb(s); ll cur;
        while(!d.empty())
        {
            cur=d.front(); d.pop_front();
            REP(i,0,adj[cur].size())
            {
                if(!visited[adj[cur][i]]) 
                {
                    visited[adj[cur][i]]=true; 
                    d.pb(adj[cur][i]); 
                    distance[adj[cur][i]]=distance[cur]+1;
                }
            }
        }
        return distance;
    }
    
    vector<pl> BFS_MS(vector<ll> sn) //multi-sourced BFS, ans[i].ff=d(i,starting nodes), ans[i].ss=starting node closer to i
    {
        Reset();
        ll K=sn.size();
        vector<pl> distance; REP(i,0,N) {distance.pb(mp(INF,-1LL));}
        REP(i,0,N) {visited[i]=false;}
        REP(i,0,K) {distance[sn[i]]=mp(0LL,sn[i]); visited[sn[i]]=true;}
        deque<ll> d; REP(i,0,K) {d.pb(sn[i]);} ll cur;
        while(!d.empty())
        {
            cur=d.front(); d.pop_front();
            REP(i,0,adj[cur].size())
            {
                if(visited[adj[cur][i]]) {continue;}
                visited[adj[cur][i]]=true; 
                d.pb(adj[cur][i]); 
                distance[adj[cur][i]].ff=distance[cur].ff+1;
                distance[adj[cur][i]].ss=distance[cur].ss;
            }
        }
        return distance;
    }
    
    vector<vector<ll> > CC()
    {
        Reset();
        ll fi=0; ll missing=N; REP(i,0,N) {visited[i]=false;}
        vector<vector<ll> > ans;
        while(missing>0)
        {
            REP(i,fi,N) {if(!visited[i]) {fi=i; break;}}
            current.clear();
            DFS(fi);
            ans.pb(current);
            missing-=current.size();
        }
        return ans;
    }
    
    vector<Graph> CCG()
    {
        Reset();
        vector<Graph> ans;
        vector<vector<ll> > CC=(*this).CC();
        unordered_map<ll,ll> m;vector<ll> xx; vector<vector<ll> > ad;
        vector<ll> ma;
        REP(cc,0,CC.size()) 
        {
            m.clear(); ma.clear();
            ad.clear(); 
            ll NN=CC[cc].size();
            REP(i,0,NN) {ad.pb(xx);}
            REP(i,0,NN) {m[CC[cc][i]]=i; ma[i]=ma[CC[cc][i]];}
            ll a,b;
            REP(i,0,NN)
            {
                a=CC[cc][i];
                REP(j,0,adj[a].size()) {b=adj[a][j]; ad[i].pb(m[b]);}
            }
            Graph H(ad); H.og=ma;
            ans.pb(H);
        }
        return ans;
    }
    
    bool Bip()
    {
        Reset();
        bip=true;
        REP(i,0,N)
        {
            if(visited[i]) {continue;}
            c[i]=0LL; DFS(i);
        }
        if(bip) {return true;}
        else {return false;}
    }
    
    bool Eulerian()
    {
        Reset();
        REP(i,0,N) {if(adj[i].size()%2!=0) {return false;}}
        return true;
    }
    
    vector<ll> Hamiltonian()
    {
        bool Ore=true;
        vector<bool> v; REP(i,0,N) {v.pb(true);}
        REP(i,0,N)
        {
            REP(j,0,N) {v[j]=true;}
            v[i]=false;
            REP(j,0,adj[i].size()) {v[adj[i][j]]=false;}
            REP(j,0,N) 
            {
                if(v[j] && adj[i].size()+adj[j].size()<N) {Ore=false; break;}
            }
        }
        if(Ore) {return Palmer();}
        REP(i,0,N) {v[i]=true;}
        REP(i,0,N) 
        {
            if(!f(v,i).empty()) {return f(v,i);}
        }
        vector<ll> ans; return ans;
    }
    
    vector<ll> f(vector<bool> v, ll x) //O(N^2*2^N), for when we dont know anything about the graph
    {
        if(!mH[mp(v,x)].empty()) {return mH[mp(v,x)];}
        ll oc=0LL; REP(i,0,N) {if(v[i]) {oc++;}}
        vector<ll> ans;
        if(oc==1) {ans.pb(x);}
        else
        {
            v[x]=false; ll node;
            REP(i,0,adj[x].size())
            {
                node=adj[x][i];
                if(!v[node]) {continue;}
                vector<ll> p=f(v,node);
                if(!p.empty()) {p.pb(x); ans=p; break;}
            }
        }
        mH[mp(v,x)]=ans;
        return ans;
    }
    
    vector<ll> Palmer() //O(N^2), constructs Hamiltonian Cycle if Ore's condition is fullfilled
    {
        vector<ll> ans; REP(i,0,N) {ans.pb(i);}
        vector<vector<bool> > madj; vector<bool> dummy; REP(i,0,N) {dummy.pb(false);} REP(i,0,N) {madj.pb(dummy);}
        REP(i,0,N) {REP(j,0,adj[i].size()) {madj[i][adj[i][j]]=true; madj[adj[i][j]][i]=true;}}
        REP(cnt,0,N)
        {
            ll ind1=-1LL;
            REP(i,0,N)
            {
                if(!madj[ans[i]][ans[(i+1)%N]]) {ind1=i; break;}
            }
            if(ind1==-1) {break;}
            ll ind2=-1LL;
            REP(j,0,N)
            {
                if(madj[ans[ind1]][ans[j]] && madj[ans[(ind1+1)%N]][ans[(j+1)%N]]) {ind2=j; break;}
            }
            REP(i,0,((ind2-ind1+N)%N +1)/2LL)
            {
                ll node1=(ind1+1+i)%N;
                ll node2=(ind2-i)%N;
                swap(ans[node1],ans[node2]);
            }
        }
        return ans;
    }
    
    void Tour(ll s)
    {
        current.pb(s);
        if(ad[s].size()==0) {return;}
        ll nxt=*ad[s].begin();
        while(!valid[mp(s,nxt)]) 
        {
            valid[mp(nxt,s)]=false; ad[s].erase(ad[s].begin()); 
            if(ad[s].size()==0) {return;}
            nxt=*ad[s].begin();
        }
        valid[mp(s,nxt)]=false; valid[mp(nxt,s)]=false;
        ad[s].erase(ad[s].begin());
        Tour(nxt);
    }
    
    vector<ll> Hierholzer()
    {
        ll nodd=0LL; REP(i,0,N) {if(adj[i].size()%2!=0) {nodd++;}}
        list<ll> ans;
        if(nodd>2LL) {vector<ll> xx; return xx;}
        vector<vector<ll> > indiferent=CC(); ll nsb1=0LL;
        REP(i,0,indiferent.size()) {if(indiferent[i].size()>1LL) {nsb1++;}}
        if(nsb1>1LL) {vector<ll> xx; return xx;}
        ll sn=0LL; REP(i,0,N) {if(adj[i].size()%2!=0) {sn=i;}}
        list<ll> xx;
        REP(i,0,N) {xx.clear(); xx.insert(xx.begin(),adj[i].begin(),adj[i].end()); ad.pb(xx);}
        ans.insert(ans.begin(),sn);
        list<ll>::iterator it=ans.begin();
        REP(i,0,N) {REP(j,0,adj[i].size()) {valid.insert(mp(mp(i,adj[i][j]),true));}}
        REP(i,0,INF)
        {
            if(it==ans.end()) {break;}
            current.clear();
            Tour(*it);
            it=ans.erase(it);
            it=ans.insert(it,current.begin(),current.end());
            it++;
        }
        it=ans.begin();
        vector<ll> f_ans; REP(i,0,ans.size()) {f_ans.pb(*it); it++;}
        return f_ans;
    }
    
    ll MaxMatching()
    {
        if(!Bip()) {return -1;}
        vector<vector<pl> > Wadj; vector<pl> xx; REP(i,0,N+2) {Wadj.pb(xx);}
        REP(i,0,N)
        {
            if(c[i]==1) {Wadj[i].pb(mp(N+1,1)); continue;}
            Wadj[N].pb(mp(i,1));
            REP(j,0,adj[i].size())
            {
                Wadj[i].pb(mp(adj[i][j],1));
            }
        }
        WDiGraph G(Wadj);
        return G.MF_Dinic(N,N+1);
    }
    
    void Build_Madj() 
    {
        if(Madj.N!=0LL) {return;}
        vector<vector<double> > madj; vector<double> xx; REP(i,0,N) {xx.pb(0.0);} REP(i,0,N) {madj.pb(xx);}
        REP(i,0,N) {REP(j,0,adj[i].size()) {madj[i][adj[i][j]]=1.0;}}
        Matrix B(madj); Madj=B;
    }
    
    ll cnt_path(ll a, ll b, ll length)
    {
        Build_Madj();
        return fastexp(Madj,length).a[a][b]; 
    }
};

class DynamicGraph
{
    public:
    ll N; ll nxt_id; 
    
    class node
    {
        public:
        ll id; //unique non-negative integer id
        unordered_set<ll> adj;
        node() {id=-1;}
        node(ll ident, vector<ll> ad) {id=ident; REP(i,0,ad.size()) {adj.insert(ad[i]);}}
    };
    
    unordered_map<ll,node> m;
    unordered_set<ll> active_id; //active node ids
    
    DynamicGraph(vector<vector<ll> > adj)
    {
        N=adj.size();
        REP(i,0,N)
        {
            node X(i,adj[i]);
            m[i]=X;
            active_id.insert(i);
        }
        nxt_id=N;
    }
    
    void add_edge(pl edge)
    {
        m[edge.ff].adj.insert(edge.ss);
        m[edge.ss].adj.insert(edge.ff);
    }
    
    void erase_edge(pl edge)
    {
        m[edge.ff].adj.erase(edge.ss);
        m[edge.ss].adj.erase(edge.ff);
    }
    
    void add_node(vector<ll> ad)
    {
        N++; vector<ll> em;
        node X(nxt_id,em); m[nxt_id]=X; active_id.insert(nxt_id); nxt_id++;
        REP(i,0,ad.size())
        {
            add_edge(mp(nxt_id-1,ad[i]));
        }
    }
    
    void erase_node(ll id)
    {
        N--;
        vector<pl> toerase;
        unordered_set<ll>::iterator it=m[id].adj.begin();
        while(it!=m[id].adj.end()) 
        {
            toerase.pb(mp(id,*it)); it++;
        }
        REP(i,0,toerase.size()) {erase_edge(toerase[i]);}
        active_id.erase(id);
        m.erase(id);
    }
};

class DynamicDiGraph
{
    public:
    ll N; ll nxt_id; 
    
    class node
    {
        public:
        ll id; //unique non-negative integer id
        unordered_set<ll> adj;
        unordered_set<ll> adjr;
        node() {id=-1;}
        node(ll ident, vector<ll> ad) {id=ident; REP(i,0,ad.size()) {adj.insert(ad[i]);}}
    };
    
    unordered_map<ll,node> m;
    unordered_set<ll> active_id; //active node ids
    
    DynamicDiGraph(vector<vector<ll> > adj)
    {
        N=adj.size();
        REP(i,0,N)
        {
            node X;
            m[i]=X;
            active_id.insert(i);
        }
        nxt_id=N;
        REP(i,0,N)
        {
            REP(j,0,adj[i].size())
            {
                m[i].adj.insert(adj[i][j]);
                m[adj[i][j]].adjr.insert(i);
            }
        }
    }
    
    void add_edge(pl edge)
    {
        m[edge.ff].adj.insert(edge.ss);
        m[edge.ss].adjr.insert(edge.ff);
    }
    
    void erase_edge(pl edge)
    {
        m[edge.ff].adj.erase(edge.ss);
        m[edge.ss].adjr.erase(edge.ff);
    }
    
    void add_node(vector<ll> in,vector<ll> out)
    {
        N++; vector<ll> em;
        node X(nxt_id,em); m[nxt_id]=X; active_id.insert(nxt_id); nxt_id++;
        REP(i,0,in.size())
        {
            add_edge(mp(in[i],nxt_id-1));
        }
        REP(i,0,out.size())
        {
            add_edge(mp(nxt_id-1,out[i]));
        }
        
    }
    
    void erase_node(ll id)
    {
        N--;
        vector<pl> toerase;
        unordered_set<ll>::iterator it;
        it=m[id].adj.begin();
        while(it!=m[id].adj.end()) 
        {
            toerase.pb(mp(id,*it)); it++;
        }
        it=m[id].adjr.begin();
        while(it!=m[id].adjr.end())
        {
            toerase.pb(mp(*it,id)); it++;
        }
        REP(i,0,toerase.size()) {erase_edge(toerase[i]);}
        active_id.erase(id);
        m.erase(id);
    }
};

class DynamicWG
{
    public:
    ll N; ll nxt_id; 
    unordered_map<pl,ll,hash_pair> we;
    
    class node
    {
        public:
        ll id; //unique non-negative integer id
        unordered_set<ll> adj;
        node() {id=-1;}
        node(ll ident, vector<ll> ad) {id=ident; REP(i,0,ad.size()) {adj.insert(ad[i]);}}
    };
    
    unordered_map<ll,node> m;
    unordered_set<ll> active_id; //active node ids
    
    DynamicWG(vector<vector<pl> > adj)
    {
        N=adj.size();
        vector<ll> em;
        REP(i,0,N)
        {
            node X(i,em);
            REP(j,0,adj[i].size()) {X.adj.insert(adj[i][j].ff); we[mp(i,adj[i][j].ff)]=adj[i][j].ss; we[mp(adj[i][j].ff,i)]=adj[i][j].ss;}
            m[i]=X;
            active_id.insert(i);
        }
        nxt_id=N;
    }
    
    void add_edge(pair<pl,ll> edge)
    {
        if(m[edge.ff.ff].adj.find(edge.ff.ss)!=m[edge.ff.ff].adj.end())
        {
            we[edge.ff]+=edge.ss; swap(edge.ff.ff,edge.ff.ss);
            we[edge.ff]+=edge.ss;
        }
        else
        {
            m[edge.ff.ff].adj.insert(edge.ff.ss);
            m[edge.ff.ss].adj.insert(edge.ff.ff);  
            we[edge.ff]=edge.ss; swap(edge.ff.ff,edge.ff.ss); we[edge.ff]=edge.ss;
        }
    }
    
    void erase_edge(pl edge)
    {
        m[edge.ff].adj.erase(edge.ss);
        m[edge.ss].adj.erase(edge.ff);
        we.erase(edge);
    }
    
    void add_node(vector<pl> ad)
    {
        N++; vector<ll> em;
        node X(nxt_id,em); m[nxt_id]=X; active_id.insert(nxt_id); nxt_id++;
        REP(i,0,ad.size())
        {
            add_edge(mp(mp(nxt_id-1,ad[i].ff),ad[i].ss)); 
        }
    }
    
    void erase_node(ll id)
    {
        N--;
        vector<pl> toerase;
        unordered_set<ll>::iterator it=m[id].adj.begin();
        while(it!=m[id].adj.end()) 
        {
            toerase.pb(mp(id,*it)); it++;
        }
        REP(i,0,toerase.size()) {erase_edge(toerase[i]);}
        active_id.erase(id);
        m.erase(id);
    }
};

class DynamicWDiGraph
{
    public:
    ll N; ll nxt_id; 
    unordered_map<pl,ll,hash_pair> we;
    
    class node
    {
        public:
        ll id; //unique non-negative integer id
        unordered_set<ll> adj;
        unordered_set<ll> adjr;
        node() {id=-1;}
        node(ll ident, vector<ll> ad) {id=ident; REP(i,0,ad.size()) {adj.insert(ad[i]);}}
    };
    
    unordered_map<ll,node> m;
    unordered_set<ll> active_id; //active node ids
    
    DynamicWDiGraph(vector<vector<pl> > adj)
    {
        N=adj.size();
        REP(i,0,N)
        {
            node X;
            m[i]=X;
            active_id.insert(i);
        }
        nxt_id=N;
        REP(i,0,N)
        {
            REP(j,0,adj[i].size())
            {
                m[i].adj.insert(adj[i][j].ff);
                m[adj[i][j].ff].adjr.insert(i);
                we[mp(i,adj[i][j].ff)]=adj[i][j].ss;
            }
        }
    }
    
    void add_edge(pair<pl,ll> edge)
    {
        if(m[edge.ff.ff].adj.find(edge.ff.ss)!=m[edge.ff.ff].adj.end())
        {
            we[edge.ff]+=edge.ss;
        }
        else
        {
            m[edge.ff.ff].adj.insert(edge.ff.ss);
            m[edge.ff.ss].adjr.insert(edge.ff.ff);   
            we[edge.ff]=edge.ss;
        }
    }
    
    void erase_edge(pl edge)
    {
        m[edge.ff].adj.erase(edge.ss);
        m[edge.ss].adjr.erase(edge.ff);
        we.erase(edge);
    }
    
    void add_node(vector<pl> in,vector<pl> out)
    {
        N++; vector<ll> em;
        node X(nxt_id,em); m[nxt_id]=X; active_id.insert(nxt_id); nxt_id++;
        REP(i,0,in.size())
        {
            add_edge(mp(mp(in[i].ff,nxt_id-1),in[i].ss));
        }
        REP(i,0,out.size())
        {
            add_edge(mp(mp(nxt_id-1,out[i].ff),out[i].ss));
        }
        
    }
    
    void erase_node(ll id)
    {
        N--;
        vector<pl> toerase;
        unordered_set<ll>::iterator it;
        it=m[id].adj.begin();
        while(it!=m[id].adj.end()) 
        {
            toerase.pb(mp(id,*it)); it++;
        }
        it=m[id].adjr.begin();
        while(it!=m[id].adjr.end())
        {
            toerase.pb(mp(*it,id)); it++;
        }
        REP(i,0,toerase.size()) {erase_edge(toerase[i]);}
        active_id.erase(id);
        m.erase(id);
    }
};

class Tree
{
    public:
    ll N; 
    vector<ll> p; 
    vector<vector<ll> > sons;
    vector<vector<ll> > adj;
    ll root;
    vector<bool> visited;
    vector<ll> level; //starting in 0
    vector<ll> sub; //number of nodes in subtree
    vector<ll> val; //node values
    vector<ll> DFSarr1; //DFS Array
    vector<ll> DFSarr2; //DFS Array for LCA with whole path
    vector<ll> pos; //inverted DFSArr, only for LCA
    vector<pl> levDFSarr; //array of levels on DFSarr, only needed for LCA
    vector<ll> sumto; //weighted graph, length of path root-->i
    SparseTable<pl> S; //for LCA
    SucPath P; //for function f
    ll max_steps; //for function f
    vector<ll> prufer; //Prufer code, defines a tree uniquely
    vector<ll> dist; 
    pair<ll,pl> diametre;
    unordered_set<ll> included; //create new tree
    vector<vector<ll> > back_edge; //in the case this tree is a DFS-tree
    vector<pl> bridge; 
    vector<ll> articulation_point;
    vector<ll> high_be; //highest back_edge per node
    vector<ll> high_sub; //highest back_edge in subtree
    vector<vector<ll> > farthest_dir;
    vector<ll> farthest_down;
    vector<ll> farthest_up;
    vector<ll> farthest;
    
    Tree(vector<vector<ll> > ad, ll r=0LL)
    {
        N=ad.size(); root=r; adj=ad;
        REP(i,0,N) {visited.pb(false);}
        vector<ll> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1); level.pb(0); sub.pb(1LL); pos.pb(0LL); sumto.pb(0LL);}
        DFS_Build(r,r);
        REP(i,0,DFSarr2.size()) {pos[DFSarr2[i]]=i;}
        REP(i,0,DFSarr2.size()) {levDFSarr.pb(mp(level[DFSarr2[i]],DFSarr2[i]));}
        SparseTable<pl> X(levDFSarr); S=X;
        max_steps=N;
        SucPath Y(p,N); P=Y;
        REP(i,0,N) {val.pb(0LL);}
        vector<ll> xxx;
        REP(i,0,N) {farthest_up.pb(0); farthest_down.pb(0); farthest_dir.pb(xxx); farthest.pb(0);}
        REP(i,0,N) {REP(j,0,adj[i].size()) {farthest_dir[i].pb(0);}}
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
    }
    
    void DFS_Build(ll s, ll par)
    {
        DFSarr1.pb(s);
        DFSarr2.pb(s);
        if(s!=root) {level[s]=level[par]+1LL;}
        p[s]=par;
        visited[s]=true;
        REP(i,0,adj[s].size())
        {
            if(adj[s][i]==par) {continue;}
            sons[s].pb(adj[s][i]);
            DFS_Build(adj[s][i],s);
            sub[s]+=sub[adj[s][i]];
            DFSarr2.pb(s);
        }
        return;
    }
    
    void DFS_sumto(ll s)
    {
        sumto[s]=sumto[p[s]]+val[s];
        REP(i,0,sons[s].size()) 
        {
            DFS_sumto(sons[s][i]);
        }
    }
    
    void DFS_distance(ll s, ll las)
    {
        REP(i,0,adj[s].size()) 
        {
            if(adj[s][i]==las) {continue;}
            dist[adj[s][i]]=dist[s]+1;
            DFS_distance(adj[s][i],s);
        }
    }
    
    void distance(ll s)
    {
        dist.clear(); REP(i,0,N) {dist.pb(INF);}
        dist[s]=0;
        DFS_distance(s,s);
    }
    
    void Calc_Diametre()
    {
        distance(root); 
        vector<ll>::iterator it=max_element(whole(dist));
        ll ind=it-dist.begin();
        distance(ind);
        diametre.ss.ff=ind;
        it=max_element(whole(dist));
        diametre.ss.ss=it-dist.begin();
        diametre.ff=*it;
    }
    
    void DFS(ll s, ll las=-1LL)
    {
        REP(i,0,adj[s].size())
        {
            if(adj[s][i]==las) {continue;}
            DFS(adj[s][i],s);
        }
        included.insert(s);
    }
    
    ll LCA(ll a, ll b)
    {
        a=pos[a]; b=pos[b]; 
        ll l=min(a,b); ll r=max(a,b);
        pl ans=S.query(l,r);
        return ans.ss;
    }
    
    ll d1(ll a, ll b)
    {
        return level[a]+level[b]-2*level[LCA(a,b)];
    }
    
    ll d2(ll a, ll b)
    {
        return sumto[a]+sumto[b]-2*sumto[LCA(a,b)];
    }  
    
    ll f(ll x, ll k)
    {
        return P.f(x,k);
    }
    
    vector<Tree> CC()
    {
        vector<Tree> ans;
        Graph G(adj);
        vector<Graph> CC_step=G.CCG();
        REP(i,0,CC_step.size()) {Tree T(CC_step[i].adj,0); ans.pb(T);}
        return ans;
    }
    
    void Build_Prufer() //O(N)
    {
        ll ptr=0LL; vector<bool> v; REP(i,0,N) {v.pb(true);}
        vector<ll> nadj; REP(i,0,N) {nadj.pb(adj[i].size());}
        ll leaf;
        while(prufer.size()<N-2LL)
        {
            while(nadj[ptr]!=1LL && ptr<N)  {ptr++;}
            leaf=ptr;
            while(leaf<=ptr && prufer.size()<N-2LL)
            {
                v[leaf]=false;
                REP(i,0,adj[leaf].size()) {if(v[adj[leaf][i]]) {leaf=adj[leaf][i]; break;}}
                prufer.pb(leaf);
                nadj[leaf]--; if(nadj[leaf]>1) {break;}
            }
            ptr++;
        }
        return;
    }
    
    Tree Subtree(ll s)
    {
        included.clear();
        DFS(s,p[s]);
        unordered_map<ll,ll> m;
        unordered_set<ll>::iterator it;
        it=included.begin();
        ll cnt=0LL;
        while(it!=included.end())
        {
            m[*it]=cnt; cnt++; it++;
        }
        it=included.begin();
        vector<ll> xx; vector<vector<ll> > ad;
        REP(i,0,included.size()) {ad.pb(xx);}
        REP(i,0,sons[s].size())
        {
            ad[0].pb(m[sons[s][i]]);
        }
        it++; cnt=1LL;
        while(it!=included.end())
        {
            REP(i,0,adj[*it].size())
            {
                ad[cnt].pb(m[adj[*it][i]]);
            }
            it++; cnt++;
        }
        Tree ANS(ad);
        return ANS;
    }
    
    Tree Uptree(ll s)
    {
        if(s==root) {vector<vector<ll> > adj; Tree T(adj); return T;}
        included.clear();
        DFS(p[s],s);
        unordered_map<ll,ll> m;
        unordered_set<ll>::iterator it;
        it=included.begin();
        ll cnt=0LL;
        while(it!=included.end())
        {
            m[*it]=cnt; cnt++; it++;
        }
        it=included.begin();
        vector<ll> xx; vector<vector<ll> > ad;
        REP(i,0,included.size()) {ad.pb(xx);}
        cnt=0LL;
        while(it!=included.end())
        {
            REP(i,0,adj[*it].size())
            {
                if(adj[*it][i]==s) {continue;}
                ad[cnt].pb(m[adj[*it][i]]);
            }
            it++; cnt++;
        }
        Tree ANS(ad);
        return ANS;
    }
    
    vector<Tree> Split(ll s) //forest created by removing node s
    {
        vector<Tree> ANS;
        REP(i,0,sons[s].size())
        {
            ANS.pb(Subtree(sons[s][i]));
        }
        if(s!=root) {ANS.pb(Uptree(s));}
        return ANS;
    }
    
    ll centroid()
    {
        REP(i,0,N)
        {
            ll max_tree = 0LL;
            REP(j,0,sons[i].size()) {max_tree=max(max_tree,sub[sons[i][j]]);}
            max_tree=max(max_tree,N-sub[i]);
            if(max_tree<=N/2) {return i;}
        }
        return 0LL;
    }
    
    class HeavyPath
    {
        public:
        ll N;
        ll low, high;
        Tree *T;
        ST S;
        
        HeavyPath() {N=0LL;}
        HeavyPath(ll x, ll y, Tree *K)
        {
            T=K;
            low=x; high=y;
            if(T->level[x]<T->level[y]) {swap(high,low);}
            N = T->level[x]-T->level[y]+1LL;
            vector<ll> st_val; ll c = low;
            while(1>0) {st_val.pb(T->val[c]); if(c==high) {break;} c=T->p[c];}
            ST R(st_val); S=R;
        }
        
        ll pos(ll x)
        {
            return (T->level[low]-T->level[x]);
        }
        
        ST::SV query(ll ind1, ll ind2)
        {
            return S.query(ind1,ind2);
        }
        
        void update(ST::LV X, ll ind1, ll ind2)
        {
            S.update(X,ind1,ind2);
        }
    };
    
    vector<HeavyPath *> h_path; //heavy paths
    unordered_map<ll,HeavyPath *> HP; //m[s] = heavy path including s
    
    void HLD()
    {
        vector<ll> large; ll c; 
        REP(i,0,N)
        {
            ll node=-1; ll ls = -1LL;
            REP(j,0,sons[i].size())
            {
                c=sons[i][j];
                if(sub[c]>=ls) {ls=sub[c]; node=c;}
            }
            large.pb(node);
        }
        REP(i,0,N)
        {
            if(sons[i].size()>0) {continue;}
            c=i; 
            while(c!=root && c==large[p[c]]) {c=p[c];}
            HeavyPath *P = new HeavyPath(i,c,this);
            c=i; while(1>0) {HP[c]=P; if(c==P->high) {break;} c=p[c];}
            h_path.pb(P);
        }
    }
    
    ST::SV query_ancestor(ll s, ll anc)
    {
        ST::SV ans;
        if(level[s]<level[anc]) {return ans;}
        ll c = s;
        while(1>0)
        {
            ST::SV thispath;
            if(level[HP[c]->high]>=level[anc])
            {
                thispath = HP[c]->query(HP[c]->pos(c),HP[c]->N-1);
            }
            else
            {
                thispath = HP[c]->query(HP[c]->pos(c),HP[c]->pos(anc));
            }
            ans=ans&thispath;
            c=HP[c]->high; c=p[c];
            if(c==root || level[c]<level[anc]) {break;}
        }
        return ans;
    }
    
    ST::SV query(ll a, ll b) //query along path a->b
    {
        ll lca = LCA(a,b);
        ST::SV V1 = query_ancestor(a,lca);
        ST::SV V2; if(b!=lca) {V2= query_ancestor(b,f(b,level[b]-level[lca]-1LL));}
        return V1&V2;
    }
    
    void update_ancestor(ST::LV X, ll s, ll anc) 
    {
        if(level[s]<level[anc]) {return;}
        ll c = s;
        while(1>0)
        {
            if(level[HP[c]->high]>=level[anc])
            {
                HP[c]->update(X,HP[c]->pos(c),HP[c]->N-1);
            }
            else
            {
                HP[c]->update(X,HP[c]->pos(c),HP[c]->pos(anc));
            }
            c=HP[c]->high; if(c==root) {break;} c=p[c];
            if(level[c]<level[anc]) {break;}
        }
    }
    
    void update(ST::LV X, ll a, ll b) 
    {
        ll lca = LCA(a,b);
        update_ancestor(X,a,lca);
        if(b!=lca) {update_ancestor(X,b,f(b,level[b]-level[lca]-1LL));}
    }
    
    void High_Sub(ll s)
    {
        REP(i,0,sons[s].size()) {High_Sub(sons[s][i]);}
        REP(i,0,sons[s].size()) {ll c=sons[s][i]; high_sub[s]=min(high_sub[s],high_sub[c]);}
    }
    
    void Init_Back_Edge(vector<vector<ll> > be)
    {
        back_edge=be;
        REP(i,0,N) {high_be.pb(level[i]); high_sub.pb(level[i]);}
        REP(i,0,N)
        {
            REP(j,0,back_edge[i].size())
            {
                ll c = back_edge[i][j];
                high_be[i]=min(high_be[i],level[c]);
            }
        }
        REP(i,0,N) {high_sub[i]=high_be[i];}
        High_Sub(root);
    }
    
    void FindBridge()
    {
        REP(i,0,N)
        {
            if(i==root) {continue;}
            if(high_sub[i]==level[i]) {bridge.pb(mp(i,p[i]));}
        }
    }
    
    void FindArticulationPoint()
    {
        REP(i,0,N)
        {
            bool include=false;
            if(i==root) 
            {
                if(sons[i].size()>1LL) {articulation_point.pb(i);}
                continue;
            }
            REP(j,0,sons[i].size())
            {
                ll c = sons[i][j];
                if(high_sub[c]==level[c]) {include=true;}
            }
            if(include) {articulation_point.pb(i);}
        }
    }
    
    void Calc_farthest_down(ll s)
    {
        REP(i,0,sons[s].size()) {Calc_farthest_down(sons[s][i]);}
        REP(i,0,adj[s].size()) 
        {
            if(adj[s][i]==p[s]) {continue;}
            farthest_dir[s][i]=farthest_down[adj[s][i]]+val[adj[s][i]];
            farthest_down[s]=max(farthest_down[s],farthest_dir[s][i]);
        }
    }
    
    void Calc_farthest_up(ll s)
    {
        if(s==root) {farthest_up[s]=0LL;}
        pl best_dis=mp(0,0);
        REP(i,0,adj[s].size()) 
        {
            if(farthest_dir[s][i]>best_dis.ff) {best_dis.ss=best_dis.ff; best_dis.ff=farthest_dir[s][i];}
            else if(farthest_dir[s][i]>best_dis.ss) {best_dis.ss=farthest_dir[s][i];}
        }
        REP(i,0,adj[s].size())
        {
            if(adj[s][i]==p[s]) {continue;}
            ll c = adj[s][i];
            if(best_dis.ff == farthest_dir[s][i]) {farthest_up[c] = best_dis.ss+val[c];}
            else {farthest_up[c]=best_dis.ff+val[c];}
            REP(j,0,adj[c].size()) {if(adj[c][j]==s) {farthest_dir[c][j]=farthest_up[c];}}
        }
        REP(i,0,sons[s].size()) {Calc_farthest_up(sons[s][i]);}
    }
    
    void Calc_farthest()
    {
        Calc_farthest_down(root);
        Calc_farthest_up(root);
        REP(i,0,N) {farthest[i]=max(farthest_up[i],farthest_down[i]);}
    }
};

Tree DFS_Tree(Graph G, ll s)
{
    vector<ll> xx; REP(i,0,G.N) {G.dfs_tree.pb(xx);}
    G.DFS_Tree(s);
    Tree T(G.dfs_tree,s);
    vector<vector<ll> > be; REP(i,0,T.N) {be.pb(xx);}
    ll a,b,c;
    REP(i,0,G.N)
    {
        REP(j,0,G.adj[i].size())
        {
            c = G.adj[i][j];
            a=i; b=c;
            if(a>b) {continue;}
            if(T.level[a]>T.level[b]) {swap(a,b);}
            if(T.p[b]!=a) {be[b].pb(a);}
        }
    }
    T.Init_Back_Edge(be);
    return T;
}

Tree Prufer(vector<ll> p) //constructs a Tree given unique Prufer code in O(N)
{
    ll N=p.size()+2LL;
    vector<vector<ll> > adj; vector<ll> xx; REP(i,0,N) {adj.pb(xx);}
    ll ptr=0LL; vector<bool> v; REP(i,0,N) {v.pb(true);}
    vector<ll> nadj; REP(i,0,N) {nadj.pb(1);}
    REP(i,0,N-2) {nadj[p[i]]++;}
    ll leaf; ll added=0LL;
    while(added<N-2LL)
    {
        while(nadj[ptr]!=1LL && ptr<N)  {ptr++;}
        leaf=ptr; 
        while(leaf<=ptr && added<N-2LL)
        {
            v[leaf]=false; nadj[leaf]--; ll par=p[added]; nadj[par]--; 
            adj[leaf].pb(par); adj[par].pb(leaf);
            added++;
            if(nadj[par]>1) {break;}
            leaf=par;
        }
        ptr++;
    }
    vector<ll> missing; 
    REP(i,0,N) {if(nadj[i]!=0LL) {missing.pb(i);}}
    adj[missing[0]].pb(missing[1]); adj[missing[1]].pb(missing[0]);
    Tree T(adj,0LL);
    return T;
}

class WTree
{
    public:
    ll N; 
    vector<ll> p; 
    vector<vector<pl> > sons;
    vector<vector<pl> > adj;
    ll root;
    vector<ll> level; //starting in 0
    
    WTree(vector<vector<pl> > ad, ll r)
    {
        N=ad.size(); root=r; adj=ad;
        vector<pl> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1); level.pb(0);}
        DFS_Build(r,r);
    }
    
    void DFS_Build(ll s, ll par)
    {
        if(s!=root) {level[s]=level[par]+1LL;}
        p[s]=par;
        REP(i,0,adj[s].size())
        {
            if(adj[s][i].ff==par) {continue;}
            sons[s].pb(adj[s][i]);
            DFS_Build(adj[s][i].ff,s);
        }
        return;
    }
    
    Tree Conv()
    {
        vector<vector<ll> > ad; vector<ll> xx; REP(i,0,N) {ad.pb(xx);}
        vector<ll> values; REP(i,0,N) {values.pb(0LL);}
        REP(i,0,N) {REP(j,0,adj[i].size()) {if(adj[i][j].ff==p[i]) {values[i]=adj[i][j].ss;} ad[i].pb(adj[i][j].ff);}}
        Tree T(ad,root); T.val=values; T.DFS(T.root);
        return T;
    } 
};

class WG //everything works for weighted directed graphs except dynamic graph
{
    public:
    ll N; vector<vector<pl> > adj;
    vector<unordered_set<ll> > adjs; //for dynamic graph
    unordered_map<pl,ll,hash_pair> we; //for dynamic graph
    vector<bool> pr; vector<ll> nv; 
    vector<bool> deleted;
    Matrix Madj;
    
    WG(vector<vector<pl> > ad)
    {
        adj=ad; N=adj.size();
        REP(i,0,N) {pr.pb(false); nv.pb(0);}
        REP(i,0,N) {deleted.pb(false);}
        unordered_set<ll> em; REP(i,0,N) {adjs.pb(em); }
        REP(i,0,N)
        {
            REP(j,0,adj[i].size())
            {
                adjs[i].insert(adj[i][j].ff); we[mp(i,adj[i][j].ff)]=adj[i][j].ss;
            }
        }
    }
    
    void Reset()
    {
        REP(i,0,N) {pr[i]=false;nv.pb(0);}
        unordered_set<ll>::iterator it;
        REP(i,0,N) {adj[i].clear(); it=adjs[i].begin(); while(it!=adjs[i].end()) {adj[i].pb(mp(*it,we[mp(i,*it)])); it++;}}
    }
    
    vector<ll> Djikstra(ll s)
    {
        Reset();
        vector<ll> d; REP(i,0,N) {d.pb(INF);}
        d[s]=0;
        priority_queue<pl> q;
        q.push(mp(0,s));
        ll cur;
        while(!q.empty())
        {
            cur=q.top().ss; q.pop();
            if(pr[cur]) {continue;}
            pr[cur]=true; 
            REP(i,0,adj[cur].size())
            {
                if(d[adj[cur][i].ff]>d[cur]+adj[cur][i].ss)
                {
                    d[adj[cur][i].ff]=d[cur]+adj[cur][i].ss;
                    q.push(mp(-d[adj[cur][i].ff],adj[cur][i].ff));
                }
            }
        }
        return d;
    }
    
    vector<pl> Djikstra_MS(vector<ll> sn) //Djikstra Multi-sourced, ans[i].ff=d(i,sn), ans[i].ss=member of sn closest to i
    {
        Reset();
        ll K=sn.size();
        vector<pl> d; REP(i,0,N) {d.pb(mp(INF,-1LL));}
        REP(i,0,K) {d[sn[i]]=mp(0LL,sn[i]);}
        priority_queue<pl> q;
        REP(i,0,K) {q.push(mp(0,sn[i]));}
        ll cur;
        while(!q.empty())
        {
            cur=q.top().ss; q.pop();
            if(pr[cur]) {continue;}
            pr[cur]=true; 
            REP(i,0,adj[cur].size())
            {
                if(d[adj[cur][i].ff].ff>d[cur].ff+adj[cur][i].ss)
                {
                    d[adj[cur][i].ff].ff=d[cur].ff+adj[cur][i].ss;
                    d[adj[cur][i].ff].ss=d[cur].ss;
                    q.push(mp(-d[adj[cur][i].ff].ff,adj[cur][i].ff));
                }
            }
        }
        return d;
    }
    
    vector<ll> SPFA(ll s)
    {
        Reset();
        vector<ll> d; REP(i,0,N) {d.pb(INF);}
        d[s]=0;
        deque<ll> tv; tv.pb(s); pr[s]=true;
        ll cur; ll mv=0;
        while(!tv.empty())
        {
            cur=tv.front(); tv.pop_front(); pr[cur]=false;
            nv[cur]++; mv=max(mv,nv[cur]);
            REP(i,0,adj[cur].size())
            {
                if(d[adj[cur][i].ff]>d[cur]+adj[cur][i].ss)
                {
                    d[adj[cur][i].ff]=d[cur]+adj[cur][i].ss;
                    if(!pr[adj[cur][i].ff]) {tv.pb(adj[cur][i].ff);}
                    pr[adj[cur][i].ff]=true;
                }
            }
            if(mv>=N) {d.clear(); break;} //negative cycle
        }
        return d;
    }
    
    vector<pl> SPFA_MS(vector<ll> sn)
    {
        ll K=sn.size();
        Reset();
        vector<pl> d; REP(i,0,N) {d.pb(mp(INF,-1LL));}
        REP(i,0,K) {d[sn[i]]=mp(0LL,sn[i]);}
        deque<ll> tv; REP(i,0,K) {tv.pb(sn[i]); pr[sn[i]]=true;}
        ll cur; ll mv=0;
        while(!tv.empty())
        {
            cur=tv.front(); tv.pop_front(); pr[cur]=false;
            nv[cur]++; mv=max(mv,nv[cur]);
            REP(i,0,adj[cur].size())
            {
                if(d[adj[cur][i].ff].ff>d[cur].ff+adj[cur][i].ss)
                {
                    d[adj[cur][i].ff].ff=d[cur].ff+adj[cur][i].ss;
                    d[adj[cur][i].ff].ss=d[cur].ss;
                    if(!pr[adj[cur][i].ff]) {tv.pb(adj[cur][i].ff);}
                    pr[adj[cur][i].ff]=true;
                }
            }
            if(mv>=N) {d.clear(); break;} //negative cycle
        }
        return d;
    }
    
    vector<vector<ll> > Floyd() //assumes there is no neg cycle
    {
        Reset();
        vector<vector<ll> > d; vector<ll> xx; REP(i,0,N) {xx.pb(INF);} REP(i,0,N) {d.pb(xx);}
        REP(i,0,N) 
        {
            d[i][i]=0;
            REP(j,0,adj[i].size())
            {
                d[i][adj[i][j].ff]=adj[i][j].ss;
            }
        }
        REP(i,0,N)
        {
            REP(q1,0,N) 
            {
                REP(q2,0,N)
                {
                    if(q1==q2) {continue;}
                    d[q1][q2]=min(d[q1][q2],d[q1][i]+d[i][q2]);
                }
            }
        }
        return d;
    }
    
    WTree Kruskal() //Minimum Spanning Tree, O(MlogM)
    {
        vector<pair<ll,pl> > ed; vector<vector<pl> > ad; vector<pl> xx; REP(i,0,N) {ad.pb(xx);}
        pair<ll,pl> cur;
        REP(i,0,N)
        {
            cur.ss.ff=i;
            REP(j,0,adj[i].size())
            {
                cur.ss.ss=adj[i][j].ff;
                cur.ff=adj[i][j].ss;
                ed.pb(cur);
            }
        }
        sort(ed.begin(),ed.end()); DSU D(N); ll a,b,we;
        REP(i,0,ed.size())
        {
            a=ed[i].ss.ff; b=ed[i].ss.ss; we=ed[i].ff;
            if(D.find(a)!=D.find(b)) 
            {
                D.unionn(a,b); ad[a].pb(mp(b,we)); ad[b].pb(mp(a,we));
            }
        }
        WTree T(ad,0);
        return T;
    }
    
    WTree Prim() //Minimim Spanning Tree, O(MlogM)
    {
        vector<vector<pl> > ad; vector<pl> xx; REP(i,0,N) {ad.pb(xx);}
        vector<bool> inT; REP(i,0,N) {inT.pb(false);}
        priority_queue<pair<pl,pl> > q;
        q.push(mp(mp(0,0),mp(0,0))); ll s;
        while(!q.empty())
        {
            s=q.top().ff.ss; pl bef=q.top().ss; q.pop(); 
            if(inT[s]) {continue;}
            inT[s]=true; 
            if(s!=0) {ad[s].pb(bef); ad[bef.ff].pb(mp(s,bef.ss));}
            REP(i,0,adj[s].size())
            {
                if(inT[adj[s][i].ff]) {continue;}
                q.push(mp(mp(-adj[s][i].ss,adj[s][i].ff),mp(s,adj[s][i].ss)));
            }
        }
        WTree T(ad,0); 
        return T;
    }
    
    void erase_edge(pl edge)
    {
        adjs[edge.ff].erase(edge.ss); adjs[edge.ss].erase(edge.ff);
    }
    
    void add_edge(pair<pl,ll> edge)
    {
        if(adjs[edge.ff.ff].find(edge.ff.ss)==adjs[edge.ff.ff].end()) 
        {
            we[edge.ff]=edge.ss; swap(edge.ff.ff,edge.ff.ss);
            we[edge.ff]=edge.ss; swap(edge.ff.ff,edge.ff.ss);
            adjs[edge.ff.ff].insert(edge.ff.ss);
            adjs[edge.ff.ss].insert(edge.ff.ff);
        }
        else
        {
            we[edge.ff]+=edge.ss; swap(edge.ff.ff,edge.ff.ss);
            we[edge.ff]+=edge.ss;
        }
    }
    
    void erase_node(ll s)
    {
        deleted[s]=true; 
        unordered_set<ll>::iterator it; it=adjs[s].begin(); vector<pl> e;
        while(it!=adjs[s].end())
        {
            e.pb(mp(s,*it));
            it++;
        }
        REP(i,0,e.size()) {erase_edge(e[i]);}
    }
    
    void add_node(vector<pl> con) // adds node with adjacency list con, and index N
    {
        N++; pr.pb(false); nv.pb(0); deleted.pb(false); unordered_set<ll> em; vector<pl> emm; adjs.pb(em); adj.pb(emm);
        REP(i,0,con.size()) {add_edge(mp(mp(N-1,con[i].ff),con[i].ss));}
    }
    
    Matrix SMul(Matrix A, Matrix B)
    {
        if(A.M!=B.N) {Matrix ANS; return ANS;}
        vector<double> xx; vector<vector<double> > ans; REP(i,0,B.M) {xx.pb((double) (INF));} REP(i,0,A.N) {ans.pb(xx);}
        REP(i,0,A.N)
        {
            REP(j,0,B.M)
            {
                double val=(double) INF;
                REP(k,0,A.M) {val=min(val,A.a[i][k]+B.a[k][j]);}
                ans[i][j]=val;
            }
        }
        Matrix ANS(ans); return ANS;
    }
    
    Matrix fastexpS(Matrix A, ll e) //O(N^3loge)
    {
        if(A.N!=A.M) {Matrix ANS; return ANS;}
        if(e<0) {A.RRE();if(A.rank==0) {e=0LL;} else {return fastexpS(*(A.Inv),-e);}}
        if(e==0) 
        {Matrix ANS=A; REP(i,0,A.N) {REP(j,0,A.N) {if(i!=j) {ANS.a[i][j]=(double) INF;} else {ANS.a[i][j]=0.0;}}} return ANS;}
        if(e%2LL==0)
        {
            Matrix V =fastexpS(A,(ll) e/2LL); return SMul(V,V);
        }
        else
        {
            Matrix V=fastexpS(A,(ll) e/2LL); return SMul(SMul(V,V),A);
        }
    }
    
    void Build_Madj() 
    {
        if(Madj.N!=0LL) {return;}
        vector<vector<double> > madj; vector<double> xx; REP(i,0,N) {xx.pb((double) (INF));} REP(i,0,N) {madj.pb(xx);}
        REP(i,0,N) {REP(j,0,adj[i].size()) {madj[i][adj[i][j].ff]=(double) (adj[i][j].ss);}}
        Matrix B(madj); Madj=B;
    }
    
    double SP(ll a, ll b, ll length) //shortest path between a,b with fixed length, O(N^3loglength)
    {
        Build_Madj();
        return (fastexpS(Madj,length).a[a][b]);
    }
};

class DiGraph
{
    public:
    ll N;
    vector<vector<ll> > adj; 
    vector<bool> visited;
    vector<ll> current; //for CC
    vector<bool> c; //for Bip
    bool bip; //for Bip
    vector<ll> TS;//Top Sort
    vector<ll> SCC; //Attributes a number to each node
    vector<vector<ll> > adjK; //reverse graph, for Kosaraju
    vector<unordered_set<ll> > adjs; vector<unordered_set<ll> > adjr; //dynamic graph
    vector<bool> deleted; //dynamic graph
    unordered_map<pair<vector<bool>,ll>,vector<ll>,hash_pair> mH; //Hamiltonian
    vector<list<ll> > ad; //for Hierholzer
    Matrix Madj;
    
    DiGraph(vector<vector<ll> > ad)
    {
        adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false); c.pb(-1); SCC.pb(-1LL);}
        vector<ll> xx; REP(i,0,N) {adjK.pb(xx);}
        REP(i,0,adj.size())
        {
            REP(j,0,adj[i].size()) {adjK[adj[i][j]].pb(i);}
        }
        unordered_set<ll> em; REP(i,0,N) {adjs.pb(em); adjr.pb(em);}
        REP(i,0,N)
        {
            REP(j,0,adj[i].size())
            {
                adjs[i].insert(adj[i][j]);
                adjr[adj[i][j]].insert(i);
            }
        }
        REP(i,0,N) {deleted.pb(false);}
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
        current.clear();
        unordered_set<ll>::iterator it;
        REP(i,0,N) {adj[i].clear();it=adjs[i].begin(); while(it!=adjs[i].end()) {adj[i].pb(*it); it++;}}
    }
    
    void DFS(ll s) 
    {
        if(visited[s]) {return;}
        visited[s]=true;
        REP(i,0,adj[s].size())
        {
            if(!visited[adj[s][i]]) {c[adj[s][i]]=(c[s]+1)%2; DFS(adj[s][i]);}
            else if(c[adj[s][i]]==c[s]) {bip=false;}
        }
        current.pb(s); //only needed for Kosaraju
        return;
    }
    
    vector<ll> BFS(ll s) 
    {
        vector<ll> distance; REP(i,0,N) {distance.pb(INF);}
        REP(i,0,N) {visited[i]=false;}
        distance[s]=0; visited[s]=true;
        deque<ll> d; d.pb(s); ll cur;
        while(!d.empty())
        {
            cur=d.front(); d.pop_front();
            REP(i,0,adj[cur].size())
            {
                if(!visited[adj[cur][i]]) 
                {
                    visited[adj[cur][i]]=true; 
                    d.pb(adj[cur][i]); 
                    distance[adj[cur][i]]=distance[cur]+1;
                }
            }
        }
        return distance;
    }
    
    bool Bip()
    {
        c[0]=0; 
        bip=true;
        DFS(0);
        if(bip) {return true;}
        else {return false;}
    }
    
    void DFSTS(ll s)
    {
        REP(i,0,adj[s].size()) 
        {
            if(!visited[adj[s][i]]) {DFSTS(adj[s][i]);}
        }
        visited[s]=true; TS.pb(s);
    }
    
    void TopSort()
    {
        Reset();
        REP(i,0,N)
        {
            if(visited[i]) {continue;}
            DFSTS(i);
        }
        reverse(TS.begin(),TS.end());
    }
    
    void DFSK(ll s) 
    {
        if(visited[s]) {return;}
        visited[s]=true;
        REP(i,0,adjK[s].size())
        {
            if(!visited[adjK[s][i]]) {DFSK(adjK[s][i]);}
        }
        current.pb(s); //only needed for Kosaraju
        return;
    }
    
    void Kosaraju()
    {
        if(SCC[0]!=-1) {return;}
        Reset();
        REP(i,0,N) 
        {
            if(visited[i]) {continue;}
            DFS(i);
        }
        vector<ll> List=current;
        Reset();
        ll c=0LL;
        for(ll i=N-1LL;i>=0LL;i--)
        {
            ll node=List[i];
            if(visited[node]) {continue;}
            DFSK(node);
            REP(j,0,current.size()) {SCC[current[j]]=c;}
            c++;
            current.clear();
        }
    }
    
    DiGraph SCCGraph()
    {
        Kosaraju();
        set<pl> ed;
        REP(i,0,adj.size())
        {
            REP(j,0,adj[i].size())
            {
                ed.insert(mp(SCC[i],SCC[adj[i][j]]));
            }
        }
        vector<vector<ll> > a; vector<ll> xx;
        ll nscc=-INF; REP(i,0,N) {nscc=max(nscc,SCC[i]+1LL);}
        REP(i,0,nscc) {a.pb(xx);}
        set<pl>::iterator it=ed.begin();
        pl cur;
        while(it!=ed.end())
        {
            cur=*it;
            if(cur.ff!=cur.ss) {a[cur.ff].pb(cur.ss);}
            it++;
        }
        DiGraph ans(a);
        return ans;
    }
    
    void erase_edge(pl edge)
    {
        adjs[edge.ff].erase(edge.ss);
        adjr[edge.ss].erase(edge.ff);
    }
    
    void add_edge(pl edge)
    {
        adjs[edge.ff].insert(edge.ss);
        adjr[edge.ss].insert(edge.ff);
        adj[edge.ff].pb(edge.ss);
    }
    
    void erase_node(ll s)
    {
        deleted[s]=true; 
        unordered_set<ll>::iterator it; vector<pl> e;
        if(adjs[s].size()>0) {it=adjs[s].begin(); while(it!=adjs[s].end()) {e.pb(mp(s,*it)); it++;}}
        if(adjr[s].size()>0) {it=adjr[s].begin(); while(it!=adjr[s].end()) {e.pb(mp(*it,s)); it++;}}
        REP(i,0,e.size()) {erase_edge(e[i]);}
    }
    
    void add_node(vector<ll> in, vector<ll> out) // adds node with adjacency list con, and index N
    {
        unordered_set<ll> em; adjs.pb(em); adjr.pb(em); vector<ll> emm; adj.pb(emm); deleted.pb(false); N++;
        SCC.pb(-1);
        REP(i,0,out.size()) {add_edge(mp(N-1,out[i]));}
        REP(i,0,in.size()) {add_edge(mp(in[i],N-1));}
    }
    
    vector<ll> Hamiltonian()
    {
        vector<bool> v; REP(i,0,N) {v.pb(true);}
        REP(i,0,N) {v[i]=true;}
        REP(i,0,N) 
        {
            if(!f(v,i).empty()) {return f(v,i);}
        }
        vector<ll> ans; return ans;
    }
    
    vector<ll> f(vector<bool> v, ll x) //O(N^2*2^N), for when we dont know anything about the graph
    {
        if(!mH[mp(v,x)].empty()) {return mH[mp(v,x)];}
        ll oc=0LL; REP(i,0,N) {if(v[i]) {oc++;}}
        vector<ll> ans;
        if(oc==1) {ans.pb(x);}
        else
        {
            v[x]=false; ll node;
            REP(i,0,adjK[x].size())
            {
                node=adjK[x][i];
                if(!v[node]) {continue;}
                vector<ll> p=f(v,node);
                if(!p.empty()) {p.pb(x); ans=p; break;}
            }
        }
        mH[mp(v,x)]=ans;
        return ans;
    }
    
    void Tour(ll s)
    {
        current.pb(s);
        if(ad[s].size()==0) {return;}
        ll nxt=*ad[s].begin(); ad[s].erase(ad[s].begin());
        Tour(nxt);
    }
    
    vector<ll> Hierholzer() //O(M)
    {
        vector<ll> indeg; vector<ll> outdeg; REP(i,0,N) {indeg.pb(0LL); outdeg.pb(0LL);}
        REP(i,0,N) {REP(j,0,adj[i].size()) {outdeg[i]++; indeg[adj[i][j]]++;}}
        ll onep=0LL; ll onem=0LL; ll un=0LL;
        REP(i,0,N)
        {
            if(outdeg[i]-indeg[i]==-1) {onem++;}
            else if(outdeg[i]-indeg[i]==1) {onep++;}
            else if(abs(outdeg[i]-indeg[i])>1) {un++;}
        }
        if(un!=0LL || onem>1LL || onep>1LL) {vector<ll> xxx; return xxx;}
        ll sn=0LL; REP(i,0,N) {if(outdeg[i]-indeg[i]==1LL) {sn=i;}}
        Reset(); DFS(sn); REP(i,0,N) {if(!visited[i]) {vector<ll> xxx; return xxx;}}
        list<ll> ans;
        list<ll> xx; 
        REP(i,0,N) {xx.clear(); xx.insert(xx.begin(),adj[i].begin(),adj[i].end()); ad.pb(xx);}
        ans.insert(ans.begin(),sn);
        list<ll>::iterator it=ans.begin();
        REP(i,0,INF)
        {
            if(it==ans.end()) {break;}
            current.clear();
            Tour(*it);
            it=ans.erase(it);
            it=ans.insert(it,current.begin(),current.end());
            it++;
        }
        it=ans.begin();
        vector<ll> f_ans; REP(i,0,ans.size()) {f_ans.pb(*it); it++;}
        return f_ans;
    }
    
    ll Edge_Disjoint(ll source, ll terminator) //max number of edge disjoint pahts source --> terminator
    {
        vector<vector<pl> > Wadj; vector<pl> xx; REP(i,0,N) {Wadj.pb(xx);}
        REP(i,0,N)
        {
            REP(j,0,adj[i].size()) {Wadj[i].pb(mp(adj[i][j],1LL));}
        }
        WDiGraph G(Wadj);
        return G.MF_Dinic(source,terminator);
    }
    
    ll Node_Disjoint(ll source, ll terminator) //max number of node disjoint paths source --> terminator
    {
        vector<vector<pl> > Wadj; vector<pl> xx; REP(i,0,2*N) {Wadj.pb(xx);}
        REP(i,0,N)
        {
            Wadj[2*i].pb(mp(2*i+1,1));
            REP(j,0,adj[i].size()) {Wadj[2*i+1].pb(mp(2*adj[i][j],1LL));}
        }
        WDiGraph G(Wadj);
        return G.MF_Dinic(source,terminator);
    }
    
    ll Node_Disjoint_Path_Cover() //min number of node disjoint paths to cover all nodes in DAG, O(MN^1/2)
    {
        vector<vector<ll> > Uadj; vector<ll> xx; REP(i,0,2*N) {Uadj.pb(xx);}
        REP(i,0,N)
        {
            REP(j,0,adj[i].size()) {Uadj[i].pb(adj[i][j]+N); Uadj[adj[i][j]+N].pb(i);}
        }
        Graph G(Uadj);
        return (N-G.MaxMatching());
    }
    
    ll General_Path_Cover() //min number of paths to cover all nodes in DAG (situation in Dilworths Theorem), O(N^5/2 + NM)
    {
        vector<vector<ll> > Uadj; vector<ll> xx; REP(i,0,2*N) {Uadj.pb(xx);}
        REP(i,0,N) 
        {
            Reset(); DFS(i);
            REP(j,0,N) {if(j==i || !visited[j]) {continue;} Uadj[i].pb(j+N); Uadj[j+N].pb(i);}
        }
        Graph G(Uadj);
        return (N-G.MaxMatching());
    }
    
    void Build_Madj() 
    {
        if(Madj.N!=0LL) {return;}
        vector<vector<double> > madj; vector<double> xx; REP(i,0,N) {xx.pb(0.0);} REP(i,0,N) {madj.pb(xx);}
        REP(i,0,N) {REP(j,0,adj[i].size()) {madj[i][adj[i][j]]=1.0;}}
        Matrix B(madj); Madj=B;
    }
    
    ll cnt_path(ll a, ll b, ll length)
    {
        Build_Madj();
        return fastexp(Madj,length).a[a][b]; 
    }
};

template<class T=ll>
class Heap
{
    public:
    ll N; 
    vector<T> a;
    
    Heap() {N=0LL;}
    Heap(vector<T> b) //O(N)
    {
        a=b; N=a.size(); ll cur;
        REP(i,0,N)
        {
            cur=i; 
            while(cur>0LL && a[cur]>a[(cur-1)/2]) {swap(a[cur],a[(cur-1)/2]); cur=(cur-1)/2;}
        }
    }
    
    void FixDown(ll node, T val) //a[node] -> val
    {
        a[node]=val; ll cur=node;
        bool up=false;
        if(node!=0 && a[node]>a[(node-1)/2]) {up=true;}
        if(up) 
        {
            while(cur>0 && a[cur]>a[(cur-1)/2]) {swap(a[cur],a[(cur-1)/2]); cur=(cur-1)/2;}
        }
        else
        {
            while(1>0)
            {
                if(2*cur+1<N && a[2*cur+1]>a[cur]) {swap(a[2*cur+1],a[cur]); cur=2*cur+1; continue;}
                if(2*cur+2<N && a[2*cur+2]>a[cur]) {swap(a[2*cur+2],a[cur]); cur=2*cur+2; continue;}
                break;
            }
        }
    }
    
    void addElement(T val) 
    {
        a.pb(val); N++; FixDown(N-1,val);
    }
};

ostream & operator << (ostream &out, Heap<ll> &H) {Out(H.a); return out;}
istream & operator >> (istream &in, Heap<ll> &H) {ll N; cin>>N; vector<ll> a; In(a,N); H.N=N; H.a=a; return in;}

template<class T=ll>
class AVL
{
    public:
    ll N; 
    class node
    {
        public:
        T val;
        ll h;
        node *par;
        node *lson, *rson; 
        node *prv,*nxt;
        
        bool operator < (node A) {if(val<A.val) {return true;} return false;}
        bool operator > (node A) {if(val>A.val) {return true;} return false;}
        bool operator <= (node A) {if(val<=A.val) {return true;} return false;}
        bool operator >= (node A) {if(val>=A.val) {return true;} return false;}
    };
    
    node * root, *beg, *en;
    
    AVL() 
    {
        en=(node *) malloc(sizeof(node));
        en->lson=NULL; en->rson=NULL; en->par=NULL; en->h=0LL;
        en->val=INF;
        en->prv=NULL; en->nxt=NULL;
        root=en; beg=en;
        N=0LL;
    }
    
    node * begin() {return beg;}
    
    node * end() {return en;}
    
    node * find(T val)
    {
        node * cur = root;
        while(1>0)
        {
            if(cur->val==val) {return cur;}
            else if(cur->val > val && cur->lson != NULL) {cur=cur->lson;}
            else if(cur->val < val && cur->rson != NULL) {cur=cur->rson;}
            else {return en;}
        }
    }
    
    node * lower_bound(T val)
    {
        node * cur = root; node * ans=root; ll mind=INF;
        while(1>0)
        {
            if(cur->val==val) {return cur;}
            if(cur->val >val && cur->val - val <mind) {mind=cur->val - val; ans=cur;}
            if(cur->val > val && cur->lson != NULL) {cur=cur->lson;}
            else if(cur->val < val && cur->rson != NULL) {cur=cur->rson;}
            else {return ans;}
        }
    }
    
    node * upper_bound(T val)
    {
        node * cur = root; node * ans=root; ll mind=INF;
        while(1>0)
        {
            if(cur->val >val && cur->val - val <mind) {mind=cur->val - val; ans=cur;}
            if(cur->val > val && cur->lson != NULL) {cur=cur->lson;}
            else if(cur->val <= val && cur->rson != NULL) {cur=cur->rson;}
            else {return ans;}
        }
    }
    
    void Balance(node *X)
    {
        node * cur=X; bool balanced=true;
        while(1>0)
        {
            ll h1=0, h2=0;
            if(cur->lson!=NULL) {h1=cur->lson->h +1;}
            if(cur->rson!=NULL) {h2=cur->rson->h +1;}
            if(abs(h1-h2)>1) {balanced=false; break;}
            if(cur==root) {break;}
            cur=cur->par;
        }
        if(balanced) {return;}
        ll h1=0; ll h2=0;
        if(cur->lson!=NULL) {h1=cur->lson->h +1;}
        if(cur->rson!=NULL) {h2=cur->rson->h +1;}
        if(h2 > h1)
        {
            ll hl=0, hr=0;
            if(cur->rson->lson!=NULL) {hl=cur->rson->lson->h +1;}
            if(cur->rson->rson!=NULL) {hr=cur->rson->rson->h +1;}
            if(hr>hl)
            {
                (cur->h)-=2;
                node * A = cur->rson; if(cur->par==NULL) {root=A;}
                A->par=cur->par; cur->par=A; 
                cur->rson=A->lson; if(A->lson!=NULL) {A->lson->par=cur;}
                A->lson=cur;
                if(A->par != NULL)
                {
                    if(A->par->rson==cur) {A->par->rson=A;}
                    if(A->par->lson==cur) {A->par->lson=A;}
                }
                cur=A; 
                while(cur!=root)
                {
                    cur=cur->par; (cur->h)--;
                }
            }
            else
            {
                node * A = cur; node * B = A->rson; node * C = B->lson; node * D = C->lson; node * E = C->rson;
                if(root==A) {root=C;}
                C->par=A->par; 
                if(C->par != NULL)
                {
                    if(C->par->rson==A) {C->par->rson=C;}
                    if(C->par->lson==A) {C->par->lson=C;}
                }
                A->par=C; C->lson=A;
                A->rson=D; if(D!=NULL) {D->par=A;}
                B->lson=E; if(E!=NULL) {E->par=B;}
                B->par=C; C->rson=B;
                B->h=0; if(B->rson!=NULL) {B->h=B->rson->h + 1;}
                A->h=0; if(A->lson!=NULL) {A->h=A->lson->h + 1;}
                (C->h)++;
                cur=C;
                while(cur!=root)
                {
                    cur=cur->par; (cur->h)--;
                }
            }
        }
        else
        {
            ll hl=0, hr=0;
            if(cur->lson->lson!=NULL) {hl=cur->lson->lson->h +1;}
            if(cur->lson->rson!=NULL) {hr=cur->lson->rson->h +1;}
            if(hl>hr)
            {
                (cur->h)-=2;
                node * A = cur->lson; if(cur->par==NULL) {root=A;}
                A->par=cur->par; cur->par=A; 
                cur->lson=A->rson; if(A->rson!=NULL) {A->rson->par=cur;}
                A->rson=cur;
                if(A->par != NULL)
                {
                    if(A->par->rson==cur) {A->par->rson=A;}
                    if(A->par->lson==cur) {A->par->lson=A;}
                }
                cur=A;
                while(cur!=root)
                {
                    cur=cur->par; (cur->h)--;
                }
            }
            else
            {
                node * A = cur; node * B = A->lson; node * C = B->rson; node * D = C->rson; node * E = C->lson;
                if(root==A) {root=C;}
                C->par=A->par; A->par=C; A->lson=D; 
                B->rson=E; B->par=C;
                C->rson=A; C->lson=B;
                if(D!=NULL) {D->par=A;}
                if(E!=NULL) {E->par=B;}
                B->h=0; if(B->lson!=NULL) {B->h=B->lson->h + 1;}
                A->h=0; if(A->rson!=NULL) {A->h=A->rson->h + 1;}
                (C->h)++;
                if(C->par != NULL)
                {
                    if(C->par->rson==cur) {C->par->rson=C;}
                    if(C->par->lson==cur) {C->par->lson=C;}
                }
                cur=C;
                while(cur!=root)
                {
                    cur=cur->par; (cur->h)--;
                }
            }
        }
        return;
    }
    
    void insert(T val)
    {
        node * next = lower_bound(val);
        node * X = (node *) malloc(sizeof(node));
        X->val=val; X->h=0; X->par=NULL; X->lson=NULL; X->rson=NULL;
        node * cur=root;
        N++; 
        while(cur->lson != NULL && cur->rson !=NULL)
        {
            (cur->h)++;
            if(*cur>=*X) {cur=cur->lson;}
            else {cur=cur->rson;}
        }
        (cur->h)++;
        if(cur->lson==NULL && cur->rson==NULL) 
        {
            if(*cur>=*X) {cur->lson=X; X->par=cur;}
            else {cur->rson=X; X->par=cur;}
        }
        else if(cur->lson==NULL)
        {
            if(*cur>=*X) {cur->lson=X; X->par=cur;}
            else 
            {
                cur=cur->rson; (cur->h)++;
                if(*X>=*cur) {cur->rson=X; X->par=cur;}
                else {cur->lson=X; X->par=cur;}
            }
        }
        else if(cur->rson==NULL)
        {
            if(*cur<=*X) {cur->rson=X; X->par=cur;}
            else 
            {
                cur=cur->lson; (cur->h)++;
                if(*X>=*cur) {cur->rson=X; X->par=cur;}
                else {cur->lson=X; X->par=cur;}
            }
        }
        if(*X < *beg) {beg=X;}
        Balance(X);
        X->nxt=next; X->prv=(X->nxt->prv);
        X->nxt->prv=X; if(X->prv !=NULL) {X->prv->nxt=X;}
    }
    
    void erase(node *X)
    {
        X->nxt->prv=X->prv;
        if(X->prv!=NULL) {X->prv->nxt=X->nxt;}
        if(X==beg) {beg=beg->nxt;}
        if(X->lson==NULL && X->rson==NULL) 
        {
            node * cur=X; node * p = cur->par; 
            cur->h=-1; cur=p;
            while(1>0)
            {
                ll h1=0; ll h2=0;
                if(cur->lson!=NULL) {h1=cur->lson->h +1;}
                if(cur->rson!=NULL) {h2=cur->rson->h +1;}
                cur->h=max(h1,h2);
                if(cur==root) {break;}
                cur=cur->par;
            }
            cur=X;
            if((cur->par)->rson==cur) {(cur->par)->rson=NULL;}
            if((cur->par)->lson==cur) {(cur->par)->lson=NULL;}
            free(cur); 
            N--;
            Balance(p);
            return;
        }
        if(X->rson==NULL)
        {
            node * cur=X; node * p = cur->lson;
            cur->h=-1; cur=p;
            while(1>0)
            {
                ll h1=0; ll h2=0;
                if(cur->lson!=NULL) {h1=cur->lson->h +1;}
                if(cur->rson!=NULL) {h2=cur->rson->h +1;}
                cur->h=max(h1,h2);
                if(cur==root) {break;}
                cur=cur->par;
            }
            cur=X;
            if(X==root) {p->par=NULL; root=p; return;}
            if((cur->par)->rson==cur) {(cur->par)->rson=p;}
            if((cur->par)->lson==cur) {(cur->par)->lson=p;}
            p->par=cur->par;
            free(cur); 
            N--;
            Balance(p);
            return;
        }
        if(X->lson==NULL)
        {
            node * cur=X; node * p = cur->rson;
            cur->h=-1; cur=p;
            while(1>0)
            {
                ll h1=0; ll h2=0;
                if(cur->lson!=NULL) {h1=cur->lson->h +1;}
                if(cur->rson!=NULL) {h2=cur->rson->h +1;}
                cur->h=max(h1,h2);
                if(cur==root) {break;}
                cur=cur->par;
            }
            cur=X;
            if(X==root) {p->par=NULL; root=p; return;}
            if((cur->par)->rson==cur) {(cur->par)->rson=p;}
            if((cur->par)->lson==cur) {(cur->par)->lson=p;}
            p->par=cur->par;
            free(cur); 
            N--;
            Balance(p);
            return;
        }
        node * p = X->lson;
        while(p->rson!=NULL) {p=p->rson;}
        swap(X->val,p->val);
        erase(p);
    }
};

template<class T=ll>
class HashTable
{
    public:
    ll M; ll N;
    
    class node
    {
        public:
        T val; 
        bool visited; 
        node * nxt, *prv;
    };
    
    vector<node> a;
    node * be, *en;
    
    HashTable(ll m) 
    {
        M=m; node X = *((node *) malloc(sizeof(node)));
        REP(i,0,M) {a.pb(X);}
        be=(node *) malloc(sizeof(node));
        en=(node *) malloc(sizeof(node));
        be->prv=NULL; be->nxt=en;
        en->prv=be; en->nxt=NULL;
        N=0;
    }
    
    node * begin() {return be;}
    node * end() {return en;}
    
    ll hash(ll i) 
    {
        return (i%M);
    }
    
    void insert(T val) 
    {
        ll ind=hash(val);
        while(a[ind].visited)
        {
            if(a[ind].val==val) {return;}
            ind=(ind+1)%M;
        }
        a[ind].visited=true; a[ind].val=val; N++;
        a[ind].nxt=end(); a[ind].prv=en->prv; a[ind].prv->nxt=&a[ind]; en->prv=&a[ind];
        if(N==1) {be=&a[ind]; return;}
        
    }
    
    node * find(T val)
    {
        ll ind=hash(val);
        while(a[ind].visited)
        {
            if(a[ind].val==val) {return &a[ind];}
            ind=(ind+1)%M;
        }
        return end();
    }
    
    void erase(node * X)
    {
        N--;
        X->visited=false; X->val=0LL;
        X->nxt->prv=X->prv;
        if(X->prv !=NULL) {X->prv->nxt=X->nxt;}
        if(be==X) {be=X->nxt;}
    }
};

class Trie
{
    public:
    ll N;
    vector<string> val; vector<char> c;
    vector<ll> p;
    vector<vector<ll> > sons;
    unordered_set<string> a;
    unordered_map<string,ll> pos;
    
    Trie() {N=1; p.pb(0); val.pb(""); c.pb(' '); pos[""]=0; vector<ll> em; sons.pb(em);}
    
    void insert(string s)
    {
        a.insert(s);
        if(pos.find(s)!=pos.end()) {return;}
        string t=""; ll node;
        REP(i,0,s.size())
        {
            node=pos[t];
            t+=s[i];
            if(pos.find(t)==pos.end()) 
            {
                N++;vector<ll> em; sons.pb(em);
                val.pb(t);c.pb(s[i]);
                p.pb(node);
                sons[node].pb(N-1);
                pos[t]=N-1;
            }
        }
    }
};

ll LIS(vector<ll> a) //Longest strictly Increasing Subsequence in O(NlogN)
{
    vector<ll> dp; dp.pb(-INF);
    vector<ll>::iterator it;
    REP(i,0,a.size())
    {
        it=upper_bound(dp.begin(),dp.end(),a[i]);
        if(it==dp.end()) {dp.pb(a[i]); continue;}
        *it=a[i];
    }
    return dp.size()-1LL;
}

template<class T=string>
ll LCS_dp(ll i, ll j, vector<vector<ll> > &dp, T a, T b) //i means prefix s[0...i]
{
    if(i==0) {if(a[0]==b[j]) {dp[i][j]=1;} else {dp[i][j]=0;}}
    else if(j==0) {if(a[i]==b[0]) {dp[i][j]=1;} else {dp[i][j]=0;}}
    else
    {
        if(a[i]==b[j]) {dp[i][j]=LCS_dp(i-1,j-1,dp,a,b)+1;}
        else {dp[i][j]=max(LCS_dp(i-1,j,dp,a,b),LCS_dp(i,j-1,dp,a,b));}
    }
    return dp[i][j];
}

template<class T=string>
ll LCS(T a, T b)
{
    vector<ll> xx; vector<vector<ll> > dp; REP(i,0,b.size()) {xx.pb(0);} REP(i,0,a.size()) {dp.pb(xx);}
    return LCS_dp<T>(a.size()-1,b.size()-1, dp, a, b);
}

template<class T=string>
ll L_dist_dp(ll i, ll j, vector<vector<ll> > &dp, T a, T b) //i means prefix s[0...(i+1)]
{
    if(i==0) {dp[i][j]=j;}
    else if(j==0) {dp[i][j]=i;}
    else 
    {
        ll c = 1; if(a[i-1]==b[j-1]) {c=0;}
        dp[i][j]=min(min(L_dist_dp(i-1,j,dp,a,b)+1,L_dist_dp(i,j-1,dp,a,b)+1),L_dist_dp(i-1,j-1,dp,a,b)+c);
    }
    return dp[i][j];
}

template<class T=string>
ll L_dist(T a, T b) //Levenshtein distance
{
    vector<ll> xx; vector<vector<ll> > dp; REP(i,0,b.size()+1) {xx.pb(0LL);} REP(i,0,a.size()+1) {dp.pb(xx);}
    return L_dist_dp(a.size(),b.size(),dp,a,b);
}

vector<ll> IC(ll k, vector<ll> a) //#strictly increasing subsequences of length k ending in each position
{
    ll N=a.size();
    unordered_map<ll,ll> m; set<ll> vals; REP(i,0,N) {vals.insert(a[i]);}
    ll cnt=0LL; set<ll>::iterator it=vals.begin();
    while(it!=vals.end()) {m[*it]=cnt; cnt++; it++;}
    REP(i,0,N) {a[i]=m[a[i]];}
    vector<ll> ans; REP(i,0,N) {ans.pb(0LL);}
    if(k>N) {return ans;}
    if(k==1) {REP(i,0,N) {ans[i]=1LL;} return ans;}
    vector<ll> last=IC(k-1,a);
    ST S(ans);
    REP(i,0,N)
    {
        ST::LV X(last[i]);
        S.update(X,a[i],a[i],1);
        ans[i]=S.query(0,a[i]-1LL,1).a;
    }
    return ans;
}

template<class T=string>
ll subcnt(T a, T b) //#subsequences of a that are equal to b (can be upgraded if occorrence of each value in b is restricted)
{
    ll N=a.size(); ll M=b.size();
    if(M>N) {return 0LL;}
    vector<ll> oc; REP(i,0,M) {oc.pb(0LL);}
    REP(i,0,N)
    {
        REP(j,0,M) 
        {
            if(a[i]==b[j]) 
            {
                if(j==0) {oc[0]++;}
                else {oc[j]+=oc[j-1];}
            }
        }
    }
    return oc[M-1];
}

vector<ModInt> PrefixHash(string s, ll B) //char a = 1, b = 2, ...
{
    ll oldmod=mod;
    mod=B;
    ModInt cur=0; ll val; ModInt x=1;
    vector<ModInt> ans;
    REP(i,0,s.size())
    {
        val=(ll) (s[i]-'a'); val++;
        cur+=(x*val);
        x*=26LL;
        ans.pb(cur);
    }
    mod=oldmod;
    return ans;
}

template<class T=string>
vector<ll> ZArr(T s)
{
    vector<ll> ans; REP(i,0,s.size()) {ans.pb(0);}
    ans[0]=s.size(); ll x=1,y=1;
    REP(i,1,s.size())
    {
        y=max(y,i);
        if(y==i)
        {
            ll ind=0; 
            while(i+ind<s.size() && s[ind]==s[i+ind]) {ind++;}
            ans[i]=ind;
            y=i+ind;
            x=i;
        }
        else if(i+ans[i-x]-1<=y-2)
        {
           ans[i]=ans[i-x];
        }
        else
        {
            ll ind=0;
            while(y+ind<s.size() && s[y+ind]==s[y+ind-i]) {ind++;}
            y=y+ind; x=i;
            ans[i]=y-i;
        }
    }
    return ans;
}

template<class T=string>
ll patt(T s, T p) //#substrings of s equal to p, O(N)
{
    if(p.size()>s.size()) {return 0;}
    T x=p; x+=' '; x+=s;
    vector<ll> a=ZArr(x);
    ll ans=0LL;
    REP(i,p.size()+1,a.size()) 
    {
        if(a[i]==p.size()) {ans++;}
    }
    return ans;
}

vector<ll> SuffixArr(string s)
{
    ll N = s.size();
    unordered_map<char,ll> m1; ll curi=1LL;
    set<char> used; REP(i,0,N) {used.insert(s[i]);}
    set<char>::iterator it=used.begin();
    while(it!=used.end())
    {
        m1[*it]=curi; curi++;
        it++;
    }
    vector<ll> l,nl; REP(i,0,N) {l.pb(m1[s[i]]);nl.pb(0);}
    ll si = 2LL;
    set<pl> old; pl cur;
    set<pl>::iterator ite;
    unordered_map<pl,ll,hash_pair> m;
    while(si<=N)
    {
        old.clear();
        m.clear();
        REP(i,0,N)
        {
            cur.ff=l[i]; if(i+si/2<N) {cur.ss=l[i+si/2];} else {cur.ss=0;}
            old.insert(cur);
        }
        ite=old.begin();
        curi=1LL;
        while(ite!=old.end())
        {
            m[*ite]=curi; curi++;
            ite++;
        }
        REP(i,0,N)
        {
            cur.ff=l[i]; if(i+si/2<N) {cur.ss=l[i+si/2];} else {cur.ss=0;}
            nl[i]=m[cur];
        }
        l=nl;
        si=2*si;
    }
    REP(i,0,N) {l[i]--;}
    vector<ll> ans; REP(i,0,N) {ans.pb(0);}
    REP(i,0,N) {ans[l[i]]=i;}
    return ans;
}

vector<ll> LCPArr(string s, vector<ll> SuffixArr)
{
    ll N = s.size();
    vector<ll> pos; vector<ll> LCP; REP(i,0,N) {pos.pb(0); LCP.pb(0);}
    REP(i,0,N) {pos[SuffixArr[i]]=i;}
    ll las = 0LL;
    REP(i,0,N)
    {
        ll s1 = i; ll s2;
        if(pos[i]+1<N) {s2 = SuffixArr[pos[i]+1];}
        else {LCP[pos[i]]=0; las=0; continue;}
        ll val=max(0LL,las-1LL);
        while(s1+val<N && s2+val<N && s[s1+val]==s[s2+val]) {val++;}
        LCP[pos[i]]=val;
        las=val;   
    }
    return LCP;
}

template<class T=ll>
T kSmall(vector<T> a, ll K) // K in [0,N-1], O(N)
{
    if(a.size()<=50LL) {sort(a.begin(),a.end(),cmp<T>); return a[K];} 
    srand(time(NULL)*time(NULL));
    ll x,y,z; x=rand()%a.size(); y=rand()%a.size(); z=rand()%a.size();
    vector<T> dummy; dummy.pb(a[x]); dummy.pb(a[y]); dummy.pb(a[z]); sort(whole(dummy),cmp<T>);
    T pivot=dummy[1LL]; 
    vector<ll> rel; REP(i,0,a.size()) {rel.pb(0LL);}
    ll sm=0LL; ll eq=0LL; ll bi=0LL;
    REP(i,0,a.size()) 
    {
        if(a[i]<pivot) {rel[i]=-1;sm++;}
        else if(a[i]>pivot) {rel[i]=1;bi++;}
        else {rel[i]=0;eq++;}
    }
    if(sm<=K && sm+eq>=K+1LL) {return pivot;}
    vector<T> nxt;
    if(sm>=K+1LL) {REP(i,0,a.size()) {if(rel[i]==-1) {nxt.pb(a[i]);}} return kSmall(nxt,K);}
    else {REP(i,0,a.size()) {if(rel[i]==1) {nxt.pb(a[i]);}} return kSmall(nxt,K-sm-eq);}
}

class LinRecursion //Linear Recursion
{
    public:
    ll K;
    vector<double> c; //a_N = c1*a_N-1 + ... + cK*a_N-K
    Matrix X; //Recursion Matrix
    Matrix V0; //Initial vector
    
    LinRecursion(vector<double> coef, vector<double> v0)
    {
        K=coef.size(); c=coef; vector<vector<double> > xxx; xxx.pb(v0); xxx.pb(v0); Matrix INSIG(xxx);
        V0=~INSIG; 
        xxx.clear(); v0.clear(); REP(i,0,K) {v0.pb(0.0);} REP(i,0,K) {xxx.pb(v0);}
        REP(i,0,K-1) {xxx[i][i+1]=1.0;}
        REP(i,0,K) {xxx[K-1][i]=c[K-i-1];}
        Matrix Y(xxx); X=Y;
    }
    
    double query(ll pos) //what's a_pos, pos from 0
    {
        return ((fastexp(X,pos)*V0).a[0][0]);   
    }
};

vector<bool> SAT2(ll N, vector<pl> a)
{
    ll M=a.size();
    vector<vector<ll> > adj; vector<ll> xx; REP(i,0,2*N) {adj.pb(xx);}
    pl c;
    REP(i,0,M) 
    {
        if(a[i].ff==-a[i].ss) {continue;}
        c.ff = -a[i].ff; c.ss=a[i].ss;
        if(c.ff<0) {c.ff=2*(-c.ff)-1;}
        else {c.ff=2*c.ff-2;}
        if(c.ss<0) {c.ss=2*(-c.ss)-1;}
        else {c.ss=2*c.ss-2;}
        adj[c.ff].pb(c.ss);
        swap(a[i].ff,a[i].ss);
        c.ff = -a[i].ff; c.ss=a[i].ss;
        if(c.ff<0) {c.ff=2*(-c.ff)-1;}
        else {c.ff=2*c.ff-2;}
        if(c.ss<0) {c.ss=2*(-c.ss)-1;}
        else {c.ss=2*c.ss-2;}
        adj[c.ff].pb(c.ss);
    }
    DiGraph G(adj); G.Kosaraju();
    vector<bool> ans; REP(i,0,N) {if(G.SCC[2*i]==G.SCC[2*i+1]) {return ans;}}
    REP(i,0,N)
    {
        if(G.SCC[2*i]>G.SCC[2*i+1]) {ans.pb(true);}
        else {ans.pb(false);}
    }
    return ans;
}

vector<vector<ll> > Sum_Set_Cover(vector<vector<ll> > p, ll MAX) //given vectors p0,...,pk-1, is it possible to get sum S in [0,MAX-1] by choosing exactly one element in each vector? ans[i][S] is -1 if S is not attainable in i steps (p0,...,pi), else it is e, meaning the chosen element in pi was pi[e]. pi[j] must be non-negative. Variation of Knapsack. O(MAX*max{pi.size()})
{
    vector<vector<ll> > ans; vector<ll> em; REP(i,0,MAX) {em.pb(-1);} REP(i,0,p.size()) {ans.pb(em);}
    REP(i,0,p.size())
    {
        if(i==0)
        {
            REP(j,0,p[0].size())
            {
                if(p[0][j]>=MAX) {continue;}
                ans[0][p[0][j]]=j;
            }
            continue;
        }
        REP(j,0,MAX)
        {
            if(ans[i-1][j]==-1) {continue;}
            REP(z,0,p[i].size()) 
            {
                if(j+p[i][z]>=MAX) {continue;}
                ans[i][j+p[i][z]]=z;
            }
        }
    }
    return ans;
}

bool cmpMo(pl a, pl b)
{
    pl p1,p2; 
    p1.ff=a.ff/Mo_bucket; p1.ss=a.ss; 
    p2.ff=b.ff/Mo_bucket; p2.ss=b.ss; 
    return (p1<p2);
}

class Sym //Symmetric sum
{
    public:
    ll N;
    vector<pair<ll,vector<ll> > > c; 
    
    Sym() {}
    Sym(ll n) {N=n;}
    Sym(vector<ll> coef) {N=coef.size(); c.pb(mp(1LL,coef));}
    vector<ll> perm; vector<vector<ll> > perms;
    
    void Perm(unordered_multiset<ll> left)
    {
        if(left.empty()) 
        {
            perms.pb(perm);
        }
        else
        {
            unordered_multiset<ll> copy = left;
            unordered_multiset<ll>::iterator it=left.begin();
            while(it!=left.end())
            {
                perm.pb(*it); copy.erase(copy.find(*it));
                Perm(copy); 
                perm.pop_back(); copy.insert(*it);
                it++;
            }
        }
    }
    
    Sym operator *(ll k) 
    {
        Sym ANS=(*this); 
        REP(i,0,ANS.c.size()) {ANS.c[i].ff*=k;}
        ANS.zip();
        return ANS;
    }
    
    Sym operator + (Sym X)
    {
        Sym ANS = (*this);
        REP(i,0,X.c.size()) {ANS.c.pb(X.c[i]);}
        ANS.zip();
        return ANS;
    }
    
    Sym operator * (Sym X)
    {
        Sym ANS(N); 
        REP(a,0,c.size())
        {
            unordered_multiset<ll> s;
            REP(i,0,N) {s.insert(c[a].ss[i]);}
            Perm(s);
            REP(b,0,X.c.size())
            {
                REP(i,0,perms.size()) 
                {
                    vector<ll> cur; REP(z,0,N) {cur.pb(perms[i][z]+X.c[b].ss[z]);}
                    ANS.c.pb(mp(c[a].ff*X.c[b].ff,cur));
                }
            }
            perms.clear();
        }
        ANS.zip();
        return ANS;
    }
    
    void zip()
    {
        REP(i,0,c.size()) {sort(whole(c[i].ss)); reverse(whole(c[i].ss));}
        set<pair<vector<ll>,ll> > s; set<pair<vector<ll>,ll> >::iterator it; 
        REP(i,0,c.size()) 
        {
            it=s.lower_bound(mp(c[i].ss,-INF));
            if(it==s.end()) {s.insert(mp(c[i].ss,c[i].ff));}
            else if(it->ff==c[i].ss) {pair<vector<ll>,ll> p; p.ff=it->ff; p.ss=it->ss+c[i].ff; s.erase(it); s.insert(p);}
            else {s.insert(mp(c[i].ss,c[i].ff));}
        }
        c.clear();
        it=s.begin(); 
        while(it!=s.end())
        {
            c.pb(mp(it->ss,it->ff));
            it++;
        }
        reverse(whole(c));
    }
    
    void disp()
    {
        zip();
        REP(i,0,c.size()) {cout<<c[i].ff<<" * ( "; REP(j,0,c[i].ss.size()) {cout<<c[i].ss[j]<<" ";} cout<<")"<<endl;}
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    return 0;
}