Template

#include<bits/stdc++.h>

using namespace std;

///Template
#define in1()    freopen("C:\\Users\\SHESHER\\Rest\\Desktop\\MY COMPUTER\\Code\\Template\\New\\input.txt", "r", stdin);
#define out1()   freopen("C:\\Users\\SHESHER\\Rest\\Desktop\\MY COMPUTER\\Code\\Template\\New\\output.txt", "w", stdout);


//Data types
#define lo      long
#define ll      long long
#define llu     unsigned long long

//loop
#define f1(i,x,y)   for(int i=x;i<=y;i++)

//Constants
#define MAX     100007
#define MOD     1000000007
#define PI      acos(-1.0)

//STL
#define vout(v)    for(int i=0;i<v.size();i++){cout<<v[i]; if(i==v.size()-1) cout<<endl; else cout<<" ";}

//Scan
#define sc(x)    scanf("%d", &x)
#define scl(x)   scanf("%lld", &x)

//Print
#define pa(a,i,n)  for(int i=0;i<n;i++){ cout<<a[i]; if(i==n-1) cout<<endl; else cout<<" ";}


//Runtime
// clock_t tStart = clock();
// printf("\n>>Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);


///Prime Check
bool primeChk(int n)
{
    if(n==0 || n==1) return 0;
    else if(n==2) return 1;
    else if(n%2==0) return 0;

    for(int i=3;i*i<=n;i+=2){
        if(n%i==0) return 0;
    }
    return 1;
}


///Sieve
bool primeFlag[MAX];
int seve[MAX+2];
int sidx=0;
void sieve(int n)
{
    primeFlag[0]=1;
    primeFlag[1]=1;

    for(int i=4;i<=n;i+=2){
        primeFlag[i]=1;
    }

    int lim=sqrt(n+1);
    for(int i=3;i<=lim;i+=2){
        if(!primeFlag[i]){
            for(int j=i*i;j<=n;j+=2*i){
                primeFlag[j]=1;
            }
        }
    }

    for(int i=0;i<=n;i++){
        if(!primeFlag[i]) seve[sidx++]=i;
    }
}

///Binary Search
int bs(int a[], int key, int l, int r)
{
    int mid=(l+r)/2;

    if(l>r) return -1;
    if(a[mid]==key) return mid;
    else if(a[mid]>key) return bs(a, key, l, mid);
    else return bs(a, key, mid, r);
}


int perc=0;
bool perFalg[MAX];
vector<int> v;
void per(int pos, int n)
{
    if(pos==n){
        vout(v);
        perc++;
        return;
    }

    // if(perc==10) return;

    for(int i=0;i<n;i++){
        if(!perFalg[i]){
            perFalg[i]=1;
            v.push_back(i);
            per(pos+1,n);
            perFalg[i]=0;
            v.pop_back();
        }
    }
}

void comb(int a[],int pos, int n)
{
    if(pos==n){
        vout(v);
        return;
    }

    v.push_back(a[pos]);
    comb(a, pos+1, n);
    v.pop_back();
    comb(a, pos+1, n);
}

llu factorial[22];
void fact(int n)
{
    factorial[0]=1;
    factorial[1]=1;
    for(int i=2;i<=n;i++){
        factorial[i]=factorial[i-1]*i;
    }
}

int n;
int ba[11111];
int lTemp=-1;
int lmBS(int key)
{
    int l=0, r=n-1, mid=0;

    while(l<r){
        mid=(l+r)/2;
        //cout<<mid<<" "<<ba[mid]<<endl;
        if(ba[mid]>key) r=mid-1;
        else if(ba[mid]<key) l=mid+1;
        else if(ba[mid]==key){ lTemp=mid; r=mid-1; }
    }

    return lTemp;
}

//int n;
//int ba[11111];
int rTemp=-1;
int rmBS(int key)
{
    int l=0, r=n-1, mid=0;

    while(l<r){
        mid=(l+r)/2;
        //cout<<mid<<" "<<ba[mid]<<endl;
        if(ba[mid]>key) r=mid-1;
        else if(ba[mid]<key) l=mid+1;
        else if(ba[mid]==key){ rTemp=mid; l=mid+1; }
    }

    return rTemp;
}

int sa[11][11];

