#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define ull unsigned long long

#define all(x) x.begin(), x.end()

#define mem(x, y) memset(x, y, sizeof(x))

#define what_is(x) cerr <<  "Line " << __LINE__ << ": " << #x << " is " << (x) << endl;

#define suf_zero(x) __builtin_ffs(x)

#define pre_zero(x) __builtin_clz(x)

#define num_one(x) __builtin_popcount(x)

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

#define lson l, mid, rt<<1

#define rson mid+1, r, rt<<1|1

void err(istream_iterator<string> it) {cerr<<endl;}

template<typename T, typename... Args>

void err(istream_iterator<string> it, T a, Args... args) {

    cerr << *it << " = " << a << " , ";

    err(++it, args...);

}

// fast IO

namespace fastIO{

    #define BUF_SIZE 100000

//     fread -> read

    bool IOerror = ;

    inline char nc(){

        static char buf[BUF_SIZE], *p1 = buf+BUF_SIZE,

         *pend = buf+BUF_SIZE;

         if(p1==pend){

             p1 = buf;

             pend = buf+fread(buf, , BUF_SIZE, stdin);

             if(pend==p1){

                 IOerror = ;

                 return -;

             }

         }

         return *p1++;

    }

    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}

    inline void read(int &x){

        char ch;

        while(blank(ch=nc()));

        if(IOerror)return ;

        for(x=ch-'';(ch=nc())>=''&&ch<='';x=x*+ch-'');

    }

    #undef BUF_SIZE

}

using namespace fastIO;

//#include<ext/pb_ds/assoc_container.hpp>

//#include<ext/pb_ds/hash_policy.hpp>

//using namespace __gnu_pbds;

//ll sum_of_sq(ll n){n%=mod;return n*(n+1)%mod*(2*n+1)%mod*inv6%mod;}

const double PI = acos(-1.0);

const double eps = 1e-;

const ll mod = 1e9+;

ll qp(ll b, ll n){ll r=;if(n<)n+=mod-;b%=mod;for(;n;n>>=,b=b*b%mod)if(n&)r=r*b%mod;return r;}

//cc_hash_table<ll, ll> S;