/** * */ #define ASSERT_LV 1 // header {{{ #ifndef ASSERT_LV # define ASSERT_LV 1 #endif #if ASSERT_LV == 0 # define NDEBUG #endif #if defined(__GNUC__) && !defined(__clang__) #include #else #include #include #include #include #include #include //#include #include //#include //#include #include #include #include #include #include #include //#include //#include #if __cplusplus >= 201103L //#include #include #include //#include //#include #include //#include //#include #endif #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 #if __cplusplus >= 201103L #include //#include #include //#include //#include #include //#include #include //#include #include #include #include #include //#include #include #include #include #include #include #include #endif #if __cplusplus >= 201402L //#include #endif #if __cplusplus >= 201703L #include //#include //#include //#include #include //#include #include #include #endif #endif using namespace std; using i8 = int8_t; using u8 = uint8_t; using i16 = int16_t; using u16 = uint16_t; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #ifdef __SIZEOF_INT128__ using i128 = __int128; using u128 = unsigned __int128; #endif using f32 = float; using f64 = double; using f80 = long double; template constexpr T PROCON_INF(); template<> constexpr i32 PROCON_INF() { return 1'010'000'011; } template<> constexpr i64 PROCON_INF() { return INT64_C(1'010'000'000'000'000'017); } template<> constexpr f32 PROCON_INF() { return 1e19F; } template<> constexpr f64 PROCON_INF() { return 1e100; } template<> constexpr f80 PROCON_INF() { return 1e100L; } // }}} using Int = i64; using Real = f80; constexpr Int MOD = 1'000'000'007; //constexpr Int MOD = 998'244'353; constexpr Real EPS = Real(1e-10L); constexpr int COUT_PREC = 15; constexpr bool COUT_AUTOFLUSH = false; // procon {{{ static_assert(is_same::value || is_same::value, ""); static_assert(is_same::value || is_same::value || is_same::value, ""); #define CPP_STR(x) CPP_STR_I(x) #define CPP_CAT(x,y) CPP_CAT_I(x,y) #define CPP_STR_I(args...) #args #define CPP_CAT_I(x,y) x ## y #define SFINAE(pred...) std::enable_if_t<(pred), std::nullptr_t> = nullptr #define ASSERT(expr...) assert((expr)) #if defined(PROCON_LOCAL) || ASSERT_LV >= 2 # define ASSERT_LOCAL(expr...) assert((expr)) #else # define ASSERT_LOCAL(expr...) #endif constexpr Int INF = PROCON_INF(); constexpr Real FINF = PROCON_INF(); constexpr Real PI = Real(3.141592653589793238462643383279502884197L); template constexpr T SQRT_MAX(); template<> constexpr i32 SQRT_MAX() { return 46340; } template<> constexpr i64 SQRT_MAX() { return INT64_C(3037000499); } template::value)> constexpr T ABS(T x) noexcept { return x < 0 ? -x : x; } constexpr bool LT_EPS(Real lhs, Real rhs, Real eps=EPS) { return lhs < rhs-eps; } constexpr bool GT_EPS(Real lhs, Real rhs, Real eps=EPS) { return lhs > rhs+eps; } constexpr bool EQ_EPS(Real lhs, Real rhs, Real eps=EPS) { return ABS(lhs-rhs) <= eps; } constexpr bool EQ_EXACT(Real lhs, Real rhs) { #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wfloat-equal" return lhs == rhs; #pragma GCC diagnostic pop } #define FOR(i, start, end) for(Int i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i) #define REP(i, n) FOR(i, 0, n) #define LOOP(n) REP(CPP_CAT(macro_loop_counter,__COUNTER__), n) #define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c)) #define SLICE(f,c,l,r,...) (([&](decltype((c)) cccc, decltype((l)) llll, decltype((r)) rrrr) {\ auto iiii = llll <= rrrr ? std::begin(cccc)+llll : std::end(cccc);\ auto jjjj = llll <= rrrr ? std::begin(cccc)+rrrr : std::end(cccc);\ return (f)(iiii, jjjj, ## __VA_ARGS__);\ })(c,l,r)) #define LIFT(f) ([](auto&&... args) -> decltype(auto) { return (f)(std::forward(args)...); }) template constexpr Int SIZE(const C& c) noexcept { return Int(c.size()); } template constexpr Int SIZE(const T (&)[N]) noexcept { return Int(N); } constexpr bool is_odd (Int x) { return x%2 != 0; } constexpr bool is_even(Int x) { return x%2 == 0; } constexpr Int PARITY(Int x) { return x%2==0 ? 0 : 1; } template constexpr Int CMP(T x, T y) noexcept { return (y constexpr Int SGN(T x) noexcept { return CMP(x,T(0)); } template, SFINAE( is_integral::value && is_integral::value && is_signed::value != is_unsigned::value )> constexpr auto MAX(T1 x, T2 y, Comp comp={}) { return max>({x,y}, comp); } template, SFINAE( is_floating_point::value && is_floating_point::value )> constexpr auto MAX(T1 x, T2 y, Comp comp={}) { return max>({x,y}, comp); } template> constexpr const T& MAX(const T& x, const T& y, Comp comp={}) { return max(x, y, comp); } template> constexpr T MAX(initializer_list ilist, Comp comp={}) { return max(ilist, comp); } template, SFINAE( is_integral::value && is_integral::value && is_signed::value != is_unsigned::value )> constexpr auto MIN(T1 x, T2 y, Comp comp={}) { return min>({x,y}, comp); } template, SFINAE( is_floating_point::value && is_floating_point::value )> constexpr auto MIN(T1 x, T2 y, Comp comp={}) { return min>({x,y}, comp); } template> constexpr const T& MIN(const T& x, const T& y, Comp comp={}) { return min(x, y, comp); } template> constexpr T MIN(initializer_list ilist, Comp comp={}) { return min(ilist, comp); } template> constexpr bool chmax(T& xmax, const U& x, Comp comp={}) noexcept { if(comp(xmax, x)) { xmax = x; return true; } return false; } template> constexpr bool chmin(T& xmin, const U& x, Comp comp={}) noexcept { if(comp(x, xmin)) { xmin = x; return true; } return false; } template auto ON(BinaryFunc&& bf, UnaryFunc&& uf) { return [bf=forward(bf),uf=forward(uf)](const auto& x, const auto& y) { return bf(uf(x), uf(y)); }; } template auto LT_ON(F&& f) { return ON(less<>{}, forward(f)); } template auto GT_ON(F&& f) { return ON(greater<>{}, forward(f)); } template auto NOT_FN(F&& f) { return [f=forward(f)](auto&&... args) -> bool { return !f(forward(args)...); }; } struct IDENTITY { using is_transparent = void; template constexpr decltype(auto) operator()(T&& x) const { return forward(x); } }; // ビット演算 {{{ // 引数は [-INF,INF] のみ想定 constexpr Int BIT_I(Int i) { return Int(1) << i; } constexpr Int BIT_I_1(Int i) { return BIT_I(i) - 1; } constexpr Int BIT_GET(Int x, Int i) { return x & BIT_I(i); } constexpr bool BIT_TEST(Int x, Int i) { return BIT_GET(x,i) != 0; } constexpr Int BIT_SET(Int x, Int i) { return x | BIT_I(i); } constexpr Int BIT_CLEAR(Int x, Int i) { return x & ~BIT_I(i); } constexpr Int BIT_FLIP(Int x, Int i) { return x ^ BIT_I(i); } constexpr Int BIT_ASSIGN(Int x, Int i, bool b) { return b ? BIT_SET(x,i) : BIT_CLEAR(x,i); } /*constexpr*/ Int BIT_COUNT_LEADING_ZEROS(Int x) { if(is_same::value) return x==0 ? 64 : __builtin_clzll(u64(x)); if(is_same::value) return x==0 ? 32 : __builtin_clz(u32(x)); ASSERT(false); } /*constexpr*/ Int BIT_COUNT_TRAILING_ZEROS(Int x) { if(is_same::value) return x==0 ? 64 : __builtin_ctzll(u64(x)); if(is_same::value) return x==0 ? 32 : __builtin_clz(u32(x)); ASSERT(false); } /*constexpr*/ Int BIT_COUNT_ONES(Int x) { if(is_same::value) return __builtin_popcountll(u64(x)); if(is_same::value) return __builtin_popcount(u32(x)); ASSERT(false); } // 1の個数が奇数なら1, 偶数なら0を返す /*constexpr*/ Int BIT_PARITY(Int x) { if(is_same::value) return __builtin_parityll(u64(x)); if(is_same::value) return __builtin_parity(u32(x)); ASSERT(false); } // X ⊆ {0,1,...,n-1}, |X| = k なる部分集合 X を昇順に列挙する // comb(n,k) 個 // // ``` // Int x = BIT_I_1(3); // do { // // ... // } while(BIT_NEXT_SET_SIZED(x, 10)); // ``` /*constexpr*/ bool BIT_NEXT_SET_SIZED(Int& x, Int n) { if(x == 0) return false; Int t = (x|(x-1)) + 1; x = t | ((~t&(t-1)) >> (BIT_COUNT_TRAILING_ZEROS(x)+1)); return x < BIT_I(n); } // 集合 Y の部分集合 X を昇順に列挙する // 2^|Y| 個 // // ``` // Int y = 0b10101; // Int x = 0; // do { // // ... // } while(BIT_NEXT_SUBSET(x, y)); // ``` constexpr bool BIT_NEXT_SUBSET(Int& x, Int y) { if(x == y) return false; x = (x-y) & y; return true; } // 集合 Y の部分集合 X を降順に列挙する // 2^|Y| 個 // // ``` // Int y = 0b10101; // Int x = y; // do { // // ... // } while(BIT_PREV_SUBSET(x, y)); // ``` constexpr bool BIT_PREV_SUBSET(Int& x, Int y) { if(x == 0) return false; x = (x-1) & y; return true; } // 集合 Y を包含する集合 X ⊆ {0,1,...,n-1} を昇順に列挙する // 2^(n-|Y|) 個 // // ``` // Int y = 0b00010101; // Int x = y; // do { // // ... // } while(BIT_NEXT_SUPERSET(x, 8, y)); // ``` constexpr bool BIT_NEXT_SUPERSET(Int& x, Int n, Int y) { x = (x+1) | y; return x < BIT_I(n); } // }}} // [lo,hi) 内で pred が真になる最大値を返す // 全部NGの場合 lo-1 を返す template /*constexpr*/ Int bisect_integer(Int lo, Int hi, Pred pred) { ASSERT(lo < hi); if(!pred(lo)) return lo-1; while(lo+1 < hi) { Int mid = (lo+hi) / 2; if(pred(mid)) lo = mid; else hi = mid; } return lo; } template /*constexpr*/ Real bisect_real(Real lo, Real hi, Pred pred, Real eps=EPS) { ASSERT_LOCAL(!GT_EPS(lo,hi,eps)); if(lo > hi) swap(lo, hi); while(!EQ_EPS(lo,hi,eps)) { Real mid = (lo+hi) / 2; if(pred(mid)) lo = mid; else hi = mid; } return lo; } template /*constexpr*/ Monoid fastpow(const Monoid& x, Int e, const Monoid& unity) { ASSERT(e >= 0); if(e == 0) return unity; Monoid res = unity; Monoid cur = x; for(;;) { if(e & 1) res *= cur; e >>= 1; if(e == 0) break; cur *= cur; } return res; } /*constexpr*/ Int ipow(Int x, Int e) { return fastpow(x,e,1); } /*constexpr*/ Int sqrt_floor(Int x) { ASSERT(x >= 0); Int lo = 0; Int hi = MIN(x/2+2, SQRT_MAX()+1); return bisect_integer(lo, hi, [x](Int r) { return r*r <= x; }); } /*constexpr*/ Int sqrt_ceil(Int x) { Int r = sqrt_floor(x); return r*r == x ? r : r+1; } /*constexpr*/ Int log2_ceil(Int x) { ASSERT(x > 0); if(is_same::value) return 64 - BIT_COUNT_LEADING_ZEROS(x-1); if(is_same::value) return 32 - BIT_COUNT_LEADING_ZEROS(x-1); ASSERT(false); } /*constexpr*/ Int log2_floor(Int x) { ASSERT(x > 0); if(is_same::value) return 63 - BIT_COUNT_LEADING_ZEROS(x); if(is_same::value) return 31 - BIT_COUNT_LEADING_ZEROS(x); ASSERT(false); } // x > 0 /*constexpr*/ Int pow2_ceil(Int x) { return BIT_I(log2_ceil(x)); } // x > 0 /*constexpr*/ Int pow2_floor(Int x) { return BIT_I(log2_floor(x)); } // Haskell の divMod と同じ constexpr pair divmod(Int a, Int b) { Int q = a / b; Int r = a % b; if((b>0 && r<0) || (b<0 && r>0)) { --q; r += b; } return {q,r}; } constexpr Int div_ceil(Int a, Int b) { Int q = a / b; Int r = a % b; if((b>0 && r>0) || (b<0 && r<0)) ++q; return q; } constexpr Int div_floor(Int a, Int b) { return divmod(a,b).first; } constexpr Int modulo(Int a, Int b) { return divmod(a,b).second; } /*constexpr*/ Int align_ceil(Int x, Int align) { ASSERT(align > 0); return div_ceil(x,align) * align; } /*constexpr*/ Int align_floor(Int x, Int align) { ASSERT(align > 0); return div_floor(x,align) * align; } template auto FOLD(InputIt first, InputIt last, typename iterator_traits::value_type init, BinaryOp op) { for(; first != last; ++first) init = op(move(init), *first); return init; } template auto FOLD1(InputIt first, InputIt last, BinaryOp op) { auto init = *first++; return FOLD(first, last, init, op); } template auto SUM(InputIt first, InputIt last) { return FOLD1(first, last, plus<>{}); } template void ERASE_IF(C& c, Pred pred) { c.erase(ALL(remove_if,c,pred), end(c)); } template void UNIQ(C& c) { c.erase(ALL(unique,c), end(c)); } template void SORT_UNIQ(C& c) { ALL(sort, c); UNIQ(c); } [[noreturn]] void EXIT() { cout.flush(); #ifdef PROCON_LOCAL cerr.flush(); exit(0); #else _Exit(0); #endif } // tuple {{{ template void tuple_enumerate(tuple&, F&&) {} template I)> void tuple_enumerate(tuple& t, F&& f) { f(I, get(t)); tuple_enumerate(t, forward(f)); } template void tuple_enumerate(const tuple&, F&&) {} template I)> void tuple_enumerate(const tuple& t, F&& f) { f(I, get(t)); tuple_enumerate(t, forward(f)); } // }}} // container {{{ template struct is_container : false_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct ProconHash { size_t operator()(const T& x) const noexcept { return hash{}(x); } }; template size_t procon_hash_value(const T& x) noexcept { return ProconHash{}(x); } size_t procon_hash_combine(size_t h1, size_t h2) noexcept { constexpr size_t M = UINT64_C(0xc6a4a7935bd1e995); constexpr int R = 47; h2 *= M; h2 ^= h2 >> R; h2 *= M; h1 ^= h2; h1 *= M; h1 += 0xe6546b64; return h1; } template struct ProconHash> { size_t operator()(const pair& p) const noexcept { size_t h1 = procon_hash_value(p.first); size_t h2 = procon_hash_value(p.second); return procon_hash_combine(h1, h2); } }; template struct ProconHash> { size_t operator()(const tuple& t) const noexcept { size_t h = 0; tuple_enumerate(t, [&h](Int, const auto& e) { h = procon_hash_combine(h, procon_hash_value(e)); }); return h; } }; template struct ProconHash::value>> { size_t operator()(const C& c) const noexcept { size_t h = 0; for(const auto& e : c) h = procon_hash_combine(h, procon_hash_value(e)); return h; } }; template, class Eq=equal_to> using HashSet = unordered_set; template, class Eq=equal_to> using HashMap = unordered_map; template, class Eq=equal_to> using HashMultiset = unordered_multiset; template, class Eq=equal_to> using HashMultimap = unordered_multimap; template auto vec_make(Int n, T x) { return vector(n, x); } template= 2)> auto vec_make(Int n, Args... args) { auto inner = vec_make(args...); return vector(n, inner); } template auto vec_reserve(Int cap) { vector res; res.reserve(cap); return res; } template auto vec_iota(Int n, T init={}) { vector res(n); ALL(iota, res, init); return res; } template auto vec_scan(ForwardIt first, ForwardIt last, typename iterator_traits::value_type init, BinaryOp op) { using T = typename iterator_traits::value_type; auto res = vec_reserve(distance(first,last)+1); res.emplace_back(init); for(; first != last; ++first) { init = op(move(init), *first); res.emplace_back(init); } return res; } template auto vec_cum(ForwardIt first, ForwardIt last) { using T = typename iterator_traits::value_type; return vec_scan(first, last, T{}, plus<>{}); } template> auto priority_queue_make(const Comp& comp, Cont&& cont={}) { return priority_queue,Comp>(comp, forward(cont)); } template auto priority_queue_reserve(const Comp& comp, Int cap) { return priority_queue,Comp>(comp, vec_reserve(cap)); } template struct ArrayType { using type = array::type,N>; }; template struct ArrayType { using type = array; }; template using Array = typename ArrayType::type; template T& array_at(Array& ary, Int i) { return ary[i]; } template 0 && sizeof...(Args) > 0)> T& array_at(Array& ary, Int i, Args... args) { return array_at(ary[i], args...); } template const T& array_at(const Array& ary, Int i) { return ary[i]; } template 0 && sizeof...(Args) > 0)> const T& array_at(const Array& ary, Int i, Args... args) { return array_at(ary[i], args...); } 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; } // }}} // fixpoint {{{ template class FixPoint { public: explicit constexpr FixPoint(F&& f) : f_(forward(f)) {} template constexpr decltype(auto) operator()(Args&&... args) const { return f_(*this, forward(args)...); } private: F f_; }; template constexpr decltype(auto) FIX(F&& f) { return FixPoint(forward(f)); } template class FixPointMemo { public: explicit FixPointMemo(F&& f) : f_(forward(f)) {} template decltype(auto) operator()(Args... args) const { using R = decltype(f_(*this,args...)); static Array done {}; static Array memo; if(!array_at(done,args...)) { array_at(memo,args...) = f_(*this,args...); array_at(done,args...) = true; } return array_at(memo,args...); } private: F f_; }; template decltype(auto) FIXMEMO(F&& f) { return FixPointMemo(forward(f)); } // }}} // math {{{ /*constexpr*/ Int GCD(Int a, Int b) noexcept { /*constexpr*/ auto f_gcd = FIX([](auto&& self, Int aa, Int bb) -> Int { if(bb == 0) return aa; return self(bb, aa%bb); }); return f_gcd(ABS(a), ABS(b)); } /*constexpr*/ Int LCM(Int a, Int b) noexcept { ASSERT(a != 0 && b != 0); /*constexpr*/ auto f_gcd = FIX([](auto&& self, Int aa, Int bb) -> Int { if(bb == 0) return aa; return self(bb, aa%bb); }); a = ABS(a); b = ABS(b); return a / f_gcd(a,b) * b; } /*constexpr*/ tuple EXTGCD(Int a, Int b) noexcept { /*constexpr*/ auto impl = FIX([](auto&& self, Int aa, Int bb, Int& x, Int& y) -> Int { if(bb == 0) { x = 1; y = 0; return aa; } Int g = self(bb, aa%bb, y, x); y -= (aa/bb)*x; return g; }); Int x{},y{}; Int g = impl(ABS(a), ABS(b), x, y); x *= SGN(a); y *= SGN(b); return make_tuple(g, x, y); } // }}} // string {{{ char chr_digit(Int n) { return char('0'+n); } Int ord_digit(char c) { return c-'0'; } char chr_lower(Int n) { return char('a'+n); } Int ord_lower(char c) { return c-'a'; } char chr_upper(Int n) { return char('A'+n); } Int ord_upper(char c) { return c-'A'; } auto str_reserve(Int cap) { string res; res.reserve(cap); return res; } // }}} // input {{{ template struct Integral1 { static_assert(is_integral::value && !is_same::value, ""); }; using Int1 = Integral1; template struct Scan { using R = T; static R scan(istream& in) { R res; in >> res; return res; } }; template struct Scan> { using R = T; static R scan(istream& in) { return Scan::scan(in) - 1; } }; template struct Scan> { using R1 = typename Scan::R; using R2 = typename Scan::R; using R = pair; static R scan(istream& in) { R1 x = Scan::scan(in); R2 y = Scan::scan(in); return {x,y}; } }; template auto tuple_scan_impl(istream& in) { return make_tuple(Scan::scan(in)); } template 0)> auto tuple_scan_impl(istream& in) { auto head = make_tuple(Scan::scan(in)); return tuple_cat(head, tuple_scan_impl(in)); } template struct Scan> { using R = decltype(tuple_scan_impl(cin)); static R scan(istream& in) { return tuple_scan_impl(in); } }; template auto RD() { return Scan::scan(cin); } template auto RD1() { return RD>(); } template auto RD_VEC(Int n) { auto res = vec_reserve::R>(n); LOOP(n) { res.emplace_back(RD()); } return res; } template auto RD1_VEC(Int n) { return RD_VEC>(n); } template auto RD_VEC2(Int h, Int w) { auto res = vec_reserve::R>>(h); LOOP(h) { res.emplace_back(RD_VEC(w)); } return res; } template auto RD1_VEC2(Int h, Int w) { return RD_VEC2>(h, w); } // }}} // output {{{ template struct Fmt { static void fmt(ostream& out, const T& x) { out << x; } }; template void fmt_write(ostream& out, const T& x) { Fmt::fmt(out, x); } template string FMT_STR(const T& x) { ostringstream out; fmt_write(out, x); return out.str(); } template struct Fmt> { static void fmt(ostream& out, const tuple& t) { tuple_enumerate(t, [&out](Int i, const auto& e) { if(i != 0) out << ' '; fmt_write(out, e); }); } }; template struct Fmt> { static void fmt(ostream& out, const pair& p) { return fmt_write(out, make_tuple(p.first,p.second)); } }; template struct Fmt::value>> { static void fmt(ostream& out, const C& c) { for(auto it = begin(c); it != end(c); ++it) { if(it != begin(c)) out << ' '; fmt_write(out, *it); } } }; void PRINT() {} template void PRINT(const T& x, const TS&... args) { fmt_write(cout, x); if(sizeof...(args) > 0) { cout << ' '; PRINT(args...); } } template void PRINTLN(const TS&... args) { PRINT(args...); cout << '\n'; } // }}} // debug {{{ template struct Dbg { static void dbg(ostream& out, const T& x) { out << x; } }; template void dbg_write(ostream& out, const T& x) { Dbg::dbg(out, x); } template string DBG_STR(const T& x) { ostringstream out; dbg_write(out, x); return out.str(); } template<> struct Dbg { static void dbg(ostream& out, Int x) { if(x == INF) out << "INF"; else if(x == -INF) out << "-INF"; else out << x; } }; template<> struct Dbg { static void dbg(ostream& out, Real x) { if(EQ_EXACT(x, FINF)) out << "FINF"; else if(EQ_EXACT(x, -FINF)) out << "-FINF"; else out << x; } }; template struct Dbg { static void dbg(ostream& out, const T (&ary)[N]) { out << "["; REP(i, N) { if(i != 0) out << ","; dbg_write(out, ary[i]); } out << "]"; } }; template struct Dbg { static void dbg(ostream& out, const char (&s)[N]) { out << s; } }; template struct Dbg> { static void dbg(ostream& out, const tuple& t) { out << "("; tuple_enumerate(t, [&out](Int i, const auto& e) { if(i != 0) out << ","; dbg_write(out, e); }); out << ")"; } }; template struct Dbg> { static void dbg(ostream& out, const pair& p) { return dbg_write(out, make_tuple(p.first,p.second)); } }; template struct Dbg::value>> { static void dbg(ostream& out, const C& c) { out << "["; for(auto it = begin(c); it != end(c); ++it) { if(it != begin(c)) out << ","; dbg_write(out, *it); } out << "]"; } }; template struct Dbg> { static void dbg(ostream& out, stack stk) { out << "["; while(!stk.empty()) { dbg_write(out,stk.top()); stk.pop(); if(!stk.empty()) out << ","; } out << "]"; } }; template struct Dbg> { static void dbg(ostream& out, queue que) { out << "["; while(!que.empty()) { dbg_write(out,que.front()); que.pop(); if(!que.empty()) out << ","; } out << "]"; } }; template struct Dbg> { static void dbg(ostream& out, priority_queue que) { out << "["; while(!que.empty()) { dbg_write(out,que.top()); que.pop(); if(!que.empty()) out << ","; } out << "]"; } }; template void DBG_IMPL(Int line, const char* expr, const T& value) { cerr << "[L " << line << "]: "; cerr << expr << " = "; dbg_write(cerr, value); cerr << "\n"; } void DBG_IMPL_HELPER() {} template void DBG_IMPL_HELPER(const T& x, const TS&... args) { dbg_write(cerr, x); if(sizeof...(args) > 0) { cerr << ","; DBG_IMPL_HELPER(args...); } } template void DBG_IMPL(Int line, const char* expr, const TS&... value) { cerr << "[L " << line << "]: "; cerr << "(" << expr << ") = ("; DBG_IMPL_HELPER(value...); cerr << ")\n"; } template::value == 0)> void DBG_DP_IMPL_HELPER(ostream& out, const T& x, const array&, const array&) { dbg_write(out, x); } template::value > 0)> void DBG_DP_IMPL_HELPER(ostream& out, const T& x, const array& sizes, const array& offs) { Int k = N - rank::value; Int off = offs[k]; Int siz = sizes[k]; if(siz == 0) siz = extent::value - off; out << "["; FOR(i, off, off+siz) { if(i != off) out << ","; DBG_DP_IMPL_HELPER(out, x[i], sizes, offs); } out << "]"; } template::value > 0)> void DBG_DP_IMPL(Int line, const char* expr, const T& dp, const array::value>& sizes={}, const array::value>& offs={}) { cerr << "[L " << line << "]: "; cerr << expr << " = "; DBG_DP_IMPL_HELPER::value>(cerr, dp, sizes, offs); cerr << "\n"; } template void DBG_GRID_IMPL(Int line, const char* expr, const vector& grid) { cerr << "[L " << line << "]: "; cerr << expr << ":\n"; for(const auto& row : grid) { dbg_write(cerr, row); cerr << "\n"; } cerr << "\n"; } #ifdef PROCON_LOCAL #define DBG(args...) DBG_IMPL(__LINE__, CPP_STR_I(args), args) #define DBG_DP(args...) DBG_DP_IMPL(__LINE__, CPP_STR_I(args), args) #define DBG_GRID(args...) DBG_GRID_IMPL(__LINE__, CPP_STR_I(args), args) #else #define DBG(args...) #define DBG_DP(args...) #define DBG_GRID(args...) #endif // }}} // modint {{{ template class ModIntT { private: Int v_; // [0,Mod::value) static Int mod() { return Mod::value; } static Int normalize(Int x) { Int res = x % mod(); if(res < 0) res += mod(); return res; } public: ModIntT() : v_(0) {} ModIntT(Int v) : v_(normalize(v)) {} explicit operator Int() const { return v_; } ModIntT operator-() const { ModIntT res; res.v_ = v_==0 ? 0 : mod()-v_; return res; } ModIntT& operator+=(ModIntT rhs) { v_ += rhs.v_; if(v_ >= mod()) v_ -= mod(); return *this; } ModIntT& operator-=(ModIntT rhs) { v_ -= rhs.v_; if(v_ < 0) v_ += mod(); return *this; } ModIntT& operator*=(ModIntT rhs) { v_ *= rhs.v_; v_ %= mod(); return *this; } ModIntT& operator++() { return *this += 1; } ModIntT& operator--() { return *this -= 1; } ModIntT operator++(int) { return exchange(*this, *this+1); } ModIntT operator--(int) { return exchange(*this, *this-1); } ModIntT pow(Int e) const { return fastpow(*this, e, ModIntT(1)); } ModIntT inv() const { Int g,x; tie(g,x,ignore) = EXTGCD(v_, mod()); ASSERT(g == 1); return ModIntT(x); } friend ModIntT operator+(ModIntT lhs, ModIntT rhs) { return lhs += rhs; } friend ModIntT operator+(ModIntT lhs, Int rhs) { return lhs += rhs; } friend ModIntT operator+(Int lhs, ModIntT rhs) { return ModIntT(lhs) += rhs; } friend ModIntT operator-(ModIntT lhs, ModIntT rhs) { return lhs -= rhs; } friend ModIntT operator-(ModIntT lhs, Int rhs) { return lhs -= rhs; } friend ModIntT operator-(Int lhs, ModIntT rhs) { return ModIntT(lhs) -= rhs; } friend ModIntT operator*(ModIntT lhs, ModIntT rhs) { return lhs *= rhs; } friend ModIntT operator*(ModIntT lhs, Int rhs) { return lhs *= rhs; } friend ModIntT operator*(Int lhs, ModIntT rhs) { return ModIntT(lhs) *= rhs; } friend bool operator==(ModIntT lhs, ModIntT rhs) { return Int(lhs) == Int(rhs); } friend bool operator==(ModIntT lhs, Int rhs) { return lhs == ModIntT(rhs); } friend bool operator==(Int lhs, ModIntT rhs) { return ModIntT(lhs) == rhs; } friend bool operator!=(ModIntT lhs, ModIntT rhs) { return !(lhs == rhs); } friend bool operator!=(ModIntT lhs, Int rhs) { return !(lhs == rhs); } friend bool operator!=(Int lhs, ModIntT rhs) { return !(lhs == rhs); } }; template struct ProconHash> { size_t operator()(ModIntT x) const noexcept { return procon_hash_value(Int(x)); } }; template struct Scan> { using R = ModIntT; static R scan(istream& in) { Int v = Scan::scan(in); return ModIntT(v); } }; template struct Fmt> { static void fmt(ostream& out, ModIntT x) { fmt_write(out, Int(x)); } }; template struct Dbg> { static void dbg(ostream& out, ModIntT x) { dbg_write(out, Int(x)); } }; template using ModIntC = ModIntT>; using ModInt = ModIntC; #define MODINT_DEFINE(alias, mod) \ struct mod { static Int value; }; \ Int mod::value; \ using alias = ModIntT; // }}} // rng {{{ // http://prng.di.unimi.it/xoroshiro128plus.c struct ProconUrbg { using result_type = u64; static constexpr result_type min() { return numeric_limits::min(); } static constexpr result_type max() { return numeric_limits::max(); } ProconUrbg(u64 s0, u64 s1) : state_{s0,s1} {} result_type operator()() { u64 s0 = state_[0]; u64 s1 = state_[1]; u64 res = s0 + s1; s1 ^= s0; state_[0] = ((s0<<24)|(s0>>40)) ^ s1 ^ (s1<<16); state_[1] = (s1<<37)|(s1>>27); return res; } private: u64 state_[2]; }; ProconUrbg& PROCON_URBG() { static u64 s0 = u64(chrono::system_clock::now().time_since_epoch().count()); static u64 s1 = u64(&s0); static ProconUrbg urbg(s0, s1); return urbg; } // }}} // init {{{ struct ProconInit { ProconInit() { cin.tie(nullptr); ios::sync_with_stdio(false); cin.exceptions(ios::failbit | ios::badbit); cout << fixed << setprecision(COUT_PREC); #ifdef PROCON_LOCAL cerr << fixed << setprecision(2); #endif if(COUT_AUTOFLUSH) cout << unitbuf; } } PROCON_INIT; // }}} // }}} //-------------------------------------------------------------------- void solve() { auto A = RD(); auto B = RD(); auto ans = pow(B-A,3) / 6; PRINTLN(ans); } signed main() { Int t = 1; //RD(); LOOP(t) { solve(); } EXIT(); }