求注释&格式化
namespace Fast_I {
char *_Buf, *_Start_ptr, *_End_ptr;
std::streambuf* inbuf;
unsigned int Size;
bool _Ok;
struct Fast_Istream {
operator bool() { return _Ok; }
Fast_Istream(std::streambuf*, unsigned int);
Fast_Istream(unsigned int);
Fast_Istream(const char*, unsigned int);
Fast_Istream& operator>>(char&);
Fast_Istream& operator>>(char*);
Fast_Istream& operator>>(bool&);
Fast_Istream& operator>>(short&);
Fast_Istream& operator>>(int&);
Fast_Istream& operator>>(long&);
Fast_Istream& operator>>(long long&);
Fast_Istream& operator>>(unsigned short&);
Fast_Istream& operator>>(unsigned int&);
Fast_Istream& operator>>(unsigned long&);
Fast_Istream& operator>>(unsigned long long&);
Fast_Istream& operator>>(float&);
Fast_Istream& operator>>(double&);
Fast_Istream& operator>>(long double&);
Fast_Istream& operator>>(std::string&);
template <typename Typex>
void operator()(Typex& _Val) { *this >> _Val; }
template <typename Typex, typename... More>
void operator()(Typex&, More&...);
std::streambuf* rdbuf() { return inbuf; }
void rdbuf(std::streambuf* _inbuf) { inbuf = _inbuf; }
void rdbuf(const char*);
void pop();
char peek();
};
} // namespace Fast_I
namespace Fast_O {
std::string buf;
std::streambuf* outbuf;
struct Fast_Ostream {
Fast_Ostream(std::streambuf*, unsigned int);
Fast_Ostream(std::streambuf* out) { outbuf = out; }
Fast_Ostream(const char*, unsigned int);
Fast_Ostream(unsigned int);
void flush();
~Fast_Ostream();
void endl() { buf.push_back('\n'); }
template <typename Typex>
void endl(const Typex& _Val);
template <typename Typex, typename... More>
void endl(const Typex&, const More&...);
template <typename Typex>
void operator()(const Typex& _Val);
template <typename Typex, typename... More>
void operator()(const Typex&, const More&...);
Fast_Ostream& operator<<(char);
Fast_Ostream& operator<<(const char*);
Fast_Ostream& operator<<(const std::string&);
Fast_Ostream& operator<<(bool);
Fast_Ostream& operator<<(short);
Fast_Ostream& operator<<(int);
Fast_Ostream& operator<<(long);
Fast_Ostream& operator<<(long long);
Fast_Ostream& operator<<(unsigned short);
Fast_Ostream& operator<<(unsigned int);
Fast_Ostream& operator<<(unsigned long);
Fast_Ostream& operator<<(unsigned long long);
std::streambuf* rdbuf() { return outbuf; }
void rdbuf(std::streambuf* _outbuf) { outbuf = _outbuf; }
void rdbuf(const char*);
};
} // namespace Fast_O
namespace Fast_IO {
Fast_I::Fast_Istream fin(std::cin.rdbuf(), 1048576); // 1 MB
Fast_O::Fast_Ostream fout(std::cout.rdbuf()); // ∞
} // namespace Fast_IO
#define cin Fast_IO::fin
#define cout Fast_IO::fout
/* ------------------------------------- */
/* ------------------------------------- */
namespace Fast_I {
Fast_Istream::Fast_Istream(std::streambuf* in, unsigned int Sz) {
_Ok = 1;
Fast_I::Size = Sz;
inbuf = in;
_Start_ptr = _End_ptr = _Buf = new char[Sz];
}
Fast_Istream::Fast_Istream(const char* in, unsigned int Sz) {
_Ok = 1;
Fast_I::Size = Sz;
rdbuf(in);
_Start_ptr = _End_ptr = _Buf = new char[Sz];
}
Fast_Istream::Fast_Istream(unsigned int Sz) {
_Ok = 1;
Fast_I::Size = Sz;
_Start_ptr = _End_ptr = _Buf = new char[Sz];
}
void Fast_Istream::rdbuf(const char* File) {
static std::ifstream __In__(File);
rdbuf(__In__.rdbuf());
}
void Get_Char(char& _Val) {
if (_Start_ptr == _End_ptr) {
_Start_ptr = _Buf;
_End_ptr = _Buf + inbuf->sgetn(_Buf, Size);
}
if (_Start_ptr == _End_ptr) {
_Val = -1;
_Ok = 0;
} else {
_Val = *_Start_ptr++;
}
}
Fast_Istream& Fast_Istream::operator>>(char& _Val) {
if (_Ok) {
Get_Char(_Val);
while (_Val == 32 || _Val == 10 || _Val == 13 || _Val == 8 || _Val == 9 ||
_Val == 7 || _Val == 12 || _Val == 11) {
Get_Char(_Val);
}
}
return *this;
}
Fast_Istream& Fast_Istream::operator>>(char* _Val) {
if (_Ok) {
Get_Char(*_Val);
while (*_Val == 32 || *_Val == 10 || *_Val == 13 || *_Val == 8 ||
*_Val == 9 || *_Val == 7 || *_Val == 12 || *_Val == 11) {
Get_Char(*_Val);
}
while (*_Val != 32 && *_Val != 10 && *_Val && *_Val != -1 && *_Val != 9 &&
*_Val != 11 && *_Val != 12) {
Get_Char(*++_Val);
}
*_Val = 0;
--_Start_ptr;
}
return *this;
}
Fast_Istream& Fast_Istream::operator>>(std::string& _Val) {
if (_Ok) {
char c;
Get_Char(c);
while (c == 32 || c == 10 || c == 13 || c == 8 || c == 9 || c == 7 ||
c == 12 || c == 11) {
Get_Char(c);
}
for (_Val.clear();
c != 32 && c != 10 && c && c != -1 && c != 9 && c != 11 && c != 12;
Get_Char(c)) {
_Val.push_back(c);
}
--_Start_ptr;
}
return *this;
}
template <typename Typex>
void Get_Int(Typex& _Val) {
if (_Ok) {
char ch;
bool _F = 0;
for (Get_Char(ch); (ch < 48 || ch > 57) && ch != -1; Get_Char(ch)) {
_F = ch == 45;
}
for (_Val = 0; ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {
_Val = _Val * 10 + (ch ^ 48);
}
if (_F) {
_Val = ~_Val + 1;
}
--_Start_ptr;
}
}
template <typename Typex>
void Get_Unsigned(Typex& _Val) {
if (_Ok) {
char ch;
Get_Char(ch);
while ((ch < 48 || ch > 57) && ch != -1) {
Get_Char(ch);
}
for (_Val = 0; ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {
_Val = _Val * 10 + (ch ^ 48);
}
--_Start_ptr;
}
}
template <typename Typex>
void Get_Double(Typex& _Val) {
if (_Ok) {
char ch;
bool _F = 0;
for (Get_Char(ch); (ch < 48 || ch > 57) && ch != -1; Get_Char(ch)) {
_F = ch == 45;
}
for (_Val = 0; ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {
_Val = _Val * 10 + (ch ^ 48);
}
if (ch == 46) {
unsigned long long _Pow = 1;
for (Get_Char(ch); ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {
_Val += Typex((ch ^ 48) * 1.0 / (_Pow *= 10));
}
}
if (_F) {
_Val = -_Val;
}
--_Start_ptr;
}
}
Fast_Istream& Fast_Istream::operator>>(bool& _Val) {
if (_Ok) {
char ch;
Get_Char(ch);
while (ch == 32 || ch == 10 || ch == 13 || ch == 8 || ch == 9 || ch == 7 ||
ch == 12 || ch == 11) {
Get_Char(ch);
}
while (ch != 32 && ch != 10 && ch && ch != -1 && ch != 9 && ch != 11 &&
ch != 12) {
_Val |= ch != 48;
Get_Char(ch);
}
--_Start_ptr;
}
return *this;
}
Fast_Istream& Fast_Istream::operator>>(short& _Val) {
Get_Int(_Val);
return *this;
}
Fast_Istream& Fast_Istream::operator>>(int& _Val) {
Get_Int(_Val);
return *this;
}
Fast_Istream& Fast_Istream::operator>>(long& _Val) {
Get_Int(_Val);
return *this;
}
Fast_Istream& Fast_Istream::operator>>(long long& _Val) {
Get_Int(_Val);
return *this;
}
Fast_Istream& Fast_Istream::operator>>(unsigned short& _Val) {
Get_Unsigned(_Val);
return *this;
}
Fast_Istream& Fast_Istream::operator>>(unsigned int& _Val) {
Get_Unsigned(_Val);
return *this;
}
Fast_Istream& Fast_Istream::operator>>(unsigned long& _Val) {
Get_Unsigned(_Val);
return *this;
}
Fast_Istream& Fast_Istream::operator>>(unsigned long long& _Val) {
Get_Unsigned(_Val);
return *this;
}
Fast_Istream& Fast_Istream::operator>>(float& _Val) {
Get_Double(_Val);
return *this;
}
Fast_Istream& Fast_Istream::operator>>(double& _Val) {
Get_Double(_Val);
return *this;
}
Fast_Istream& Fast_Istream::operator>>(long double& _Val) {
Get_Double(_Val);
return *this;
}
template <typename Typex, typename... More>
void Fast_Istream::operator()(Typex& _Val, More&... _More) {
*this >> _Val;
operator()(_More...);
}
void Fast_Istream::pop() {
char ch;
Get_Char(ch);
}
char Fast_Istream::peek() {
if (_Start_ptr == _End_ptr) {
_Start_ptr = _Buf;
_End_ptr = _Buf + inbuf->sgetn(_Buf, Size);
}
if (_Start_ptr == _End_ptr) {
_Ok = 0;
return -1;
} else {
return *_Start_ptr;
}
}
} // namespace Fast_I
namespace Fast_O {
Fast_Ostream::Fast_Ostream(std::streambuf* out, unsigned int Size) {
buf.reserve(Size);
outbuf = out;
}
Fast_Ostream::Fast_Ostream(const char* File, unsigned int Size) {
buf.reserve(Size);
rdbuf(File);
}
void Fast_Ostream::rdbuf(const char* File) {
static std::ofstream __Out__(File);
rdbuf(__Out__.rdbuf());
}
Fast_Ostream::Fast_Ostream(unsigned int Size) {
buf.reserve(Size);
}
void Fast_Ostream::flush() {
outbuf->sputn(buf.data(), buf.size());
buf.clear();
}
Fast_Ostream::~Fast_Ostream() {
flush();
}
Fast_Ostream& Fast_Ostream::operator<<(char _Val) {
buf.push_back(_Val);
return *this;
}
Fast_Ostream& Fast_Ostream::operator<<(const char* _Val) {
while (*_Val) {
buf.push_back(*_Val++);
}
return *this;
}
Fast_Ostream& Fast_Ostream::operator<<(const std::string& _Val) {
for (auto&& i : _Val) {
buf.push_back(i);
}
return *this;
}
template <typename Typex>
void Put_Unsigned(Typex _Val) {
char* _Stack = (char*)malloc(sizeof(Typex) * 3);
unsigned S_top = 0;
while (_Val) {
_Stack[++S_top] = (_Val % 10) ^ 48;
_Val /= 10;
}
if (!S_top) {
buf.push_back('0');
}
while (S_top) {
buf.push_back(_Stack[S_top--]);
}
free(_Stack);
}
void Put_Int(long long _Val) {
if (_Val < 0) {
buf.push_back('-');
Put_Unsigned(~_Val + 1);
} else {
Put_Unsigned(_Val);
}
}
Fast_Ostream& Fast_Ostream::operator<<(bool _Val) {
buf.push_back(_Val ? '1' : '0');
return *this;
}
Fast_Ostream& Fast_Ostream::operator<<(short _Val) {
Put_Int(_Val);
return *this;
}
Fast_Ostream& Fast_Ostream::operator<<(int _Val) {
Put_Int(_Val);
return *this;
}
Fast_Ostream& Fast_Ostream::operator<<(long _Val) {
Put_Int(_Val);
return *this;
}
Fast_Ostream& Fast_Ostream::operator<<(long long _Val) {
Put_Int(_Val);
return *this;
}
Fast_Ostream& Fast_Ostream::operator<<(unsigned short _Val) {
Put_Unsigned(_Val);
return *this;
}
Fast_Ostream& Fast_Ostream::operator<<(unsigned int _Val) {
Put_Unsigned(_Val);
return *this;
}
Fast_Ostream& Fast_Ostream::operator<<(unsigned long _Val) {
Put_Unsigned(_Val);
return *this;
}
Fast_Ostream& Fast_Ostream::operator<<(unsigned long long _Val) {
Put_Unsigned(_Val);
return *this;
}
template <typename Typex>
void Fast_Ostream::endl(const Typex& _Val) {
*this << _Val << '\n';
}
template <typename Typex, typename... More>
void Fast_Ostream::endl(const Typex& _Val, const More&... _More) {
*this << _Val;
endl(_More...);
}
template <typename Typex>
void Fast_Ostream::operator()(const Typex& _Val) {
//*this << _Val;
}
template <typename Typex, typename... More>
void Fast_Ostream::operator()(const Typex& _Val, const More&... _More) {
*this << _Val;
operator()(_More...);
}
}
class fastIO{private:char ibuf[50007],*p1=ibuf,*p2=ibuf,obuf[50007],*p3=obuf,sta[50];bool file_end=false;char get(){return p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,50007,stdin),p1==p2)?(file_end=true),char(EOF):*p1++;}void put(const char x){p3-obuf<50007?*p3++=x:(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x);}public:explicit operator bool(){return!file_end;}size_t flush(){size_t f=fwrite(obuf,p3-obuf,1,stdout);p3=obuf;*p3=0;return f;}fastIO&operator>>(char&t){for(t=get();!isgraph(t);t=get());return*this;}template<typename any>typename std::enable_if<std::is_same<any,char>::value,any>::type tpval(){char t;for(t=get();!isgraph(t);t=get());return t;}fastIO&operator>>(char*t){char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())*t=c,t++;*t=0;return*this;}fastIO&operator>>(std::string&t){t.clear();char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())t+=c;return*this;}template<typename any>typename std::enable_if<std::is_same<any,std::string>::value,any>::type tpval(){std::string t;char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())t+=c;return t;}template<typename any>typename std::enable_if<(std::is_signed<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__int128_t>::value,fastIO>::type&operator>>(any&t){t=0;bool y=0;char c=get();for(;!isdigit(c);c=get())if(c==45)y=true;for(;isdigit(c);c=get())t=t*10+c-48;if(y==1)t=-t;return*this;}template<typename any>typename std::enable_if<(std::is_signed<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__int128_t>::value,any>::type tpval(){any t=0;bool y=0;char c=get();for(;!isdigit(c);c=get())if(c==45)y=true;for(;isdigit(c);c=get())t=t*10+c-48;if(y==1)t=-t;return t;}template<typename any>typename std::enable_if<(std::is_unsigned<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__uint128_t>::value,fastIO>::type&operator>>(any&t){t=0;char c=get();for(;!isdigit(c);c=get());for(;isdigit(c);c=get())t=t*10+c-48;return*this;}template<typename any>typename std::enable_if<(std::is_unsigned<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__uint128_t>::value,any>::type tpval(){any t=0;char c=get();for(;!isdigit(c);c=get());for(;isdigit(c);c=get())t=t*10+c-48;return t;}template<typename any1,typename any2>fastIO&operator>>(std::pair<any1,any2>&t){return*this>>t.first>>t.second;}template<typename any1,typename any2>std::pair<any1,any2>tpval(){return std::pair<any1,any2>(tpval<any1>(),tpval<any2>());}template<typename any>fastIO&read(any&t){return*this>>t;}fastIO&read(char*t){char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())*t=c,t++;*t=0;return*this;}template<typename any,typename...args>fastIO&read(any&t1,args&...t2){return(*this>>t1).read(t2...);}fastIO&operator<<(const char t){put(t);return*this;}fastIO&operator<<(const char*t){for(;*t;t++)put(*t);return*this;}fastIO&operator<<(const std::string&t){for(const char it:t)put(it);return*this;}template<typename any>typename std::enable_if<(std::is_signed<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__int128_t>::value,fastIO>::type&operator<<(any t){if(!t){put(48);return*this;}int len=0;if(t<0)t=-t,put(45);while(t)sta[len++]=char(t%10+48),t/=10;while(len--)put(sta[len]);return*this;}template<typename any>typename std::enable_if<(std::is_unsigned<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__uint128_t>::value,fastIO>::type&operator<<(any t){if(!t){put(48);return*this;}int len=0;while(t)sta[len++]=char(t%10+48),t/=10;while(len--)put(sta[len]);return*this;}template<typename any1,typename any2>fastIO&operator<<(const std::pair<any1,any2>&t){return*this<<t.first<<' '<<t.second;}template<typename any>fastIO&write(const any&t){return*this<<t;}template<typename any,typename...args>fastIO&write(const any&t1,const args&...t2){return(*this<<t1).write(t2...);}~fastIO(){fwrite(obuf,p3-obuf,1,stdout);}}fio;
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<33&&ch!=EOF)
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(!isspace(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
#undef BUFFER_SIZE
}
using namespace Octane;