#include<string>
struct IO {
#include <cstdio>
#include <iostream>
using std::string;
char buf[1 << 20], * ptr; // 1 MB output buffer
char tmp[1 << 10];
// fast input routines
char cur;
inline char nextChar() { return cur = getc_unlocked(stdin); }
inline char peekChar() { return cur; }
inline operator bool() { return (peekChar() != 0); }
inline static bool isBlank(char c) { return (c < '.' && c); }
inline bool skipBlanks() { while (isBlank(nextChar())); return peekChar() != 0; }
inline IO& operator >> (char & c) { c = nextChar(); return *this; }
inline IO& operator >> (char * buf) {
if (skipBlanks()) {
if (peekChar()) {
*(buf++) = peekChar();
while (!isBlank(nextChar())) *(buf++) = peekChar();
} *(buf++) = 0; } return *this; }
inline IO& operator >> (string & s) {
if (skipBlanks()) { s.clear(); s += peekChar();
while (!isBlank(nextChar())) s += peekChar(); }
return *this; }
inline IO& operator >> (double & d) { if ((*this) >> tmp) sscanf(tmp, "%lf", &d); return *this; }
#define defineInFor(intType) \
inline IO& operator >>(intType & n) { \
if (skipBlanks()) { \
int sign = +1; \
if (peekChar() == '-') { \
sign = -1; \
n = nextChar() - '0'; \
} else \
n = peekChar() - '0'; \
while (!isBlank(nextChar())) { \
n *= 10; \
n += peekChar() - '0'; \
} \
n *= sign; \
} \
return *this; \
}
defineInFor(int)
defineInFor(unsigned int)
defineInFor(long long)
defineInFor(unsigned long long)
defineInFor(short)
defineInFor(unsigned short)
// fast output routines
IO() { cur = 0; ptr = buf; }
void flush() { fwrite(buf, 1, ptr - buf, stdout); ptr = buf; }
~IO() { flush(); }
inline void putChar(char c) {
if (ptr >= buf + sizeof(buf))
flush();
*ptr++ = c;
#ifndef ONLINE_JUDGE
flush(); // always flush when local
#endif
}
inline IO& operator << (char c) { putChar(c); return *this; }
inline IO& operator << (char * s) { while (*s) putChar(*s++); return *this; }
inline IO& operator << (string & s) { for (int i = 0; i < (int)s.size(); ++i) putChar(s[i]); return *this; }
char * toString(double d) { sprintf(tmp, "%lf%c", d, '\0'); return tmp; }
inline IO& operator << (double d) { return (*this) << toString(d); }
#define defineOutFor(intType) \
inline char * toString(intType n) { \
char * p = (tmp + 30); \
*p-- = 0; \
if (n == 0) *p-- = '0'; \
else { \
bool isNeg = 0; \
if (n < 0) isNeg = 1, n = -n; \
while (n > 0) *p-- = (n % 10) + '0', n /= 10; \
if (isNeg) *p-- = '-'; \
} \
return p + 1; \
} \
inline IO& operator << (intType n) { return (*this) << toString(n); }
defineOutFor(int)
defineOutFor(unsigned int)
defineOutFor(long long)
defineOutFor(unsigned long long)
defineOutFor(short)
defineOutFor(unsigned short)
#define endl ('\n')
#define cout __io__
#define cin __io__
} __io__;
int getline(IO & io, string & s) {
s.clear(); char c;
while ((io >> c) && (c != '\n' && c != '\r')) s += c;
if (c == '\r') io >> c; // CR LF found -> skip \n
return (int)s.size();
}