// https://github.com/miscalculation53/library #define SINGLE_TESTCASE // #define MULTI_TESTCASE // #define AOJ_TESTCASE #define FAST_IO // #define FAST_CIO // #define INTERACTIVE #define INF 4'000'000'000'000'000'037LL #define EPS 1e-11 #line 30 #include using namespace std; #if __cplusplus > 202002L && defined(__STDCPP_FLOAT128_T__) #include using f128 = std::float128_t; #elif defined(__SIZEOF_FLOAT128__) using f128 = __float128; #else #error "f128 requires a compiler with IEEE binary128 support, such as GCC on x86_64." #endif #define LIBRARY_HAS_FLOAT128 1 #include using namespace std; using ld = decltype(EPS); using ll = long long; using uint = unsigned int; using ull = unsigned long long; using pll = pair; using tlll = tuple; using tllll = tuple; #define vc vector template using vvc = vc>; template using vvvc = vc>>; using vb = vc; using vl = vc; using vpll = vc; using vtlll = vc; using vtllll = vc; using vstr = vc; using vvb = vvc; using vvl = vvc; template using pql = priority_queue, greater>; template using pqg = priority_queue; using i128 = __int128_t; using u128 = __uint128_t; #define cauto const auto #line 103 //! https://gcc.gnu.org/onlinedocs/libquadmath/Math-Library-Routines.html #line 289 i128 stoi128(const string &s) { const bool neg = s.front() == '-'; u128 res = 0; for (size_t i = size_t(neg); i < s.size(); i++) res = 10 * res + unsigned(s[i] - '0'); if (neg) return -i128(res - 1) - 1; return i128(res); } inline string u128tos(u128 x) { string res; do { res += char('0' + x % 10); x /= 10; } while (x > 0); reverse(res.begin(), res.end()); return res; } string i128tos(i128 x) { return x < 0 ? "-" + u128tos(u128(-(x + 1)) + 1) : u128tos(u128(x)); } istream &operator>>(istream &is, i128 &a) { string s; if (!(is >> s)) return is; a = stoi128(s); return is; } ostream &operator<<(ostream &os, const i128 &a) { os << i128tos(a); return os; } #line 337 #define overload4(_1, _2, _3, _4, name, ...) name #define LIBRARY_REPEAT_LOOP(T, i, l, r, d) \ for (auto [i, library_repeat_end, library_repeat_step] = array{T(l), T(r), T(d)}; \ library_repeat_step > 0 ? i < library_repeat_end : i > library_repeat_end; \ i += library_repeat_step) #define rep1(i, n) LIBRARY_REPEAT_LOOP(ll, i, 0, n, 1) #define rep2(i, l, r) LIBRARY_REPEAT_LOOP(ll, i, l, r, 1) #define rep3(i, l, r, d) LIBRARY_REPEAT_LOOP(ll, i, l, r, d) #define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define repi1(i, n) LIBRARY_REPEAT_LOOP(int, i, 0, n, 1) #define repi2(i, l, r) LIBRARY_REPEAT_LOOP(int, i, l, r, 1) #define repi3(i, l, r, d) LIBRARY_REPEAT_LOOP(int, i, l, r, d) #define repi(...) overload4(__VA_ARGS__, repi3, repi2, repi1)(__VA_ARGS__) #define fe(...) for (auto __VA_ARGS__) #define fec(...) for (cauto &__VA_ARGS__) #define fem(...) for (auto &__VA_ARGS__) #line 408 template constexpr pair &operator+=(pair &a, const P &b) { a.first += b.first; a.second += b.second; return a; } template constexpr pair operator+(pair a, const P &b) { return a += b; } template constexpr pair &operator-=(pair &a, const P &b) { a.first -= b.first; a.second -= b.second; return a; } template constexpr pair operator-(pair a, const P &b) { return a -= b; } template constexpr pair operator-(pair a) { a.first = -a.first; a.second = -a.second; return a; } template constexpr array &operator+=(array &a, const A &b) { for (size_t i = 0; i < n; i++) a[i] += b[i]; return a; } template constexpr array operator+(array a, const A &b) { return a += b; } template constexpr array &operator-=(array &a, const A &b) { for (size_t i = 0; i < n; i++) a[i] -= b[i]; return a; } template constexpr array operator-(array a, const A &b) { return a -= b; } template constexpr array operator-(array a) { for (auto &ai : a) ai = -ai; return a; } namespace internal { template constexpr auto &tuple_add_impl(A &a, const B &b, const index_sequence) ; template constexpr auto &tuple_sub_impl(A &a, const B &b, const index_sequence) ; template constexpr auto &tuple_neg_impl(A &a, const index_sequence) ; }; template constexpr tuple &operator+=(tuple &a, const Tp &b) { return internal::tuple_add_impl(a, b, make_index_sequence>>{}); } template constexpr tuple operator+(tuple a, const Tp &b) { return a += b; } template constexpr tuple &operator-=(tuple &a, const Tp &b) { return internal::tuple_sub_impl(a, b, make_index_sequence>>{}); } template constexpr tuple operator-(tuple a, const Tp &b) { return a -= b; } template constexpr tuple operator-(tuple a) { internal::tuple_neg_impl(a, make_index_sequence{}); return a; } #line 512 template constexpr bool is_integral_ext = is_integral_v || is_same_v || is_same_v; template constexpr bool is_signed_ext = is_signed_v || is_same_v; template constexpr bool is_unsigned_ext = is_unsigned_v || is_same_v; #line 531 template struct make_unsigned_ext { using type = make_unsigned_t; }; template <> struct make_unsigned_ext { using type = u128; }; template <> struct make_unsigned_ext { using type = u128; }; template using make_unsigned_ext_t = typename make_unsigned_ext::type; template struct make_signed_ext { using type = make_signed_t; }; template <> struct make_signed_ext { using type = i128; }; template using make_signed_ext_t = typename make_signed_ext::type; template constexpr bool is_negative(T x) { static_assert(is_integral_ext); if constexpr (is_signed_ext) return x < 0; return false; } template constexpr make_unsigned_ext_t unsigned_abs(T x) ; template > struct unsigned_arithmetic { using type = T; }; template struct unsigned_arithmetic { static_assert(!is_same_v); using type = common_type_t>; }; template using unsigned_arithmetic_t = typename unsigned_arithmetic::type; template constexpr R wrapping_cast(T x) ; #line 625 template constexpr decltype(auto) default_infty(); namespace default_infty_detail { template struct is_product : false_type {}; template struct is_product> : true_type {}; template struct is_product> : true_type {}; template struct is_product> : true_type {}; template constexpr T product_value(index_sequence) ; template struct has_infty : false_type {}; template struct has_infty> : true_type {}; template const T &custom_value() ; template inline constexpr bool unsupported = false; } template constexpr decltype(auto) default_infty() ; #line 696 template inline bool chmin(T &a, U b) ; template inline bool chmax(T &a, U b) ; template || is_same_v, int> = 0> inline constexpr T abs(T x) ; namespace template_math_detail { template constexpr common_type_t gcd(T a, U b) ; #line 720 template constexpr common_type_t lcm(T a, U b) ; } template && !is_same_v, int> = 0> constexpr common_type_t gcd(i128 a, T b) ; template && !is_same_v && !is_same_v && !is_same_v, int> = 0> constexpr common_type_t gcd(T a, i128 b) ; template && !is_same_v, int> = 0> constexpr common_type_t gcd(u128 a, T b) ; template && !is_same_v && !is_same_v && !is_same_v, int> = 0> constexpr common_type_t gcd(T a, u128 b) ; template && !is_same_v, int> = 0> constexpr common_type_t lcm(i128 a, T b) ; template && !is_same_v && !is_same_v && !is_same_v, int> = 0> constexpr common_type_t lcm(T a, i128 b) ; template && !is_same_v, int> = 0> constexpr common_type_t lcm(u128 a, T b) ; template && !is_same_v && !is_same_v && !is_same_v, int> = 0> constexpr common_type_t lcm(T a, u128 b) ; template && is_integral_ext>> inline constexpr T divfloor(U a, V b) ; template && is_integral_ext>> inline constexpr T divceil(U a, V b) ; template && is_integral_ext>> inline constexpr T safemod(U a, V b) { const T x = T(a), y = T(b); if constexpr (is_signed_ext) if (y == T(-1)) return T(0); const T r = x % y; return r != T(0) && is_negative(x) != is_negative(y) ? T(r + y) : r; } template constexpr T ipow(U a, V b) ; #line 791 template T mul_limited(A a, B b, M m) ; template T mul_limited(A a, B b) ; template T pow_limited(A a, B b, M m) ; #line 826 template T pow_limited(A a, B b) ; template constexpr T iroot(A a, K k) ; #line 885 template constexpr T iroot_ceil(A a, K k) ; //! https://misawa.github.io/others/avoid_errors/techniques_to_avoid_errors.html template int SGN(A a, D eps = EPS) ; template vc base_repr(U val, V base) ; #line 915 template vc base_repr(U val, V base, int n) ; #line 930 template string base_repr_str(U val, int base) ; template string base_repr_str(U val, int base, int n) ; #line 963 #define ALL(a) (a).begin(), (a).end() template inline T SZ(const V &x) { return x.size(); } #define eb emplace_back #define LMD(x, fx) ([&](const auto &x) { return fx; }) template auto gen_vec(int n, const F &f) { assert(n >= 0); vc res; res.reserve(n); repi(i, n) res.eb(f(i)); return res; } #define GEN_VEC(n, i, fi) (gen_vec(n, LMD(i, fi))) namespace template_vector_detail { template struct nested_vector { using type = vc::type>; }; template struct nested_vector { using type = T; }; template void populate_dimensions(typename nested_vector::type &result, const V *sizes, const T &init) ; #line 1008 template typename nested_vector::type build_dimensions(const V *sizes, const T &init) ; } template auto dvec(const V (&sz)[d], const T &init) ; template auto dvec(const ll (&sz)[d], const T &init) ; template void fill(V &v, const T &value) { if constexpr (is_assignable_v) std::fill(std::begin(v), std::end(v), value); else for (auto &row : v) fill(row, value); } template optional ctol(const char &c, const string &s) ; template vc stov(const string &s, char first) { return gen_vec(SZ(s), [&](int i) -> T { return s[i] - first; }); } template optional> stov(const string &s, const string &t) ; template string vtos(const vc &v, char first) ; template string vtos(const vc &v, const string &t) ; template vc concat(const vvc &vs) ; template vc concat(const vc &v) ; template vc concat(vc v, const vc &...vs) ; template vc merged(const vc &a, const vc &b) ; template T vecget(const vc &v, I i, const T &dflt_negative = -default_infty(), const T &dflt_positive = default_infty()) ; #line 1134 template , int> = 0> constexpr T resolved_value() ; template , long> = 0> const T &resolved_value() ; template constexpr decltype(auto) resolved_infty() ; #line 1170 namespace internal { template struct HasMonoidPow : false_type {}; template struct HasMonoidPow(), declval()))>> : true_type {}; } namespace internal_monoid_power { template constexpr void check_exponent(I k) ; template constexpr typename M::S binary_inplace(typename M::S &x, I k) ; template constexpr typename M::S binary(typename M::S x, I k) ; } template constexpr typename M::S pow_monoid(typename M::S x, I k) ; template constexpr typename G::S pow_group(typename G::S x, I k) ; #line 1238 template auto SUM(const V &v) ; template T SUM(const V &v) ; template auto MAX(const V &v) ; template auto MIN(const V &v) ; template optional ARGMAX(const V &v) ; template optional ARGMIN(const V &v) ; template T mex(const V &a) ; template bool is_permutation(const vc &p) ; #line 1295 template vc permid(const int &n, const int &base_index = 0) ; template vc perminv(const vc &p) ; template vc permuted(const vc &a, const vc &p) ; template vc permuted(const vc &p, const vc &q, const vc &...rs) ; template V reversed(const V &v) ; template V sorted(V v, Args&&... args) ; template > void unique(V &v, Equal equal = {}) { v.erase(std::unique(ALL(v), equal), v.end()); } template > V uniqued(V v, Equal equal = {}) ; template , class Equal = equal_to<>> void sortunique(V &v, Compare comp = {}, Equal equal = {}) ; template , class Equal = equal_to<>> V sortuniqued(V v, Compare comp = {}, Equal equal = {}) ; template void rotate(V &v, U k) ; template V rotated(V v, U k) ; template vvc top(const vvc &a) { if (a.empty()) return {}; const int n = a.size(), m = a[0].size(); vvc b(m, vc(n)); repi(i, n) { assert(SZ(a[i]) == m); repi(j, m) b[j][i] = a[i][j]; } return b; } vstr top(const vstr &a) { vvc a_(a.size()); repi(i, SZ(a)) a_[i] = {ALL(a[i])}; vvc b_ = top(a_); vstr b(b_.size()); repi(i, SZ(b)) b[i] = {ALL(b_[i])}; return b; } template struct has_e0 : false_type {}; template struct has_e0> : true_type {}; template inline constexpr bool has_e0_v = has_e0::value; template struct MonoidAdd { using S = T; static constexpr S op(S a, S b) { return a + b; } static constexpr S e() { if constexpr (has_e0_v) return S::e0(); else return {}; } template () * declval())> static constexpr S pow(const S &a, I k) { return a * k; } }; template struct MonoidMin { using S = T; static constexpr S op(S a, S b) { return min(a, b); } static constexpr decltype(auto) e() { return resolved_infty(); } template static constexpr S pow(const S &a, I k) { return k == 0 ? e() : a; } }; template struct MonoidMax { using S = T; static constexpr S op(S a, S b) { return max(a, b); } static constexpr S e() { return -resolved_infty(); } template static constexpr S pow(const S &a, I k) { return k == 0 ? e() : a; } }; template vc cuml(const vc &v, int left_index = 0) ; template vc cumr(const vc &v, int right_index = 0) ; template vc cumlsum(const vc &v, int left_index = 0) ; template vc cumrsum(const vc &v, int right_index = 0) ; template vc cumlmin(const vc &v, int left_index = 0) ; template vc cumrmin(const vc &v, int right_index = 0) ; template vc cumlmax(const vc &v, int left_index = 0) ; template vc cumrmax(const vc &v, int right_index = 0) ; template vc adjd(const vc &v, int left_index = 0, int right_index = 0) ; #line 1504 constexpr array DRULgrid = {{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}}; constexpr array DRULplane = {{{0, -1}, {1, 0}, {0, 1}, {-1, 0}}}; template struct is_random_access_iterator { static constexpr bool value = is_same_v< typename iterator_traits::iterator_category, random_access_iterator_tag >; }; template constexpr bool is_random_access_iterator_v = is_random_access_iterator::value; #line 1569 template inline T LB(const V &v, const Value &val, Comp comp = {}, Proj proj = {}) ; template inline T UB(const V &v, const Value &val, Comp comp = {}, Proj proj = {}) ; #define DEFAULT_COMP ranges::less template inline auto lt_max(const V &v, const Value &val, Comp comp = {}, Proj proj = {}) -> enable_if_t, T> ; template inline auto leq_max(const V &v, const Value &val, Comp comp = {}, Proj proj = {}) -> enable_if_t, T> ; template inline auto gt_min(const V &v, const Value &val, Comp comp = {}, Proj proj = {}) -> enable_if_t, T> ; template inline auto geq_min(const V &v, const Value &val, Comp comp = {}, Proj proj = {}) -> enable_if_t, T> ; template inline auto lt_cnt(const V &v, const Value &val, Comp comp = {}, Proj proj = {}) -> enable_if_t, T> ; template inline auto leq_cnt(const V &v, const Value &val, Comp comp = {}, Proj proj = {}) -> enable_if_t, T> ; template inline auto gt_cnt(const V &v, const Value &val, Comp comp = {}, Proj proj = {}) -> enable_if_t, T> ; template inline auto geq_cnt(const V &v, const Value &val, Comp comp = {}, Proj proj = {}) -> enable_if_t, T> ; template inline auto in_cnt(const V &v, L l, R r, Comp comp = {}, Proj proj = {}) -> enable_if_t, T> ; template inline auto lt_max(const V &v, const Value &val) -> enable_if_t, optional> ; template inline auto leq_max(const V &v, const Value &val) -> enable_if_t, optional> ; template inline auto gt_min(const V &v, const Value &val) -> enable_if_t, optional> ; template inline auto geq_min(const V &v, const Value &val) -> enable_if_t, optional> ; namespace internal { template bool binsearch_adjacent(T a, T b) ; }; template pair binsearch(const Judge &judge, InitOk init_ok, InitNg init_ng, bool check_ok = true, bool check_ng = true) ; #line 1707 template T binsearch_real(const Judge &judge, InitOk init_ok, InitNg init_ng, int iteration_count = 100, bool check_ok = true, bool check_ng = true) ; #line 1723 template pair expsearch(const Judge &judge, InitVal init_val, bool positive = true) ; #line 1769 template inline constexpr ull pow2(T k) ; template inline constexpr ull MASK(T k) { return (1ULL << k) - 1ULL; } #line 1787 inline constexpr ll bit_width(ll x) { return std::bit_width((ull)x); } inline constexpr ll bit_floor(ll x) { return std::bit_floor((ull)x); } inline constexpr ll bit_ceil(ll x) { return std::bit_ceil((ull)x); } inline constexpr ll countr_zero(ll x) { assert(x != 0); return std::countr_zero((ull)x); } inline constexpr ll popcount(ll x) { return std::popcount((ull)x); } inline constexpr bool has_single_bit(ll x) { return std::has_single_bit((ull)x); } inline constexpr ull lsb_pos(ull x) { assert(x != 0); return countr_zero(x); } inline constexpr ull msb_pos(ull x) { assert(x != 0); return bit_width(x) - 1; } inline constexpr ull lsb_mask(ull x) { assert(x != 0); return x & -x; } inline constexpr ull msb_mask(ull x) { assert(x != 0); return bit_floor(x); } inline constexpr bool btest(ull x, uint k) { return (x >> k) & 1; } template inline void bset(T &x, uint k, bool b = 1) ; template inline void bflip(T &x, uint k) ; inline constexpr bool bsubset(ull x, ull y) { return (x & y) == x; } inline constexpr bool bsupset(ull x, ull y) { return (x & y) == y; } inline constexpr ull bsetminus(ull x, ull y) { return x & ~y; } #line 1912 #define CPP_DUMP_DEFINE_DATA(...) #define dump(...) ((void)0) #define local(...) #define oj(...) __VA_ARGS__ #define local_oj(a, b) (b) template vc content(queue que) { vc res; while (!que.empty()) { res.eb(que.front()); que.pop(); } return res; } template vc content(priority_queue pque) { vc res; while (!pque.empty()) { res.eb(pque.top()); pque.pop(); } return res; } template auto content(const T &obj) { return obj.content(); } #line 1977 namespace fastio { constexpr uint32_t SIZ = 1 << 17; inline char ibuf[SIZ + 1], obuf[SIZ]; inline uint32_t pil = 0, pir = 0, por = 0; __attribute__((noinline)) inline void load() { const uint32_t remaining = pir - pil; if (remaining && pil) memmove(ibuf, ibuf + pil, remaining); pil = 0; pir = remaining + uint32_t(fread(ibuf + remaining, 1, SIZ - remaining, stdin)); ibuf[pir] = '\x7f'; } inline bool ascii_space(unsigned char c) { return c == ' ' || unsigned(c - '\t') < 5; } inline void find_token() { for (;;) { const char *p = ibuf + pil; const char *end = ibuf + pir; while (ascii_space(*p)) ++p; pil = uint32_t(p - ibuf); if (p != end) return; load(); if (!pir) abort(); } } __attribute__((noinline)) inline void flush() { size_t written = 0; while (written < por) { const size_t n = fwrite(obuf + written, 1, por - written, stdout); if (!n) abort(); written += n; } por = 0; } inline void append_bytes(const char *data, size_t size) { while (size) { const size_t n = min(size, size_t(SIZ - por)); memcpy(obuf + por, data, n); por += uint32_t(n); data += n; size -= n; if (por == SIZ) flush(); } } inline void append_char(char c) { if (por == SIZ) flush(); obuf[por++] = c; } template using integer_magnitude = conditional_t<(sizeof(T) > sizeof(ull)), u128, conditional_t<(sizeof(T) > sizeof(uint)), ull, uint>>; inline uint decode_eight(uint64_t columns) { columns &= 0x0f0f0f0f0f0f0f0fULL; const uint64_t pairs = (columns & 0x00ff00ff00ff00ffULL) * 10 + ((columns >> 8) & 0x00ff00ff00ff00ffULL); const uint64_t quads = (pairs & 0x0000ffff0000ffffULL) * 100 + ((pairs >> 16) & 0x0000ffff0000ffffULL); return uint(quads) * 10000 + uint(quads >> 32); } inline constexpr uint powers_of_ten[8] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000}; template __attribute__((always_inline)) inline void read_wide_integer_tail( U &value, const char *&p, uint64_t columns, uint64_t stop) ; #line 2078 template __attribute__((always_inline)) inline void rd1_integer(T &x) { using U = integer_magnitude; const char *p = ibuf + pil; for (;;) { while (ascii_space(*p)) ++p; if (p != ibuf + pir) break; pil = pir; load(); if (!pir) abort(); p = ibuf; } bool negative = false; if (*p == '+') ++p; else if constexpr (numeric_limits::is_signed) { if (*p == '-') negative = true, ++p; } U value = 0; for (;;) { while (size_t(ibuf + pir - p) >= 8) { uint64_t columns; memcpy(&columns, p, 8); const uint64_t stop = ((columns + 0x4646464646464646ULL) | (columns - 0x3030303030303030ULL)) & 0x8080808080808080ULL; if (stop) { if constexpr (sizeof(U) > sizeof(ull)) { read_wide_integer_tail(value, p, columns, stop); goto integer_complete; } else { if (stop & 0x80808080ULL) { if (!(stop & 0x808080ULL)) { value = value * 1000 + uint(columns & 15) * 100 + uint(columns >> 8 & 15) * 10 + uint(columns >> 16 & 15); p += 3; } else if (!(stop & 0x8080ULL)) { value = value * 100 + uint(columns & 15) * 10 + uint(columns >> 8 & 15); p += 2; } else if (!(stop & 0x80ULL)) { value = value * 10 + uint(columns & 15); ++p; } goto integer_complete; } break; } } columns &= 0x0f0f0f0f0f0f0f0fULL; const uint64_t pairs = (columns & 0x00ff00ff00ff00ffULL) * 10 + ((columns >> 8) & 0x00ff00ff00ff00ffULL); const uint64_t quads = (pairs & 0x0000ffff0000ffffULL) * 100 + ((pairs >> 16) & 0x0000ffff0000ffffULL); value = value * 100000000 + uint(quads) * 10000 + uint(quads >> 32); p += 8; } while (unsigned(*p - '0') < 10) { value = value * 10 + unsigned(*p - '0'); ++p; } pil = uint32_t(p - ibuf); if (pil != pir) break; load(); p = ibuf; if (!pir) break; } integer_complete: pil = uint32_t(p - ibuf); if constexpr (numeric_limits::is_signed) { if (negative && value) x = T(-T(value - 1) - 1); else x = T(value); } else x = T(value); } template ::is_integer, int> = 0> __attribute__((always_inline)) inline void rd1(T &x) { rd1_integer(x); } inline void rd1(char &x) ; inline void rd1(string &x) { find_token(); x.clear(); for (;;) { const char *p = ibuf + pil; const char *end = ibuf + pir; const char *first = p; while (p != end && !ascii_space(*p)) ++p; x.append(first, size_t(p - first)); pil = uint32_t(p - ibuf); if (p != end) return; load(); if (!pir) return; } } template void rd1_real(T &x) { string token; rd1(token); const char *first = token.data(); const char *last = first + token.size(); if (first != last && *first == '+') ++first; auto result = from_chars(first, last, x, chars_format::general); if (result.ec != errc{} || result.ptr != last) { char *end; if constexpr (is_same_v) x = strtof(token.c_str(), &end); else if constexpr (is_same_v) x = strtod(token.c_str(), &end); else x = strtold(token.c_str(), &end); if (end != token.data() + token.size()) abort(); } } inline void rd1(float &x) ; inline void rd1(double &x) ; inline void rd1(long double &x) ; template void rd1(pair &x); template void rd1(tuple &x); template void rd1(array &x); template void rd1(vc &x); template void rd1(pair &x) ; template void rd1(tuple &x) ; template void rd1(array &x) ; template void rd1(vc &x) ; inline constexpr auto decimal_triplets = [] { array, 1000> result{}; for (unsigned i = 0; i < 1000; ++i) { result[i][0] = char('0' + i / 100); result[i][1] = char('0' + i / 10 % 10); result[i][2] = char('0' + i % 10); } return result; }(); inline void store_nine(char *out, uint x) { const uint q = x / 1000, r = q / 1000; memcpy(out, decimal_triplets[r].data(), 3); memcpy(out + 3, decimal_triplets[q - r * 1000].data(), 3); memcpy(out + 6, decimal_triplets[x - q * 1000].data(), 3); } inline char *prepend_small(char *end, uint x) { while (x >= 1000) { const uint q = x / 1000; end -= 3; memcpy(end, decimal_triplets[x - q * 1000].data(), 3); x = q; } const unsigned digits = 1 + unsigned(x >= 10) + unsigned(x >= 100); end -= digits; memcpy(end, decimal_triplets[x].data() + 3 - digits, digits); return end; } inline char *prepend_wide(char *end, ull x) { while (x >= 1000000000ULL) { const ull q = x / 1000000000ULL; end -= 9; store_nine(end, uint(x - q * 1000000000ULL)); x = q; } return prepend_small(end, uint(x)); } inline char *store_leading_triplet(char *out, uint x) { if (x >= 100) { memcpy(out, decimal_triplets[x].data(), 3); return out + 3; } if (x >= 10) { memcpy(out, decimal_triplets[x].data() + 1, 2); return out + 2; } *out = char('0' + x); return out + 1; } inline char *store_short(char *out, uint x) { if (x >= 1000000) { const uint q = x / 1000000; const uint r = x - q * 1000000; out = store_leading_triplet(out, q); memcpy(out, decimal_triplets[r / 1000].data(), 3); memcpy(out + 3, decimal_triplets[r % 1000].data(), 3); return out + 6; } if (x >= 1000) { const uint q = x / 1000; out = store_leading_triplet(out, q); memcpy(out, decimal_triplets[x - q * 1000].data(), 3); return out + 3; } return store_leading_triplet(out, x); } template inline char *store_ordinary(char *out, U x) { if constexpr (sizeof(U) > sizeof(uint)) { if (x >= 1000000000000000000ULL) { const uint hi = uint(x / 1000000000000000000ULL); const ull tail = x - ull(hi) * 1000000000000000000ULL; const uint middle = uint(tail / 1000000000ULL); out = store_leading_triplet(out, hi); store_nine(out, middle); store_nine(out + 9, uint(tail - ull(middle) * 1000000000ULL)); return out + 18; } } if (x >= 1000000000) { const uint hi = uint(x / 1000000000); out = store_short(out, hi); store_nine(out, uint(x - U(hi) * 1000000000)); return out + 9; } return store_short(out, uint(x)); } template __attribute__((always_inline)) inline void write_wide_integer(U magnitude, bool negative) ; #line 2386 template __attribute__((always_inline)) inline void wt1_integer(T x) { using U = integer_magnitude; U magnitude = U(x); bool negative = false; if constexpr (numeric_limits::is_signed) { negative = x < 0; const U sign_mask = U(0) - U(negative); magnitude = (magnitude ^ sign_mask) + U(negative); } if constexpr (sizeof(U) <= sizeof(ull)) { if (por > SIZ - 40) flush(); char *out = obuf + por; *out = '-'; out += negative; out = store_ordinary(out, magnitude); if constexpr (newline) *out++ = '\n'; por = uint32_t(out - obuf); return; } else write_wide_integer(magnitude, negative); } template ::is_integer, int> = 0> __attribute__((always_inline)) inline void wt1(T x) { wt1_integer(x); } inline void wt1(char x) ; inline void wt1(const char *x) ; inline void wt1(string_view x) ; inline void wt1(const string &x) ; template void wt1_real(T x) { char text[numeric_limits::max_exponent10 + 64]; auto result = to_chars(text, text + sizeof(text), x, chars_format::fixed, 15); if (result.ec != errc{}) abort(); append_bytes(text, size_t(result.ptr - text)); } inline void wt1(float x) ; inline void wt1(double x) ; inline void wt1(long double x) ; template void wt1(const pair &x); template void wt1(const tuple &x); template void wt1(const array &x); template void wt1(const vc &x); template void wt1(const pair &x) ; template void wt1(const tuple &x) ; template void wt1(const array &x) ; template void wt1(const vc &x) ; template void read(T &...x) { (rd1(x), ...); } template void write(T &&...x) { (wt1(forward(x)), ...); } template void print(T &&...x) { if constexpr (sizeof...(T) == 1 && ((is_integral_v> && !is_same_v, char>) && ...)) (wt1_integer, true>(forward(x)), ...); else { size_t index = 0; ((index++ ? void(append_char(' ')) : void(), wt1(forward(x))), ...); append_char('\n'); } } } struct Dummy { Dummy() { atexit(fastio::flush); } } dummy; //! https://trap.jp/post/1224/ #line 2532 namespace internal { template void READnodump(Ts &...a) { fastio::read(a...); } template void READVECnodump(int n, vc &...v) ; template void READVEC2nodump(int n, int m, vvc &...v) ; template void READJAGnodump(int n, vvc &...vs) ; #line 2579 }; #define READ(...) internal::READnodump(__VA_ARGS__); dump(__VA_ARGS__) #define LIBRARY_INOUT_TYPE(...) LIBRARY_INOUT_TYPE_IMPL(__VA_ARGS__)(__VA_ARGS__) #define LIBRARY_INOUT_TYPE_IMPL(T, ...) LIBRARY_INOUT_TYPE_SELECT(LIBRARY_INOUT_TYPE_PROBE T, LIBRARY_INOUT_TYPE_KEEP) #define LIBRARY_INOUT_TYPE_PROBE(...) _, LIBRARY_INOUT_TYPE_REMOVE #define LIBRARY_INOUT_TYPE_SELECT(...) LIBRARY_INOUT_TYPE_SECOND(__VA_ARGS__) #define LIBRARY_INOUT_TYPE_SECOND(_0, _1, ...) _1 #define LIBRARY_INOUT_TYPE_KEEP(...) __VA_ARGS__ #define LIBRARY_INOUT_TYPE_REMOVE(T) LIBRARY_INOUT_TYPE_KEEP T #define IN(T, ...) LIBRARY_INOUT_TYPE(T) __VA_ARGS__; READ(__VA_ARGS__) #define CHAR(...) IN(char, __VA_ARGS__) #define INT(...) IN(int, __VA_ARGS__) #define LL(...) IN(ll, __VA_ARGS__) #define STR(...) IN(string, __VA_ARGS__) #define ARR(T, n, ...) array __VA_ARGS__; READ(__VA_ARGS__) #define READVEC(...) internal::READVECnodump(__VA_ARGS__); dump(__VA_ARGS__) #define READVEC2(...) internal::READVEC2nodump(__VA_ARGS__); dump(__VA_ARGS__) #define VEC(T, n, ...) vc __VA_ARGS__; READVEC(n, __VA_ARGS__) #define VEC2(T, n, m, ...) vvc __VA_ARGS__; READVEC2(n, m, __VA_ARGS__) #define READJAG(...) internal::READJAGnodump(__VA_ARGS__); dump(__VA_ARGS__) #define JAG(T, n, ...) vvc __VA_ARGS__; READJAG(n, __VA_ARGS__) #define ENDL '\n' #line 2688 #define WRITE fastio::write #define PRINT fastio::print #define PRINTEXIT(...) do { PRINT(__VA_ARGS__); exit(0); } while (false) #define PRINTRETURN(...) do { PRINT(__VA_ARGS__); return; } while (false) template void PRINTV(const vc &v) ; #define PRINTVEXIT(...) do { PRINTV(__VA_ARGS__); exit(0); } while (false) #define PRINTVRETURN(...) do { PRINTV(__VA_ARGS__); return; } while (false) template void offset(vc &v, const Add &add) ; template void offset(vvc &v, const Add &add) ; template array, m> unzip(const vc> &vt) ; template vc> zip(const array, m> &tv) ; #line 2737 template pair, vc> unzip(const vc> &vt) ; template vc> zip(const pair, vc> &tv) ; namespace internal { template auto vt_to_tv_impl(V &tv, const Tp &t, index_sequence, size_t index) ; template auto tv_to_vt_impl(const Tp &tv, index_sequence, size_t index) ; }; template auto unzip(const vc> &vt) ; template auto zip(const tuple...> &tv) ; namespace internal { template auto zip_vectors(const vc &...v) ; }; #define UNZIP(vt, ...) auto [__VA_ARGS__] = unzip(vt) #define ZIP(vt, ...) auto vt = internal::zip_vectors(__VA_ARGS__) mt19937_64 mt; template T randint(U1 l, U2 r) ; template T randrange(U1 l, U2 r) ; template T randreal(U1 l, U2 r) ; bool randbool(double p) { assert(0 <= p && p <= 1); return bernoulli_distribution(p)(mt); } namespace internal { template void random_sample_range(V &res, T l, T r) ; #line 2888 }; template array random_sample_range_array(U1 l, U2 r) ; template vc random_sample_range_vector(U1 l, U2 r, int k) ; #line 2917 /*! * Portions corresponding to AtCoder Library (CC0-1.0): modular arithmetic operators. * Upstream: atcoder/modint.hpp * https://github.com/atcoder/ac-library/tree/864245a00b00dd008d1abfdc239618fdb7d139da * License: https://github.com/atcoder/ac-library/blob/864245a00b00dd008d1abfdc239618fdb7d139da/LICENSE */ #line 2936 namespace larger_int_detail { template [[deprecated("larger_int: 128-bit integer is not widened; intermediate arithmetic may overflow")]] constexpr bool warn_no_wider_integer() { return true; } } template struct larger_int { private: static constexpr bool check() ; static_assert(check()); public: using type = T; }; #define LARGER_INT(T, U) \ template <> \ struct larger_int \ { \ using type = U; \ }; LARGER_INT(signed char, short) LARGER_INT(short, int) LARGER_INT(int, long long) LARGER_INT(long, __int128_t) LARGER_INT(long long, __int128_t) LARGER_INT(unsigned char, unsigned short) LARGER_INT(unsigned short, unsigned int) LARGER_INT(unsigned int, unsigned long long) LARGER_INT(unsigned long, __uint128_t) LARGER_INT(unsigned long long, __uint128_t) #undef LARGER_INT template struct Rational; template struct larger_int> { using type = Rational::type>; }; template using larger_int_t = typename larger_int::type; /*! * Portions corresponding to AtCoder Library (CC0-1.0): primality testing. * Upstream: atcoder/internal_math.hpp * https://github.com/atcoder/ac-library/tree/864245a00b00dd008d1abfdc239618fdb7d139da * License: https://github.com/atcoder/ac-library/blob/864245a00b00dd008d1abfdc239618fdb7d139da/LICENSE */ namespace internal { template constexpr ll powmod_constexpr(ll x, ll n, T m) { if (m == 1) return 0; using U = make_unsigned_t; using L = larger_int_t; U r = 1, y = safemod(x, m); while (n) { if (n & 1) r = L(r) * y % m; y = L(y) * y % m; n >>= 1; } return r; } template constexpr bool isprime_constexpr(T n) { if constexpr (sizeof(T) > 4) { if (n <= INT_MAX) return isprime_constexpr(n); } if (n <= 1) return false; if (n == 2 || n == 7 || n == 61) return true; if (n % 2 == 0) return false; ll d = n - 1; while (d % 2 == 0) d /= 2; using U = make_unsigned_t; using L = larger_int_t; auto miller_rabin = [&](const auto &bases) constexpr { for (ll a : bases) { ll t = d, y = powmod_constexpr(a, t, n); while (t != n - 1 && y != 1 && y != n - 1) { y = L(y) * y % n; t <<= 1; } if (y != n - 1 && t % 2 == 0) return false; } return true; }; if constexpr(sizeof(T) <= 4) { constexpr ll bases[3] = {2, 7, 61}; return miller_rabin(bases); } else { constexpr ll bases[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; return miller_rabin(bases); } } template constexpr bool isprime = isprime_constexpr(n); }; namespace internal { template struct policy_static { using mod_type = decltype(M); using value_type = make_unsigned_t; using calc_type = conditional_t<(M <= UINT_MAX), ull, larger_int_t>; static constexpr bool is_prime = isprime_constexpr(M); static constexpr mod_type mod() { return M; } static constexpr value_type umod() { return M; } static constexpr value_type init(value_type v) { return v; } static constexpr mod_type val(value_type v) { return v; } static constexpr value_type mul(value_type a, value_type b) { const calc_type product = calc_type(a) * b; if constexpr (M == (1LL << 61) - 1) { const value_type reduced = (value_type(product) & umod()) + value_type(product >> 61); return reduced >= umod() ? reduced - umod() : reduced; } else return value_type(product % M); } }; }; /*! * Portions corresponding to AtCoder Library (CC0-1.0): Barrett reduction. * Upstream: atcoder/internal_math.hpp * https://github.com/atcoder/ac-library/tree/864245a00b00dd008d1abfdc239618fdb7d139da * License: https://github.com/atcoder/ac-library/blob/864245a00b00dd008d1abfdc239618fdb7d139da/LICENSE */ namespace internal { struct barrett32 { uint m = 0; ull im = 0; barrett32() = default; explicit barrett32(uint m) : m(m), im((ull)(-1) / m + 1) {} uint umod() const ; uint mul(uint a, uint b) const ; }; template struct policy_barrett32 { using value_type = uint; using calc_type = ull; using mod_type = int; static constexpr bool is_prime = false; static inline barrett32 reducer{}; static void set_mod(mod_type m) ; static mod_type mod() ; static value_type umod() ; static value_type init(value_type v) { return v; } static mod_type val(value_type v) ; static value_type mul(value_type a, value_type b) ; }; }; namespace internal { inline constexpr ull inv64(ull a) { ull x = a; while (a * x != 1) x *= 2 - a * x; return x; } struct montgomery64odd { ull m = 0, im = 0, sq = 0; montgomery64odd() = default; explicit montgomery64odd(ull m) : m(m), im(inv64(m)), sq(-u128(m) % m) {} ull umod() const ; ull reduce(u128 x) const ; ull inv_reduce(i128 v) const ; }; //! https://www.mathenachia.blog/even-mod-montgomery-impl/ struct montgomery64 { ull m = 0, mx = 0, imx = 0, d = 0, q = 0; uint b = 0; montgomery64() = default; explicit montgomery64(ull m) : m(m) { b = countr_zero(m), mx = m >> b; imx = inv64(mx); d = powmod_constexpr((mx + 1) / 2, b, mx); u128 sq = -u128(mx) % mx; q = (1 + (((sq - 1) * d) << b)) % m; } ull umod() const ; ull reduce(u128 x) const ; #line 3229 ull inv_reduce(i128 v) const ; }; template struct policy_montgomery64_odd { using value_type = ull; using calc_type = u128; using mod_type = ll; static constexpr bool is_prime = false; static inline montgomery64odd reducer{}; static void set_mod(mod_type m) ; static mod_type mod() ; static value_type umod() ; static value_type init(value_type v) { return reducer.inv_reduce(v); } static mod_type val(value_type v) ; static value_type mul(value_type a, value_type b) ; }; template struct policy_montgomery64 { using value_type = ull; using calc_type = u128; using mod_type = ll; static constexpr bool is_prime = false; static inline montgomery64 reducer{}; static void set_mod(mod_type m) ; static mod_type mod() ; static value_type umod() ; static value_type init(value_type v) { return reducer.inv_reduce(v); } static mod_type val(value_type v) ; static value_type mul(value_type a, value_type b) ; }; }; template constexpr tuple extgcd(T a, T b) ; #line 3311 namespace internal { template struct modint_impl { using V = typename Policy::value_type; using M = typename Policy::mod_type; using mint = modint_impl; private: V _v; public: static constexpr M mod() { M m = Policy::mod(); assert(m > 0 && "modint: modulus is not set; call mint::set_mod(m) before use"); return m; } template static auto set_mod(M m) -> decltype(T::set_mod(m)) ; static void precompute() ; static mint raw(V v) { mint x; x._v = v; return x; } modint_impl() : _v(0) { (void)mod(); } template >> modint_impl(T v) { const V m = mod(); V rem; if constexpr (is_signed_ext) { using S = make_signed_t; S x = v % S(m); if (x < 0) x += m; rem = x; } else rem = V(v % m); _v = Policy::init(rem); }; M val() const { return Policy::val(_v); } mint &operator+=(const mint &rhs) { _v += rhs._v; if (_v >= Policy::umod()) _v -= Policy::umod(); return *this; } mint &operator-=(const mint &rhs) ; mint &operator*=(const mint &rhs) { _v = Policy::mul(_v, rhs._v); return *this; } mint &operator/=(const mint &rhs) ; mint &operator++() ; mint &operator--() ; mint operator++(int) ; mint operator--(int) ; mint operator+() const ; mint operator-() const ; template mint pow(T n) const ; #line 3439 mint inv() const ; #line 3457 friend mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; } friend mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; } friend mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; } friend mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; } friend bool operator==(const mint &lhs, const mint &rhs) { return lhs._v == rhs._v; } friend bool operator!=(const mint &lhs, const mint &rhs) { return lhs._v != rhs._v; } friend M safe_hash_key(const mint &x) { return x.val(); } #line 3479 friend void rd1(mint &x) { long long a; fastio::rd1(a); x = a; } friend void wt1(const mint &x) { fastio::wt1(x.val()); } }; }; template using static_modint32 = internal::modint_impl>; template using dynamic_modint32 = internal::modint_impl>; template using static_modint64 = internal::modint_impl>; template using dynamic_modint64_odd = internal::modint_impl>; template using dynamic_modint64 = internal::modint_impl>; using modint998244353 = static_modint32<998244353>; using modint1000000007 = static_modint32<1000000007>; using modint = dynamic_modint32<-1>; using modint61 = static_modint64<(1LL << 61) - 1>; using modint64 = dynamic_modint64<-1>; template struct is_modint : std::false_type { }; template struct is_modint> : std::true_type { }; template inline constexpr bool is_modint_v = is_modint::value; template struct is_static_modint : false_type {}; template struct is_static_modint, PowInv>> : true_type {}; template struct is_static_modint, PowInv>> : true_type {}; template inline constexpr bool is_static_modint_v = is_static_modint::value; template struct is_dynamic_modint : false_type {}; template struct is_dynamic_modint> : true_type {}; template struct is_dynamic_modint> : true_type {}; template struct is_dynamic_modint> : true_type {}; template inline constexpr bool is_dynamic_modint_v = is_dynamic_modint::value; template struct has_mod : std::false_type { }; template struct has_mod> : std::true_type { }; template struct modint_less { bool operator()(const mint &a, const mint &b) const ; }; template struct modint_hash { auto operator()(const mint &x) const ; }; template struct PowerTable { private: decltype(mint::mod()) mod{}; mint base{}; vc pw; public: CPP_DUMP_DEFINE_DATA(mod, base, pw); PowerTable() {} PowerTable(const mint &base) : mod(mint::mod()), base(base), pw(1, 1) {} void reserve(int n) ; #line 3612 mint pow(int n) ; }; template struct Binomial { private: inline static decltype(T::mod()) mod; public: inline static vc fac_, finv_, inv_; static void reserve(int n) ; #line 3664 static T fac(int n) ; static T finv(int n) ; static T inv(int n) ; static T P(int n, int k) ; static T C(int n, int k) ; static T H(int n, int k) ; }; template mint stom(string s) ; #line 3757 template > pair svp2d(const pair &a, const pair &b) ; #line 3795 template pair mint_to_rat(const mint &x) { auto [p, q] = svp2d({x.val(), 1}, {mint::mod(), 0}); if (q < 0) p = -p, q = -q; return {p, q}; } namespace cpp_dump { template struct rat_value { T p, q; friend ostream &operator<<(ostream &os, const rat_value &x) { os << x.p; if (x.q != 1) os << '/' << x.q; return os; } }; struct mint_to_rat_fn { template requires requires(const T &x) { { T::mod() } -> std::convertible_to; { x.val() } -> std::convertible_to; } constexpr auto operator()(const T &x) const -> rat_value { auto [p, q] = mint_to_rat(x); return {p, q}; } }; template struct rat_object { T value; }; template inline constexpr bool rat_is_map = false; template inline constexpr bool rat_is_map> = true; template inline constexpr bool rat_is_map> = true; template inline constexpr bool rat_is_map> = true; template inline constexpr bool rat_is_map> = true; struct rat_closure : std::ranges::range_adaptor_closure { template static constexpr bool can_convert() ; #line 3887 template requires(!requires { std::views::all | std::declval(); }) constexpr decltype(auto) operator()(T &&t) const { if constexpr (!std::ranges::range && std::invocable) { return mint_to_rat_fn{}(std::forward(t)); } else if constexpr (can_convert()) { if constexpr (!std::ranges::range || rat_is_map>) return rat_object{std::forward(t)}; else return std::forward(t) | std::views::transform(*this); } else { return std::forward(t); } } }; #line 3958 template requires(!requires { std::views::all | std::declval(); }) constexpr decltype(auto) operator|(T &&t, rat_closure c) { return c(std::forward(t)); } constexpr rat_closure rat() { return rat_closure{}; } } using mint = modint998244353; // using mint = modint1000000007; // using mint = static_modint<1000000000>; // using mint = modint; using bi = Binomial; void init() { oj(mt.seed(random_device()())); } /*! * Portions corresponding to AtCoder Library (CC0-1.0): iterative segment-tree operations. * Upstream: atcoder/segtree.hpp * https://github.com/atcoder/ac-library/tree/864245a00b00dd008d1abfdc239618fdb7d139da * License: https://github.com/atcoder/ac-library/blob/864245a00b00dd008d1abfdc239618fdb7d139da/LICENSE */ struct SegmentTreeRange { private: int n; ll siz; void check_node(ll i) const { assert(1 <= i && i < 2 * siz); } public: CPP_DUMP_DEFINE_DATA(n, siz); explicit SegmentTreeRange(int n) : n(n), siz(1) { assert(0 <= n); siz = bit_ceil(ll(n)); } int size() const ; ll leaf_size() const { return siz; } ll node_count() const { return 2 * siz - 1; } int depth(ll i) const { check_node(i); return bit_width(i) - 1; } bool is_leaf(ll i) const { check_node(i); return siz <= i; } ll range_length(ll i) const { return siz >> depth(i); } pair node_to_range(ll i) const { const int d = depth(i); const ll len = siz >> d, l = (i - (1LL << d)) * len; return {l, l + len}; } ll range_to_node(ll l, ll r) const { assert(0 <= l && l < r && r <= siz); const ll len = r - l; assert(has_single_bit(len) && l % len == 0); return (siz + l) / len; } ll point_to_node(int p) const { assert(0 <= p && p < n); return siz + p; } int node_to_point(ll i) const { assert(siz <= i && i < siz + n); return i - siz; } template struct NodeRange { Iter first; Iter begin() const { return first; } Iter end() const { return {}; } bool empty() const ; vc to_v() const ; }; template struct RangeIterator { using iterator_category = input_iterator_tag; using value_type = ll; using difference_type = ptrdiff_t; using reference = ll; using pointer = void; private: ll l = 0, r = 0, i = 0; void advance() { if constexpr (from_left) { if (l < r) { const ll len = min(lsb_mask(l), bit_floor(r - l)); i = l / len; l += len; return; } } else { while (l < r) { if (l & 1) { i = l++; return; } if (r & 1) { i = --r; return; } l >>= 1, r >>= 1; } } l = r = i = 0; } public: RangeIterator() = default; RangeIterator(ll l, ll r) : l(l), r(r) { advance(); } ll operator*() const { return i; } RangeIterator &operator++() { advance(); return *this; } RangeIterator operator++(int) ; bool operator==(const RangeIterator &other) const { return l == other.l && r == other.r && i == other.i; } bool operator!=(const RangeIterator &other) const { return !(*this == other); } }; template struct AncestorIterator { using iterator_category = input_iterator_tag; using value_type = ll; using difference_type = ptrdiff_t; using reference = ll; using pointer = void; private: ll target = 0, i = 0; int shift = 0; public: AncestorIterator() = default; explicit AncestorIterator(ll target) : target(target), i(target) { if constexpr (from_top) { shift = bit_width(target) - 1; i = 1; } } ll operator*() const ; AncestorIterator &operator++() ; AncestorIterator operator++(int) ; bool operator==(const AncestorIterator &other) const ; bool operator!=(const AncestorIterator &other) const ; }; auto range_to_nodes_from_left(int l, int r) const { assert(0 <= l && l <= r && r <= n); return NodeRange>{RangeIterator(siz + l, siz + r)}; } auto range_to_nodes_from_bottom(int l, int r) const { assert(0 <= l && l <= r && r <= n); return NodeRange>{RangeIterator(siz + l, siz + r)}; } auto ancestors_from_bottom(ll i) const { check_node(i); return NodeRange>{AncestorIterator(i)}; } auto ancestors_from_top(ll i) const { check_node(i); return NodeRange>{AncestorIterator(i)}; } auto point_to_nodes_from_bottom(int p) const { return ancestors_from_bottom(point_to_node(p)); } auto point_to_nodes_from_top(int p) const { return ancestors_from_top(point_to_node(p)); } }; template struct SegmentTree { using S = typename M::S; private: int n, siz; vc dat; void update(int i) { dat[i] = M::op(dat[2 * i], dat[2 * i + 1]); } public: SegmentTree() {} SegmentTree(int n) : SegmentTree(vc(n, M::e())) {} template SegmentTree(const Iter &bg, const Iter &ed) : SegmentTree(vc(bg, ed)) {} template SegmentTree(const vc &vec) : n(vec.size()), siz(bit_ceil(vec.size())), dat(2 * siz, M::e()) { repi(i, vec.size()) dat[siz + i] = vec[i]; repi(i, siz - 1, 0, -1) update(i); } void set(int p, const S &x) { assert(0 <= p && p < n); p += siz; dat[p] = x; while (p > 1) p >>= 1, update(p); } S get(int p) const ; S prod(int l, int r) const ; #line 4264 S all_prod() const ; template X prod_apply(int l, int r, X x, F &&apply) const { for (auto i : SegmentTreeRange(n).range_to_nodes_from_left(l, r)) x = apply(x, dat[i]); return x; } template int max_right_ok(int l, const G &g) const ; #line 4310 template int min_left_ok(int r, const G &g) const ; #line 4342 vc content() const ; }; #line 4465 template struct IntervalMap { struct Segment { I l, r; T x; }; private: struct Compare { using is_transparent = void; bool operator()(const Segment &a, const Segment &b) const { return a.l < b.l; } bool operator()(const Segment &a, const I b) const { return a.l < b; } bool operator()(const I a, const Segment &b) const { return a < b.l; } }; std::set segs; T dflt; template void replace(I l, I r, const T *x, Add &add, Del &del) { assert(!(r < l)); if (!(l < r)) return; if (x) { auto it = segs.lower_bound(l); if (it != segs.begin()) { --it; if (!(it->r < l) && it->x == *x) l = it->l; } it = segs.upper_bound(r); if (it != segs.begin()) { --it; if (r < it->r && it->x == *x) r = it->r; } } auto it = geq_min_it(l).value_or(segs.end()); while (it != segs.end() && it->l < r) { const Segment a = *it; del(a.l, a.r, a.x); it = segs.erase(it); if (a.l < l) { segs.insert(it, Segment{a.l, l, a.x}); add(a.l, l, a.x); } if (r < a.r) { it = segs.insert(it, Segment{r, a.r, a.x}); add(r, a.r, a.x); break; } } if (x) { segs.insert(it, Segment{l, r, *x}); add(l, r, *x); } } public: using iterator = typename std::set::const_iterator; explicit IntervalMap(const T &dflt = T()) : dflt(dflt) {} IntervalMap(const vc &a, const T &dflt = T()) : dflt(dflt) { const int n = a.size(); for (int l = 0, r; l < n; l = r) { for (r = l + 1; r < n && a[l] == a[r]; ++r) {} segs.insert(segs.end(), Segment{I(l), I(r), a[l]}); } } optional get_it(const I p) const ; optional leq_max_it(const I p) const ; optional geq_min_it(const I p) const { auto it = segs.upper_bound(p); if (it != segs.begin() && p < prev(it)->r) return prev(it); if (it != segs.end()) return it; return nullopt; } optional lt_max_it(const I p) const ; optional gt_min_it(const I p) const ; T get(const I p) const ; T operator[](const I p) const ; template void set(I l, I r, T x, Add &&add, Del &&del) { replace(l, r, &x, add, del); } void set(I l, I r, T x) ; template void erase(I l, I r, Add &&add, Del &&del) ; void erase(I l, I r) ; bool empty() const ; iterator begin() const ; iterator end() const ; vc> content() const ; }; #line 4667 namespace internal_monoid_power { template struct HasMemberScalarProduct : false_type {}; template struct HasMemberScalarProduct().operator*({declval()})))>> : true_type {}; template struct HasFreeScalarProduct : false_type {}; template struct HasFreeScalarProduct(), {declval()})))>> : true_type {}; template struct HasScalarProduct : bool_constant || is_same_v || HasMemberScalarProduct::value || HasFreeScalarProduct::value> {}; template constexpr T scalar_product(const T &x, I k) ; template constexpr T scale(const T &x, I k) ; #line 4716 template constexpr T bounded_scale(const T &x, I k, const T &cap) ; #line 4741 template using ConstRefPower = typename M::S (*)(const typename M::S &, I); template using ValuePower = typename M::S (*)(typename M::S, I); template struct HasConstRefPower : false_type {}; template struct HasConstRefPower>(M::pow))>> : true_type {}; template struct HasValuePower : false_type {}; template struct HasValuePower>(M::pow))>> : true_type {}; template constexpr typename M::S power(const typename M::S &x, I k) ; } template struct Monoid { using S = S_; static constexpr auto op = op_; static constexpr auto e = e_; }; template struct Group { using S = S_; static constexpr auto op = op_; static constexpr auto e = e_; static constexpr auto inv = inv_; }; template struct SemiRing { using S = S_; static constexpr auto add = add_; static constexpr auto e0 = e0_; static constexpr auto mul = mul_; static constexpr auto e1 = e1_; }; template struct Ring { using S = S_; static constexpr auto add = add_; static constexpr auto e0 = e0_; static constexpr auto minus = minus_; static constexpr auto mul = mul_; static constexpr auto e1 = e1_; }; template struct Field { using S = S_; static constexpr auto add = add_; static constexpr auto e0 = e0_; static constexpr auto minus = minus_; static constexpr auto mul = mul_; static constexpr auto e1 = e1_; static constexpr auto inv = inv_; }; template struct HasInverse : false_type {}; template struct HasInverse()))>> : true_type {}; template struct OppositeMonoid { using S = typename M::S; static constexpr S op(const S &a, const S &b) { return M::op(b, a); } static constexpr auto e = M::e; template static constexpr S pow(const S &x, I k) { return internal_monoid_power::power(x, k); } }; template struct OppositeGroup { using S = typename G::S; static constexpr S op(const S &a, const S &b) { return G::op(b, a); } static constexpr auto e = G::e; static constexpr auto inv = G::inv; template static constexpr S pow(const S &x, I k) { return internal_monoid_power::power(x, k); } }; template struct NormalAndOppositeMonoid { struct S { typename M::S normal; typename M::S opposite; S() {} template , std::nullptr_t> = nullptr> S(Args &&...args) : normal(std::forward(args)...), opposite(normal) {} S rev() ; S(const typename M::S &normal, const typename M::S &opposite) : normal(normal), opposite(opposite) {} }; static constexpr S op(const S &a, const S &b) { return {M::op(a.normal, b.normal), M::op(b.opposite, a.opposite)}; } static constexpr S e() { return {M::e(), M::e()}; } template static constexpr S pow(const S &x, I k) { return {internal_monoid_power::power(x.normal, k), internal_monoid_power::power(x.opposite, k)}; } }; template struct NormalAndOppositeGroup { struct S { typename G::S normal; typename G::S opposite; S() {} template , std::nullptr_t> = nullptr> S(Args &&...args) : normal(std::forward(args)...), opposite(normal) {} S rev() ; S(const typename G::S &normal, const typename G::S &opposite) : normal(normal), opposite(opposite) {} }; static constexpr S op(const S &a, const S &b) { return {G::op(a.normal, b.normal), G::op(b.opposite, a.opposite)}; } static constexpr S e() { return {G::e(), G::e()}; } static constexpr S inv(const S &a) { return {G::inv(a.normal), G::inv(a.opposite)}; } template static constexpr S pow(const S &x, I k) { return {internal_monoid_power::power(x.normal, k), internal_monoid_power::power(x.opposite, k)}; } }; template using MonoidOfSemiRingAdd = Monoid; template using MonoidOfSemiRingMul = Monoid; template using GroupOfRingAdd = Group; template using GroupOfFieldMul = Group; template struct SemiRingFromMonoidMonoid { static_assert(is_same_v, "Madd::S and Mmul::S must be identical"); using S = typename Madd::S; static constexpr auto add = Madd::op; static constexpr auto e0 = Madd::e; static constexpr auto mul = Mmul::op; static constexpr auto e1 = Mmul::e; }; template struct RingFromGroupMonoid { static_assert(is_same_v, "Gadd::S and Mmul::S must be identical"); using S = typename Gadd::S; static constexpr auto add = Gadd::op; static constexpr auto e0 = Gadd::e; static constexpr auto minus = Gadd::inv; static constexpr auto mul = Mmul::op; static constexpr auto e1 = Mmul::e; }; template struct FieldFromGroupGroup { static_assert(is_same_v, "Gadd::S and Gmul::S must be identical"); using S = typename Gadd::S; static constexpr auto add = Gadd::op; static constexpr auto e0 = Gadd::e; static constexpr auto minus = Gadd::inv; static constexpr auto mul = Gmul::op; static constexpr auto e1 = Gmul::e; static constexpr auto inv = Gmul::inv; }; template struct has_e1 : false_type {}; template struct has_e1> : true_type {}; template inline constexpr bool has_e1_v = has_e1::value; template struct MonoidMul { using S = T; static constexpr S op(S a, S b) { return a * b; } static constexpr S e() { if constexpr (has_e1_v) return S::e1(); else return 1; } }; template struct GroupAddSub { using S = T; static constexpr S op(S a, S b) { return a + b; } static constexpr S e() { if constexpr (has_e0_v) return S::e0(); else return S{}; } static constexpr S inv(S a) { return -a; } template () * declval())> static constexpr S pow(const S &a, I k) { return a * k; } }; template struct GroupMulDiv { using S = T; static constexpr S op(S a, S b) { return a * b; } static constexpr S e() { if constexpr (has_e1_v) return S::e1(); else return S(1); } static constexpr S inv(S a) { return e() / a; } }; template using SemiRingMinPlus = SemiRingFromMonoidMonoid, MonoidAdd>; template using SemiRingMaxPlus = SemiRingFromMonoidMonoid, MonoidAdd>; template using RingAddSubMul = RingFromGroupMonoid, MonoidMul>; template using FieldAddSubMulDiv = FieldFromGroupGroup, GroupMulDiv>; #line 5018 namespace internal { template struct ordinary_mod32 : false_type {}; template struct ordinary_mod32, PowInv>> : true_type {}; template struct ordinary_mod32> : true_type {}; } namespace internal { template struct ordinary_mod32_add_group : false_type {}; template struct ordinary_mod32_add_group> : ordinary_mod32 {}; template struct ordinary_mod32_add_group::op, GroupAddSub::e, GroupAddSub::inv>> : ordinary_mod32 {}; template struct ordinary_mod32_field : false_type {}; template struct ordinary_mod32_field> : ordinary_mod32 {}; } #include #include #include namespace internal { template inline std::uint32_t block_dot32(std::size_t n, std::uint32_t mod, std::size_t block, std::uint32_t seed, NextProduct next) { std::uint64_t carry = seed; while (n) { const std::size_t count = std::min(n, block); std::size_t i = 0; std::uint64_t s0 = carry, s1 = 0, s2 = 0, s3 = 0; for (; i + 4 <= count; i += 4) { s0 += next(); s1 += next(); s2 += next(); s3 += next(); } for (; i < count; ++i) s0 += next(); carry = (s0 + s1 + s2 + s3) % mod; n -= count; } return static_cast(carry); } } namespace internal { template using dot_product_mod32_value = ordinary_mod32; template S dot_product_mod32_impl(int n, It1 a, It2 b) { return S::raw(block_dot32(n, S::mod(), block, 0, [&]() { return ull((a++)->val()) * (b++)->val(); })); } template S dot_product_mod32_values(int n, It1 a, It2 b) { static_assert(ordinary_mod32::value); assert(n >= 0); if (S::mod() <= (1 << 30)) return dot_product_mod32_impl<16, S>(n, a, b); return dot_product_mod32_impl<4, S>(n, a, b); } } namespace internal { template struct dot_product_mod32 : false_type {}; template struct dot_product_mod32> : dot_product_mod32_value {}; template struct dot_product_mod32> : dot_product_mod32_value {}; template struct dot_product_mod32, MonoidMul>> : dot_product_mod32_value {}; } template typename SR::S dot_product(int n, It1 a, It2 b) { using S = typename SR::S; assert(n >= 0); if constexpr (internal::dot_product_mod32::value) { return internal::dot_product_mod32_values(n, a, b); } else { S sum = SR::e0(); repi(i, n) sum = SR::add(sum, SR::mul(*a++, *b++)); return sum; } } //! https://codeforces.com/blog/entry/61306 template struct BerlekampMassey { using S = typename F::S; vc a, b, c, tmp; int pos = -1; S inv_x = F::e0(); CPP_DUMP_DEFINE_DATA(a, c, pos); int degree() const ; void append(S value) { const int i = a.size(), d = c.size(); a.eb(value); S y = F::add(value, F::minus(dot_product(d, c.begin(), a.rbegin() + 1))); if (y == F::e0()) return; if (c.empty()) { c.assign(i + 1, F::e0()); pos = i; inv_x = F::inv(y); return; } S z = F::mul(y, inv_x); int d2 = i - pos + b.size(); if (d2 > d) { tmp = c; c.resize(d2, F::e0()); } c[i - 1 - pos] = F::add(c[i - 1 - pos], z); const S minus_z = F::minus(z); repi(j, b.size()) c[i - pos + j] = F::add(c[i - pos + j], F::mul(minus_z, b[j])); if (d2 > d) pos = i, inv_x = F::inv(y), swap(tmp, b); } vc coefficients() const ; }; template vc berlekamp_massey(const vc &a) ; #line 5232 template mint random_modint() ; //! https://yukicoder.me/wiki/black_box_linear_algebra namespace bbla { template mint random_sample_mint() ; template vc krylov_sequence(const LinearMap &linear_map, const vc &u, vc v, int count) ; #line 5269 template vc apply_polynomial(const LinearMap &linear_map, const vc &v, const vc &p) ; #line 5290 template )> vc minimal_polynomial_vector(const LinearMap &linear_map, vc v, const RandomSample &random_sample = random_sample_mint) ; #line 5306 template )> vc minimal_polynomial(int n, const LinearMap &linear_map, const RandomSample &random_sample = random_sample_mint) ; #line 5321 template )> vc solve(const LinearMap &linear_map, vc y, const RandomSample &random_sample = random_sample_mint) ; #line 5364 template )> typename F::S det(int n, const LinearMap &linear_map, const RandomSample &random_sample = random_sample_mint) ; #line 5395 } template struct CSR { protected: int n, m; vc start; vc elist; vc len; inline int get_last(int i) const { if constexpr (is_erasable) return start[i] + len[i]; else return start[i + 1]; } template struct RowBase { using iterator = Iter; using reference = typename iterator_traits::reference; private: iterator begi, endi; public: RowBase(const iterator &begi, const iterator &endi) : begi(begi), endi(endi) {} inline iterator begin() const { return begi; } inline iterator end() const { return endi; } template inline I size() const ; inline bool empty() const ; inline reference operator[](int i) const { return *(begi + i); } inline reference at(int i) const ; inline reference front() const { assert(!empty()); return *begi; } inline reference back() const { assert(!empty()); return *prev(endi); } vc to_v() const ; vc content() const ; }; using Row = RowBase::iterator>; using ConstRow = RowBase::const_iterator>; public: CSR() : n(0), m(0), start{0} {} template CSR(const vc &row_sizes) : n(row_sizes.size()) { static_assert(is_integral_ext); start.resize(n + 1); for (int i = 0; i < n; i++) { if constexpr (is_signed_ext) assert(row_sizes[i] >= 0); start[i + 1] = start[i] + int(row_sizes[i]); } m = start.back(); elist.resize(m); if constexpr (is_erasable) len.assign(ALL(row_sizes)); } template CSR(int n, const vc> &ies) : n(n), m(ies.size()), start(n, 0), elist(m) { if constexpr (is_erasable) len.resize(n); fec([ i, e ] : ies) { assert(0 <= i && i < n); start[i]++; } start = cumlsum(start); if constexpr (is_erasable) repi(i, n) len[i] = start[i + 1] - start[i]; auto cnt = start; repi(j, m) { cauto & [ i, e ] = ies[j]; int &k = cnt[i]; elist[k] = e; k++; } } template CSR(const vvc &vv) : n(vv.size()), start(n + 1, 0) { m = 0; fec(row : vv) m += row.size(); elist.resize(m); if constexpr (is_erasable) len.resize(n); for (int i = 0, j = 0; i < n; i++) { start[i] = j; if constexpr (is_erasable) len[i] = vv[i].size(); fec(e : vv[i]) { elist[j] = e; j++; } } start.back() = m; } template explicit CSR(const CSR &other) : CSR(gen_vec(other.template size(), [&](int i) { return other[i].template size(); })) { for (int i = 0; i < n; i++) copy(ALL(other[i]), elist.begin() + start[i]); } Row operator[](int i) { return Row(elist.begin() + start[i], elist.begin() + get_last(i)); } ConstRow operator[](int i) const ; Row at(int i) ; ConstRow at(int i) const ; void pop_back(int i) ; int offset(int i) const ; void sortunique() ; #line 5589 template I size() const ; vvc to_vv() const ; vvc content() const ; vc &get_elist() ; const vc &get_elist() const ; }; template CSR(const vvc &) -> CSR; namespace internal { template pair row_reduction_mod32(Rows &a, int n, int m, bool rref) ; #line 5678 } #include #include #include #include #include #include #include namespace internal { namespace matrix_power_mod32_detail { template inline constexpr bool supported_builtin_exponent_v = std::is_integral_v || std::is_same_v || std::is_same_v ; template using Matrix = std::vector>; template Matrix identity(std::size_t n) ; template void require_square(const Matrix& a) ; template Matrix multiply(const Matrix& a, const Matrix& b) ; #line 5734 template Matrix power_over_ring(const Matrix& a, T exponent) ; #line 5748 template std::size_t binary_multiplication_count(T exponent) ; template S scalar_power(S a, T exponent) ; template Matrix power_weighted_map(std::vector next, std::vector weight, T exponent, bool transposed) ; #line 5803 template std::optional> rank_one_power(const Matrix& a, T exponent) ; #line 5840 template std::optional> invert(const Matrix& a) ; #line 5876 template std::vector apply_vector(const Matrix& a, const std::vector& v) ; template std::vector polynomial_multiply(const std::vector& a, const std::vector& b, const std::vector& recurrence) ; #line 5909 template std::vector polynomial_power(T exponent, const std::vector& recurrence) ; #line 5925 template std::optional> try_cyclic_power(const Matrix& a, T exponent) ; #line 5958 template std::vector characteristic_recurrence(Matrix h) ; #line 6004 inline std::size_t evaluation_block_size(std::size_t n) { std::size_t s = 1; while (s * s < n) ++s; return s; } template Matrix evaluate_polynomial(const Matrix& a, const std::vector& coefficient) ; #line 6039 template Matrix power_over_field(const Matrix& a, T exponent) ; #line 6098 template bool is_prime_modulus() ; #line 6113 } } namespace internal { template void matrix_product(int n, int m, int p, const A &a, const B &b, C &c) { using S = typename F::S; const S zero = F::e0(); if (n == m && m == p && n <= 8) { bool upper = true; for (int i = 1; i < n && upper; ++i) for (int j = 0; j < i; ++j) if (a[i][j] != zero || b[i][j] != zero) { upper = false; break; } if (upper) { for (int i = 0; i < n; ++i) for (int k = i; k < m; ++k) { S x = a[i][k]; if (x == zero) continue; for (int j = k; j < p; ++j) c[i][j] = F::add(c[i][j], F::mul(x, b[k][j])); } return; } } if (n >= 16 && m >= 16 && p >= 16) { ll left = 0, right = 0; for (int i = 0; i < n; ++i) for (int k = 0; k < m; ++k) left += a[i][k] != zero; if (!left) return; vc sizes(m); for (int k = 0; k < m; ++k) for (int j = 0; j < p; ++j) if (b[k][j] != zero) { ++sizes[k]; ++right; } if (!right) return; if (right * 4 <= ll(m) * p) { CSR> rows(sizes); for (int k = 0; k < m; ++k) { int at = 0; for (int j = 0; j < p; ++j) if (b[k][j] != zero) rows[k][at++] = {j, b[k][j]}; } for (int i = 0; i < n; ++i) for (int k = 0; k < m; ++k) { S x = a[i][k]; if (x == zero) continue; for (const auto &[j, y] : rows[k]) c[i][j] = F::add(c[i][j], F::mul(x, y)); } return; } if constexpr (dot_product_mod32::value) { if (left * 2 >= ll(n) * m) { vc bt(size_t(p) * m); for (int k = 0; k < m; ++k) for (int j = 0; j < p; ++j) bt[size_t(j) * m + k] = b[k][j]; for (int i = 0; i < n; ++i) for (int j = 0; j < p; ++j) c[i][j] = dot_product(m, a[i].begin(), bt.begin() + size_t(j) * m); return; } } if (left * 4 <= ll(n) * m) { for (int i = 0; i < n; ++i) for (int k = 0; k < m; ++k) { S x = a[i][k]; if (x == zero) continue; for (int j = 0; j < p; ++j) c[i][j] = F::add(c[i][j], F::mul(x, b[k][j])); } return; } } for (int ii = 0; ii < n; ii += BS) for (int kk = 0; kk < m; kk += BS) for (int jj = 0; jj < p; jj += BS) for (int i = ii; i < min(ii + BS, n); ++i) for (int k = kk; k < min(kk + BS, m); ++k) { S x = a[i][k]; if (x == zero) continue; for (int j = jj; j < min(jj + BS, p); ++j) c[i][j] = F::add(c[i][j], F::mul(x, b[k][j])); } } } template struct MatrixArray : array, n> { using S = typename F::S; using M = MatrixArray; using Vn = array; using Vm = array; using Base = array, n>; using Base::at; template static constexpr pair shape() ; S &operator()(int i,int j) ; const S &operator()(int i,int j) const ; S &at(int i,int j) ; const S &at(int i,int j) const ; auto &row(int i) ; const auto &row(int i) const ; MatrixArray(const S &diag = F::e0(), const S &non_diag = F::e0()) { repi(i, n) repi(j, m)(*this)[i][j] = i == j ? diag : non_diag; } MatrixArray(const array, n> &a) { repi(i, n) repi(j, m) (*this)[i][j] = a[i][j]; } MatrixArray transpose() const ; static constexpr MatrixArray e0() ; static constexpr MatrixArray e1() { return MatrixArray(F::e1(), F::e0()); } M operator-() const ; M &operator+=(const M &b) ; M &operator-=(const M &b) ; M &operator*=(const S &x) ; M &operator/=(const S &x) ; Vn operator*(const Vm &v) const { Vn res; fill(ALL(res), F::e0()); repi(i, n) res[i] = dot_product(m, (*this)[i].begin(), v.begin()); return res; } friend Vm operator*(const Vn &v, const M &a) { Vm res; fill(ALL(res), F::e0()); repi(i, n) repi(j, m) res[j] = F::add(res[j], F::mul(v[i], a[i][j])); return res; } template MatrixArray operator*(const MatrixArray &b) const { MatrixArray res; repi(i, n) repi(j, p) res[i][j] = F::e0(); internal::matrix_product(n, m, p, *this, b, res); return res; } template M pow(T k) const ; #line 6347 M operator+(const M &a) const ; M operator-(const M &a) const ; M operator*(const S &x) const ; M operator/(const S &x) const { return M(*this) /= x; } M &operator*=(const M &a) ; template tuple row_reduction(bool rref = false) const ; #line 6417 template I rank() const ; S det() const ; optional inv() const ; #line 6445 optional>> solve(const Vn &b) const ; #line 6478 }; using Mat = MatrixArray, 3, 3>; const Mat M0 = {{{ {1, 1, 0}, {0, 1, 0}, {0, 0, 1} }}}; const Mat M1 = {{{ {1, 0, 0}, {1, 1, 1}, {0, 0, 1} }}}; void main2() { LL(N, Q); STR(S); auto A = stov(S, '0'); vc vec(N); rep(i, N) vec[i] = S[i] == '0' ? M0 : M1; SegmentTree>> seg(vec); IntervalMap im(A); rep(_, Q) { LL(t, l, r); l--; if (t == 1) { auto add = [&](ll, ll, ll) {}; auto del = [&](ll l, ll r, ll x) { if (x != 2) { rep(i, l, r) seg.set(i, MonoidMul::e()); } }; im.set(l, r, 2, add, del); dump(seg); } else if (t == 2) { auto res = seg.prod_apply(l, r, array{0, 0, 1}, [&](auto &x, auto &m) { return m * x; }); dump(res); PRINT(res[0] + res[1]); } } } void test() { } template struct Main { Main() { cauto CERR = [](string val, string color) { string s = "\033[" + color + "m" + val + "\033[m"; }; CERR("\n[FAST_IO]\n\n", "32"); cout << fixed << setprecision(20); init(); #line 6589 CERR("\n[SINGLE_TESTCASE]\n\n", "36"); main2(); #line 6604 } }; Main main_dummy; int main() {} // submit-code: hash=ea0db16f393f source=ea0db16f393f2245714ea5d797943c296c85b60dfea8638616987ac122855335 input=d130b4789af86c9439b99daa61e83c8d3f11cad8333a4c94a6af4016723b835d body=f34d4e141171ba781cdaac928297f4336f3660281672a1c27c9349ebf6c7fb3e