namespace Octane { #define OCTANE #define BUFFER_SIZE 100000 #define ll long long #define db double #define ldb long double char ibuf[BUFFER_SIZE], obuf[BUFFER_SIZE]; char *p1 = ibuf, *p2 = ibuf, *p3 = obuf; #ifdef ONLINE_JUDGE #define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,BUFFER_SIZE,stdin),p1==p2)?(EOF):(*p1++)) #define putchar(x) ((p3==obuf+BUFFER_SIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x) #endif
#define isdigit(ch) (ch>47&&ch<58) #define isspace(ch) (ch<=32&&ch!=EOF) #define isseen(ch) (ch>32) const ll pow10[] = { (ll)1e0, (ll)1e1, (ll)1e2, (ll)1e3, (ll)1e4, (ll)1e5, (ll)1e6, (ll)1e7, (ll)1e8, (ll)1e9, (ll)1e10, (ll)1e11, (ll)1e12, (ll)1e13, (ll)1e14, (ll)1e15, (ll)1e16, (ll)1e17, (ll)1e18, }; 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(); if(ch == '.') { ll flt = 0; int cnt = 0; while(ch=getchar(), isdigit(ch)) if(cnt < 18) flt=flt*10+ch-48, cnt++; s += (db)flt/pow10[cnt]; } 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(); if(ch == '.') { ll flt = 0; int cnt = 0; while(ch=getchar(), isdigit(ch)) if(cnt < 18) flt=flt*10+ch-48, cnt++; s += (db)flt/pow10[cnt]; } return s *= w, true; } inline bool read(char &s) { while(s = getchar(), isspace(s)); return s != EOF; } inline bool read(char *s) { char ch; while(ch=getchar(), isspace(ch)); if(ch == EOF) return false; while(isseen(ch)) *s++ = ch, ch=getchar(); *s = '\000'; return true; } template<typename T> void print(T x) { static int t[20]; int top = 0; if(x < 0) putchar('-'), x = -x; do { t[++top] = x%10; x /= 10; } while(x); while(top) putchar(t[top--]+48); } struct empty_type{}; int pcs = 8; empty_type setpcs(int cnt) { return pcs = cnt, empty_type(); } inline void print(empty_type x){} inline void print(double x) { if(x < 0) putchar('-'), x = -x; x += 5.0 / pow10[pcs+1]; print((ll)(x)); x -= (ll)(x); if(pcs != 0) putchar('.'); for(int i = 1; i <= pcs; i++) x *= 10, putchar((int)x+'0'), x -= (int)x; } inline void print(float x) { if(x < 0) putchar('-'), x = -x; x += 5.0 / pow10[pcs+1]; print((ll)(x)); x -= (ll)(x); if(pcs != 0) putchar('.'); for(int i = 1; i <= pcs; i++) x *= 10, putchar((int)x+'0'), x -= (int)x; } inline void print(char x) { putchar(x); } inline void print(char *x) { for(int i = 0; x[i]; i++) putchar(x[i]); } inline void print(const char *x) { for(int i = 0; x[i]; i++) putchar(x[i]); } #ifdef _GLIBCXX_STRING 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 void print(std::string x) { for(string::iterator i = x.begin(); i != x.end(); i++) putchar(*i); } inline bool getline(Octane_t &io, string s) { s = ""; char ch = getchar(); if(ch == EOF) return false; while(ch != '\n' and ch != EOF) s += ch, ch = getchar(); return true; } #endif #if __cplusplus >= 201103L template<typename T, typename... T1> inline int read(T& a, T1& ...other) { return read(a)+read(other...); } template<typename T, typename... T1> inline void print(T a, T1... other) { print(a); print(other...); } #endif 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 print(b), io; }
#define cout io #define cin io #define endl '\n' #undef ll #undef db #undef ldb } using namespace Octane;
|