void TwoDSort()
{
    for(int j=0;j<10;j++){
        for(int i=0;i<5;i++){
            for(int k=i+1;k<5;k++){
                if(sa[i][j]<sa[k][j]){
                    swap(sa[i],sa[k]);
                }
            }
        }
        if(sa[0][j]!=sa[1][j]) break;
    }
}

vector<int> ff[111];
void firstFit(int w[], int n, int k)
{
    int sum=0;
    for(int i=0;i<n;i++) sum+=w[i];

    int bin=sum/k;
    if(sum%k!=0) bin++;

    //cout<<bin<<endl;

    int csum[111];
    for(int i=0;i<bin;i++) csum[i]=k;

    for(int i=0;i<n;i++){
        for(int j=0;j<bin;j++){
            if(csum[j]>=w[i]){
                ff[j].push_back(w[i]);
                csum[j]-=w[i];
                break;
            }
        }
    }

    for(int i=0;i<bin;i++){
        for(int j=0;j<ff[i].size();j++){
            cout<<ff[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

vector<int>ffni[111];
void firstFitNI(int w[], int n, int k)
{
    int a[1111];
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=w[i];
        a[i]=w[i];
    }

    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(a[i]<a[j]) swap(a[i],a[j]);
        }
    }

    int bin=sum/k;
    if(sum%k!=0) bin++;

    int csum[111];
    for(int i=0;i<bin;i++) csum[i]=k;

    for(int i=0;i<n;i++){
        for(int j=0;j<bin;j++){
            if(csum[j]>=a[i]){
                ffni[j].push_back(a[i]);
                csum[j]-=a[i];
                break;
            }
        }
    }

    for(int i=0;i<bin;i++){
        for(int j=0;j<ffni[i].size();j++){
            cout<<ffni[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

vector<int>bf[1111];
void bestFit(int w[], int n, int k)
{
    int sum=0;
    for(int i=0;i<n;i++) sum+=w[i];

    int bin=sum/k;
    if(sum%k!=0) bin++;

    int csum[1111];
    for(int i=0;i<bin;i++) csum[i]=k;

    int mn=k;
    int temp;
    int idx;
    for(int i=0;i<n;i++){
        mn=k;
        for(int j=0;j<bin;j++){
            if(csum[j]>=w[i]){
                temp=csum[j]-w[i];
                if(temp<mn){
                    mn=temp;
                    idx=j;
                }
            }
        }
        bf[idx].push_back(w[i]);
        csum[idx]-=w[i];
    }

    for(int i=0;i<bin;i++){
        for(int j=0;j<bf[i].size();j++){
            cout<<bf[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

///bitwise sieve
bool check(int n, int pos)
{
    return (bool)(n & (1<<pos));
}
int Set(int n, int pos)
{
    return n=n | (1<<pos);
}
int status[111111111/32];
// vector<int> bitv;
int ccc=0;
void bitSieve(int n)
{
    int sq=sqrt(n);
    for(int i=3;i<=n+1;i+=2){
        if(check(status[i/32],i%32)==0){
            for(int j=i*i;j<=n;j+=2*i){
                status[j/32]=Set(status[j/32],j%32);
            }
        }
    }
    // bitv.push_back(2);
    for(int i=3;i<=n;i+=2){
        if( check(status[i/32],i%32)==0){
            // bitv.push_back(i);
            ccc++;
        }
    }

    cout<<ccc<<endl;
}


//Number of co-prime of n (euler's totient functio)
int NOCP(int n)
{
    double rv=n*1.0;
    for(int i=2;i<=sqrt(n)+1;i++){
        if(n%i==0){
            rv*=(1-(1/(i*1.0)));
            while(n%i==0) n/=i;
        }
    }

    if(n>1) rv*=(1-(1/(n*1.0)));

    return (int)rv;
}

//Number Of Divisors
int NOD(int n)
{
    int rv=1;
    int cunt;
    for(int i=2;i<=sqrt(n)+1;i++){
        if(n%i==0){
            cunt=0;
            while(n%i==0){
                n/=i;
                cunt++;
            }
            rv*=(cunt+1);
        }
    }
    if(n>1) rv*=2;

    return rv;
}

//Big mod
ll bigmod(ll base, ll pw, ll mod)
{
    if(pw==0) return 1%mod;

    ll x=bigmod(base,pw/2,mod); //dividing the job into two parts(2^5=2^2&2^2)

    x=(x*x)%mod; //combining the divided parts

    if(pw%2!=0) x=(x*base)%mod; // if(powe if odd left part is being multiplied)

    return x;
}

//Number add using string
string digadd(string s1, string s2)
{
    reverse(s1.begin(),s1.end());
    reverse(s2.begin(),s2.end());

    // cout<<s1<<" "<<s2<<endl;

    if(s1.size()<s2.size()) swap(s1,s2);

    // cout<<s1<<" "<<s2<<endl;

    string s3;

    bool carry=0;
    int x, y;
    for(int ii=0;ii<s1.size();ii++){
        x=s1[ii]-'0';
        if(ii<s2.size()) y=s2[ii]-'0';
        else y=0;
        x=x+y+carry;
        if(x<10){
            s3+=(x+'0');
            carry=0;
        }
        else{
            s3+=((x%10)+'0');
            carry=1;
        }
    }
    if(carry==1) s3+='1';

    reverse(s3.begin(),s3.end());
    return s3;
}

//Number multiply using string
string digmul(string x, string y)
{
    reverse(x.begin(),x.end());
    reverse(y.begin(),y.end());

    string s="0";
    string temp;

    // int cunt=0;
    int carry=0;
    for(int i=0;i<y.size();i++){
        temp.clear();
        carry=0;
        for(int j=0;j<x.size();j++){
            int xx=x[j]-'0';
            int yy=y[i]-'0';
            int z=xx*yy;
            z+=carry;
            int md=z%10;
            temp+=(md+'0');
            carry=z/10;
        }

        while(1){
            if(carry==0) break;

            temp+=((carry%10)+'0');
            carry/=10;
        }

        reverse(temp.begin(),temp.end());
        for(int ii=0;ii<i;ii++){
            temp+='0';
        }
        // cout<<temp<<endl;
        s=digadd(s,temp);
    }

    return s;
}


// Number divide using string
// result stored in a vector
string digdiv(string s1, string s2)
{
    vector<int>v;
    int y=0;
    for(int i=0;i<s2.size();i++){
        y=(y*10)+(s2[i]-'0');
    }

    int x=0;
    for(int i=0;i<s1.size();i++){
        x=(x*10)+(s1[i]-'0');
        if(x>=y){
            v.push_back(x/y);
            x=x%y;
        }
        else{
            v.push_back(0);
        }
    }

    string s3;
    bool f=0;
    for(int i=0;i<v.size();i++){
        if(v[i]==0){
            if(f) s3+=(v[i]+'0');
        }
        else{
            f=1;
            s3+=(v[i]+'0');
        }
    }

    return s3;
}


//Factorial with modulus
ll mFact[11111111];
void modFact(ll modval)
{
    mFact[0]=1;
    for(int i=1;i<=10000000;i++){
        mFact[i]=(((mFact[i-1]%modval)*(i%modval))%modval);
    }
}

//Inverse Mod
ll invmod(ll y, ll x, ll modval)
{
    ll down=bigmod(x,modval-2,modval);

    return ((y%modval)*(down%modval))%modval;
}

ll nCr(ll n, ll r, ll modval)
{
    // cout<<n<<" "<<mFact[n]<<endl;
    // cout<<r<<" "<<mFact[r]<<endl;
    // cout<<n-r<<" "<<mFact[n-r]<<endl;
    ll rv=((mFact[n]%modval)*((bigmod(mFact[r],modval-2,modval))%modval)*((bigmod(mFact[n-r],modval-2,modval)%modval)))%modval;

    return rv;
}

ll nCr2(ll n, ll r, ll modval) //its working
{
    ll rv=1;
    ll x=r, y=n-r;
    ll total=1;
    if(x<y) swap(x,y);
    ll temp=1;
    for(ll i=n;i>x;i--){
        total=((total%modval)*(i%modval))%modval;
        if(temp<=y){
            total=invmod(total,temp,MOD);
            temp++;
        }
    }

    return total;
}

//Fibonacci in log n  time
ll fibn[111111];
int fib(int n)
{
    if(n==0) return 0;
    if(n==1 || n==2) return (fibn[n]=1);
    if(fibn[n]!=-1) return fibn[n];

    int k;
    if(n%2==0){
        k=n/2;
        fibn[n]= (2*fib(k-1)+fib(k))*fib(k);
    }
    else{
        k=(n+1)/2;
        fibn[n]= fib(k)*fib(k)+fib(k-1)*fib(k-1);
    }

    return fibn[n];
}