namespace Octane {
    //non terrae plus ultra dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
    #define OCTANE // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
    #define BUFFER_SIZE 100000 // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
    #define ll long long // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
    #define db double // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
    #define ldb long double // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
    char ibuf[100000], obuf[100000], *p1=ibuf,*p2=ibuf,*p3=obuf;
    #ifdef ONLINE_JUDGE//dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
    #define getchar() ((p1==p2) and (p2=(p1=ibuf)+fread(ibuf,1,\
    BUFFER_SIZE,stdin),p1==p2)?(EOF):(*p1++)) // dqrdqrdqrdqrdqr
    #define putchar(x) ((p3==obuf+BUFFER_SIZE) && (fwrite(obuf,\
    p3-obuf,1,stdout),p3=obuf),*p3++=x) // dqrdqrdqrdqrdqrdqrdqr
    #endif// fread in OJ, getchar in local dqrdqrdqrdqrdqrdqrdqr
    #define isdigit(ch) (ch>47&&ch<58)//dqrdqrdqrdqrdqrdqrdqrdqr
    #define isspace(ch) (ch<=32&&ch!=EOF)//dqrdqrdqrdqrdqrdqrdqr
    #define isseen(ch) (ch>32) // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
    struct Octane_t{~Octane_t(){fwrite(obuf,p3-obuf, 1, stdout);
    }bool flag=false;operator bool(){return flag;} }io; template
    <typename T>inline T read(){T s=0; int w = 1; char ch; while
    (ch=getchar(), !isdigit(ch)&&(ch!=EOF))if(ch == '-') w = -1;
    if(ch == EOF) return 0; while(isdigit(ch)) s = s*10+ch-48,ch
    =getchar(); return s *= w; } template<typename T>inline bool
    read(T &s) { s = 0; int w = 1; char ch; while(ch = getchar()
    ,!isdigit(ch)&&(ch!=EOF))if(ch == '-') w = -1; if(ch == EOF)
    return false;while(isdigit(ch))s = s*10+ch-48, ch=getchar();
    return s*=w,true;}inline bool read(char &s){while(s= getchar
    (), isspace(s)); return s != EOF; } inline bool read(char *s
    ){char ch=getchar();while(isspace(ch))ch= getchar();if(ch ==
    EOF)return false;while(isseen(ch)) *s++ = ch, ch= getchar();
    *s='\000';return true;}template<typename T> void printv(T a)
    {if(a== 0){ putchar('0'); return void(); }static char st[65]
    ; int top = 0; if (a < 0) putchar ('-'), a = - a; while(a)st
    [++top]='0'+a%10,a/=10;while(top)putchar(st[top--]);} inline
    void printv(char c){putchar(c);}inline void printv(char *s){
    for(int i=0;s[i];i++)putchar(s[i]);}inline void printv(const
    char *s){ for(int i=0;s[i];i++) putchar(s[i]); } inline void
    printv(bool a){ if(a != 0)putchar('1'); else putchar('0'); }
    #ifdef _GLIBCXX_STRING // support for string dqrdqrdqrdqrdqr
    inline bool read(std::string& s) { s = ""; char ch; while(ch
    =getchar(), isspace(ch)); if(ch == EOF) return false; while(
    !isspace(ch)) s+=ch,ch=getchar(); return true; } inline bool
    getline(Octane_t &io,std::string s){s="";char ch= getchar();
    if(ch==EOF)return false;while(ch!='\n' and ch !=EOF)s+=ch,ch
    =getchar();return true;}inline void printv(const std::string
    &a){for(auto i = a.begin(); i != a.end(); ++i) putchar(*i);}
    #endif// dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
    template<typename T>inline void print(const char *p,T first)
    { int n = strlen(p) - 1; for(int i = 0; i <= n; i++) { if(p[
    i] == '`') { putchar(p[++ i]); continue; } else if ( p[i] ==
    '{'){printv(first); i++; continue; } else putchar(p[i]); } }
    #if __cplusplus >= 201103L // support for many values dqrdqr
    template<typename T,typename... T1>inline int read(T& a, T1&
    ...other){return read(a)+read(other...); } inline void print
    (const char *p) { printv(p); }template<typename T1, typename
    ... T2>void print(const char*p, T1 first, T2 ...other) { int
    n=strlen(p)-1; for(int i = 0; i <= n; i++) { if(p[i] == '`')
    {putchar(p[++i]);continue;}else if(p[i]=='{'){printv(first);
    print(p+i+2,other...);return void();}else putchar(p[i]); } }
    #endif // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdq
    template <typename T> Octane_t& operator >> (Octane_t &io, T
    &b){return io.flag=read(b),io;}Octane_t& operator>>(Octane_t
    &io, char *b){return io.flag=read(b), io;} template<typename
    T>Octane_t&operator<<(Octane_t&io,T b){return printv(b),io;}
    #define cout io// dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
    #define cin io // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
    #define endl '\n' // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
    #undef ll// dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
    #undef db// dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
    #undef ldb//dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
} using namespace Octane;