template <typename T>
T reduce2(T v) {
T k = ((v * 410) >> 12) & 0x000F000F000F000Full;
return (((v - k * 10) << 8) + k);
}
template <typename T>
T reduce4(T v) {
T k = ((v * 10486) >> 20) & 0xFF000000FFull;
return reduce2(((v - k * 100) << 16) + (k));
}
typedef unsigned long long ull;
inline ull reduce8(ull v) {
ull k = ((v * 3518437209u) >> 45);
return reduce4(((v - k * 10000) << 32) + (k));
}
template <typename T>
std::string itostr(T o) {
union {
char str[16];
unsigned short u2[8];
unsigned u4[4];
unsigned long long u8[2];
};
unsigned v = o < 0 ? ~o + 1 : o;
u8[0] = (ull(v) * 3518437209u) >> 45;
u8[0] = (u8[0] * 28147497672ull);
u8[1] = v - u2[3] * 100000000;
u8[1] = reduce8(u8[1]);
char* f;
if (u2[3]) {
u2[3] = reduce2(u2[3]);
f = str + 6;
} else {
unsigned short* k = u4[2] ? u2 + 4 : u2 + 6;
f = *k ? (char*)k : (char*)(k + 1);
}
if (!*f) f++;
u4[1] |= 0x30303030;
u4[2] |= 0x30303030;
u4[3] |= 0x30303030;
if (o < 0) *--f = '-';
return std::string(f, (str + 16) - f);
}
dGVtcGxhdGUgPHR5cGVuYW1lIFQ+IApUIHJlZHVjZTIoVCB2KSB7CiAgICBUIGsgPSAoKHYgKiA0MTApID4+IDEyKSAmIDB4MDAwRjAwMEYwMDBGMDAwRnVsbDsKICAgIHJldHVybiAoKCh2IC0gayAqIDEwKSA8PCA4KSArIGspOwp9Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4KVCByZWR1Y2U0KFQgdikgewogICAgVCBrID0gKCh2ICogMTA0ODYpID4+IDIwKSAmIDB4RkYwMDAwMDBGRnVsbDsKICAgIHJldHVybiByZWR1Y2UyKCgodiAtIGsgKiAxMDApIDw8IDE2KSArIChrKSk7Cn0KCnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIHVsbDsKaW5saW5lIHVsbCByZWR1Y2U4KHVsbCB2KSB7CiAgICB1bGwgayA9ICgodiAqIDM1MTg0MzcyMDl1KSA+PiA0NSk7CiAgICByZXR1cm4gcmVkdWNlNCgoKHYgLSBrICogMTAwMDApIDw8IDMyKSArIChrKSk7Cn0KCnRlbXBsYXRlIDx0eXBlbmFtZSBUPgpzdGQ6OnN0cmluZyBpdG9zdHIoVCBvKSB7CiAgICB1bmlvbiB7CiAgICAgICAgY2hhciBzdHJbMTZdOwogICAgICAgIHVuc2lnbmVkIHNob3J0IHUyWzhdOwogICAgICAgIHVuc2lnbmVkIHU0WzRdOwogICAgICAgIHVuc2lnbmVkIGxvbmcgbG9uZyB1OFsyXTsKICAgIH07CgogICAgdW5zaWduZWQgdiA9IG8gPCAwID8gfm8gKyAxIDogbzsKCiAgICB1OFswXSA9ICh1bGwodikgKiAzNTE4NDM3MjA5dSkgPj4gNDU7CiAgICB1OFswXSA9ICh1OFswXSAqIDI4MTQ3NDk3NjcydWxsKTsKICAgIHU4WzFdID0gdiAtIHUyWzNdICogMTAwMDAwMDAwOwoKICAgIHU4WzFdID0gcmVkdWNlOCh1OFsxXSk7CiAgICBjaGFyKiBmOwogICAgaWYgKHUyWzNdKSB7CiAgICAgICAgdTJbM10gPSByZWR1Y2UyKHUyWzNdKTsKICAgICAgICBmID0gc3RyICsgNjsKICAgIH0gZWxzZSB7CiAgICAgICAgdW5zaWduZWQgc2hvcnQqIGsgPSB1NFsyXSA/IHUyICsgNCA6IHUyICsgNjsKICAgICAgICBmID0gKmsgPyAoY2hhciopayA6IChjaGFyKikoayArIDEpOwogICAgfQogICAgaWYgKCEqZikgZisrOwoKICAgIHU0WzFdIHw9IDB4MzAzMDMwMzA7CiAgICB1NFsyXSB8PSAweDMwMzAzMDMwOwogICAgdTRbM10gfD0gMHgzMDMwMzAzMDsKICAgIGlmIChvIDwgMCkgKi0tZiA9ICctJzsKICAgIHJldHVybiBzdGQ6OnN0cmluZyhmLCAoc3RyICsgMTYpIC0gZik7Cn0K