/** * */ // #include {{{ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef DEBUG #include #include #endif using namespace std; // }}} // type {{{ using s8 = int8_t; using u8 = uint8_t; using s16 = int16_t; using u16 = uint16_t; using s32 = int32_t; using u32 = uint32_t; using s64 = int64_t; using u64 = uint64_t; template using max_heap = priority_queue, less>; template using min_heap = priority_queue, greater>; // }}} // hide {{{ #ifdef __clang__ #pragma clang diagnostic push #pragma clang diagnostic ignored "-Wunused-const-variable" #endif // }}} // 適宜調整 //#define int s64 //#define double long double constexpr bool AUTOFLUSH = false; constexpr bool STDIO_ENABLE = false; constexpr int IOS_PREC = 10; constexpr int INF_S32 = 1'010'000'000; constexpr s64 INF_S64 = 1'010'000'000'000'000'000LL; constexpr auto INF = INF_S64; constexpr double EPS = 1e-9; constexpr s64 MOD = 1'000'000'007; // hide {{{ #ifdef __clang__ #pragma clang diagnostic pop #endif // }}} // util {{{ template struct ArrayStruct { using type = array::type,N>; }; template struct ArrayStruct { using type = array; }; template using Array = typename ArrayStruct::type; template constexpr bool is_odd(T x) { return x % 2 != 0; } template constexpr bool is_even(T x) { return x % 2 == 0; } template constexpr int cmp(T x, T y) { return (x > y) - (x < y); } template constexpr int sgn(T x) { return cmp(x, T(0)); } template constexpr T ipow(T a, T b) { assert(b >= 0); T res(1); for(T i = 0; i < b; ++i) res *= a; return res; } template< typename T, std::enable_if_t< std::is_integral::value && std::is_signed::value, std::nullptr_t> = nullptr> constexpr T div_ceil(T a, T b) { return a/b + (((a<0)^(b>0)) && (a%b)); } template< typename T, std::enable_if_t< std::is_integral::value && std::is_unsigned::value, std::nullptr_t> = nullptr> constexpr T div_ceil(T a, T b) { return a/b + !!(a%b); } template< typename T, std::enable_if_t< std::is_integral::value && std::is_signed::value, std::nullptr_t> = nullptr> constexpr T div_floor(T a, T b) { return a/b - (((a>0)^(b>0)) && (a%b)); } template< typename T, std::enable_if_t< std::is_integral::value && std::is_unsigned::value, std::nullptr_t> = nullptr> constexpr T div_floor(T a, T b) { return a/b; } template constexpr typename enable_if::value,T>::type modulo(T a, T b) { assert(b > 0); T r = a % b; return r >= 0 ? r : r+b; } template constexpr T clamp(T x, T lo, T hi) { assert(lo <= hi); if(x < lo) return lo; else if(x > hi) return hi; else return x; } int sqrti(int x) { assert(x >= 0); return static_cast(sqrt(x)); } s64 sqrtl(s64 x) { assert(x >= 0); return static_cast(sqrt(x)); } template bool chmax(T& xmax, const T& x) { if(x > xmax) { xmax = x; return true; } else { return false; } } template bool chmin(T& xmin, const T& x) { if(x < xmin) { xmin = x; return true; } else { return false; } } template constexpr int SIZE(const T& c) { return static_cast(c.size()); } template constexpr int SIZE(const T (&)[N]) { return static_cast(N); } template int argfind(InputIt first, InputIt last, const T& x) { auto it = find(first, last, x); return distance(first, it); } template int argmax(InputIt first, InputIt last) { auto it = max_element(first, last); return distance(first, it); } template int argmin(InputIt first, InputIt last) { auto it = min_element(first, last); return distance(first, it); } template bool alltrue(InputIt first, InputIt last) { return all_of(first, last, [](bool b) { return b; }); } template bool anytrue(InputIt first, InputIt last) { return any_of(first, last, [](bool b) { return b; }); } template bool allfalse(InputIt first, InputIt last) { return !anytrue(first, last); } template bool anyfalse(InputIt first, InputIt last) { return !alltrue(first, last); } template array,4> neighbor4(const T& x, const T& y) { return array,4> {{ { x, y-1 }, { x-1, y }, { x+1, y }, { x, y+1 }, }}; } template array,8> neighbor8(const T& x, const T& y) { return array,8> {{ { x-1, y-1 }, { x, y-1 }, { x+1, y-1 }, { x-1, y }, { x+1, y }, { x-1, y+1 }, { x, y+1 }, { x+1, y+1 }, }}; } template bool in_bounds(const T& x, const T& minx, const T& maxx) { return !(x < minx) && !(maxx < x); } template bool in_bounds_2( const T& x, const T& y, const T& minx, const T& miny, const T& maxx, const T& maxy) { return in_bounds(x, minx, maxx) && in_bounds(y, miny, maxy); } template bool in_bounds_wh(const T& x, const T& y, const T& w, const T& h) { return in_bounds_2(x, y, 0, 0, w-1, h-1); } struct pairhash { template size_t operator()(const pair& p) const { size_t ans = 17; ans = 31*ans + hash()(p.first); ans = 31*ans + hash()(p.second); return ans; } }; template pair::iterator, bool> insert_or_assign(map& m, const K& k, const V& v) { auto it = m.lower_bound(k); if(it != end(m) && !m.key_comp()(k,it->first)) { it->second = v; return make_pair(it, false); } else { auto it_ins = m.insert(it, make_pair(k,v)); return make_pair(it_ins, true); } } template pair::iterator, bool> insert_or_assign(unordered_map& m, const K& k, const V& v) { auto it = m.find(k); if(it != end(m)) { it->second = v; return make_pair(it, false); } else { auto it_ins = m.insert(it, make_pair(k,v)); return make_pair(it_ins, true); } } template string TO_STRING(const T& x) { ostringstream out; out << x; return out.str(); } template string JOIN(InputIt first, InputIt last, const string& sep) { ostringstream out; while(first != last) { out << *first++; if(first != last) out << sep; } return out.str(); } template auto SUM(InputIt first, InputIt last) { using T = typename iterator_traits::value_type; return accumulate(first, last, T()); } template void UNIQ(T& c) { c.erase(unique(begin(c), end(c)), end(c)); } template enable_if_t::value==0> ARRAY_FOREACH(T& e, F f) { f(e); } template enable_if_t::value!=0> ARRAY_FOREACH(Array& ary, F f) { for(auto& e : ary) ARRAY_FOREACH(e, f); } template enable_if_t::value!=0> ARRAY_FILL(Array& ary, const U& v) { ARRAY_FOREACH(ary, [&v](auto& elem) { elem = v; }); } template T POP(stack& stk) { T x = stk.top(); stk.pop(); return x; } template T POP(queue& que) { T x = que.front(); que.pop(); return x; } template T POP(priority_queue& que) { T x = que.top(); que.pop(); return x; } template void RD(T& x) { cin >> x; #ifdef DEBUG if(!cin) assert(false); #endif } template void RD(vector& v, int n) { v.reserve(n); for(int i = 0; i < n; ++i) { T e; RD(e); v.emplace_back(e); } } // 出力 {{{ // FPRINTSEQ {{{ template ostream& FPRINTSEQ(ostream& out, InputIt first, InputIt last) { for(InputIt it = first; it != last; ++it) { if(it != first) out << ' '; out << *it; } return out; } template ostream& PRINTSEQ(InputIt first, InputIt last) { return FPRINTSEQ(cout, first, last); } template ostream& DPRINTSEQ(InputIt first, InputIt last) { return FPRINTSEQ(cerr, first, last); } // }}} // 1次元生配列 {{{ template ostream& FPRINTARRAY1(ostream& out, const T (&c)[N]) { return FPRINTSEQ(out, cbegin(c), cend(c)); } template ostream& PRINTARRAY1(const T (&c)[N]) { return FPRINTARRAY1(cout, c); } template ostream& DPRINTARRAY1(const T (&c)[N]) { return FPRINTARRAY1(cerr, c); } // }}} // 2次元生配列 {{{ template ostream& FPRINTARRAY2(ostream& out, const T (&c)[N1][N2]) { out << '\n'; for(const auto& e : c) { FPRINTARRAY1(out, e) << '\n'; } return out; } template ostream& PRINTARRAY2(const T (&c)[N1][N2]) { return FPRINTARRAY2(cout, c); } template ostream& DPRINTARRAY2(const T (&c)[N1][N2]) { return FPRINTARRAY2(cerr, c); } // }}} // 非mapコンテナ {{{ template ostream& operator<<(ostream& out, const vector& c) { return FPRINTSEQ(out, cbegin(c), cend(c)); } // 特別扱い template ostream& operator<<(ostream& out, const vector>& c) { out << '\n'; for(const auto& e : c) { out << e << '\n'; } return out; } // 特別扱い ostream& operator<<(ostream& out, const vector& c) { out << '\n'; for(const string& e : c) { out << e << '\n'; } return out; } template ostream& operator<<(ostream& out, const deque& c) { return FPRINTSEQ(out, cbegin(c), cend(c)); } template ostream& operator<<(ostream& out, const list& c) { return FPRINTSEQ(out, cbegin(c), cend(c)); } template ostream& operator<<(ostream& out, const forward_list& c) { return FPRINTSEQ(out, cbegin(c), cend(c)); } template ostream& operator<<(ostream& out, const set& c) { return FPRINTSEQ(out, cbegin(c), cend(c)); } template ostream& operator<<(ostream& out, const unordered_set& c) { return out << set(cbegin(c), cend(c)); } template ostream& operator<<(ostream& out, const multiset& c) { return FPRINTSEQ(out, cbegin(c), cend(c)); } template ostream& operator<<(ostream& out, const unordered_multiset& c) { return out << multiset(cbegin(c), cend(c)); } template ostream& operator<<(ostream& out, const array& c) { return FPRINTSEQ(out, cbegin(c), cend(c)); } // }}} // mapコンテナ {{{ template ostream& FPRINTMAP(ostream& out, InputIt first, InputIt last) { out << "{\n"; for(auto it = first; it != last; ++it) { out << " " << it->first << " : " << it->second << '\n'; } out << "}\n"; return out; } template ostream& PRINTMAP(InputIt first, InputIt last) { return FPRINTMAP(cout, first, last); } template ostream& DPRINTMAP(InputIt first, InputIt last) { return FPRINTMAP(cerr, first, last); } template ostream& operator<<(ostream& out, const map& c) { return FPRINTMAP(out, cbegin(c), cend(c)); } template ostream& operator<<(ostream& out, const unordered_map& c) { return out << map(cbegin(c), cend(c)); } template ostream& operator<<(ostream& out, const multimap& c) { return FPRINTMAP(out, cbegin(c), cend(c)); } template ostream& operator<<(ostream& out, const unordered_multimap& c) { return out << multimap(cbegin(c), cend(c)); } // }}} // stack/queue/priority_queue {{{ template ostream& operator<<(ostream& out, stack c) { while(!c.empty()) { out << c.top(); c.pop(); if(!c.empty()) out << ' '; } return out; } template ostream& operator<<(ostream& out, queue c) { while(!c.empty()) { out << c.front(); c.pop(); if(!c.empty()) out << ' '; } return out; } template ostream& operator<<(ostream& out, priority_queue c) { while(!c.empty()) { out << c.top(); c.pop(); if(!c.empty()) out << ' '; } return out; } // }}} // pair/tuple {{{ template ostream& operator<<(ostream& out, const pair& p) { return out << '(' << p.first << ',' << p.second << ')'; } template ostream& FPRINTTUPLE(ostream& out, const Tuple&) { return out; } template ostream& FPRINTTUPLE(ostream& out, const Tuple& t) { if(Pos != 0) out << ','; out << get(t); return FPRINTTUPLE(out, t); } template ostream& operator<<(ostream& out, const tuple& t) { out << '('; FPRINTTUPLE,0,TS...>(out, t); out << ')'; return out; } // }}} // PRINT {{{ ostream& FPRINT(ostream& out) { return out; } template ostream& FPRINT(ostream& out, const T& x, const TS& ...args) { out << x; if(sizeof...(args)) out << ' '; return FPRINT(out, args...); } template ostream& FPRINTLN(ostream& out, const TS& ...args) { FPRINT(out, args...); return out << '\n'; } template ostream& PRINT(const TS& ...args) { return FPRINT(cout, args...); } template ostream& PRINTLN(const TS& ...args) { return FPRINTLN(cout, args...); } template ostream& DPRINT(const TS& ...args) { return FPRINT(cerr, args...); } template ostream& DPRINTLN(const TS& ...args) { return FPRINTLN(cerr, args...); } // }}} // }}} void FLUSH() { if(STDIO_ENABLE) fflush(stdout); else cout.flush(); } [[noreturn]] void EXIT() { #ifdef DEBUG fflush(stdout); fflush(stderr); cout.flush(); cerr.flush(); #else FLUSH(); #endif //quick_exit(0); // does not work on codeforces _Exit(0); } struct IoInit { IoInit() { #ifndef DEBUG cin.tie(nullptr); if(!STDIO_ENABLE) ios::sync_with_stdio(false); #endif cout << fixed << setprecision(IOS_PREC); if(AUTOFLUSH) { if(STDIO_ENABLE) setvbuf(stdout, nullptr, _IONBF, 0); cout << unitbuf; } } } IOINIT; #define FOR(i, start, end) for(s64 i = (start); i < (end); ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(f,c,...) (([&](decltype((c)) cc) { return (f)(begin(cc), end(cc), ## __VA_ARGS__); })(c)) #define GENERIC(f) ([](auto&&... args) -> decltype(auto) { return (f)(forward(args)...); }) #define MEMSET(a,v) memset((a), (v), sizeof(a)) #define DBG(x) DPRINTLN('L', __LINE__, ':', #x, ':', (x)) // }}} int popcount(u64 n) { n = (n & 0x5555555555555555ULL) + ((n>> 1) & 0x5555555555555555ULL); n = (n & 0x3333333333333333ULL) + ((n>> 2) & 0x3333333333333333ULL); n = (n & 0x0F0F0F0F0F0F0F0FULL) + ((n>> 4) & 0x0F0F0F0F0F0F0F0FULL); n = (n & 0x00FF00FF00FF00FFULL) + ((n>> 8) & 0x00FF00FF00FF00FFULL); n = (n & 0x0000FFFF0000FFFFULL) + ((n>>16) & 0x0000FFFF0000FFFFULL); n = (n & 0x00000000FFFFFFFFULL) + ((n>>32) & 0x00000000FFFFFFFFULL); return n; } u64 N; void solve() { if(N == 0) { PRINTLN(0); return; } u64 cnt = popcount(N); u64 ans = (N+1) - (1ULL<