// 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) ; 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) ; 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) { ((get(a) += get(b)), ...); return a; } 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) ; 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() { if constexpr (default_infty_detail::has_infty::value) return default_infty_detail::custom_value(); else if constexpr (default_infty_detail::is_product>::value) return default_infty_detail::product_value>( make_index_sequence>>{}); else if constexpr (is_same_v || is_same_v) return T(INF) * T(INF); else if constexpr (is_integral_ext && !is_same_v) { if constexpr (sizeof(T) >= sizeof(ll)) return T(INF); else if constexpr (numeric_limits::digits >= 31) return (T(1) << 30) - 1; else return T(numeric_limits::max() / 2); } else if constexpr (numeric_limits::has_infinity) return numeric_limits::infinity(); else static_assert(default_infty_detail::unsupported, "No default infinity for this type; specify infty explicitly or define T::infty()."); } template inline bool chmin(T &a, U b) { return a > b ? a = b, true : false; } template inline bool chmax(T &a, U b) { return a < b ? a = b, true : false; } 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) { assert(b >= 0); if (b == 0) return 1; if (a == 0 || a == 1) return a; if (a < 0 && a == -1) return b & 1 ? -1 : 1; T res = 1, tmp = a; while (true) { if (b & 1) res *= tmp; b >>= 1; if (b == 0) break; tmp *= tmp; } return res; } template T mul_limited(A a, B b, M m) { assert(a >= 0 && b >= 0 && m >= 0); if (b == 0) return 0; return T(a) > T(m) / T(b) ? T(m) : T(a) * T(b); } template T mul_limited(A a, B b) { return mul_limited(a, b, default_infty()); } template T pow_limited(A a, B b, M m) { assert(a >= 0 && b >= 0 && m >= 0); if (a <= 1 || b == 0) return min(ipow(a, b), T(m)); T res = 1, tmp = a; while (true) { if (b & 1) { if (res > T(m) / tmp) return m; res *= tmp; } b >>= 1; if (b == 0) break; if (tmp > T(m) / tmp) return m; tmp *= tmp; } return res; } template T pow_limited(A a, B b) { return pow_limited(a, b, default_infty()); } 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) ; #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) ; 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() { if constexpr (is_same_v) return default_infty(); else return resolved_value(); } 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 = {}) { sort(ALL(v), comp); unique(v, 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) ; static constexpr S e() ; 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) ; static constexpr decltype(auto) e() ; 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) ; static constexpr S e() ; 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 = {}) { return ranges::lower_bound(v, val, comp, proj) - v.begin(); } 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) ; #line 2197 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) { rd1(x.first), rd1(x.second); } template void rd1(tuple &x) { apply([](auto &...element) { (rd1(element), ...); }, x); } template void rd1(array &x) ; template void rd1(vc &x) { if constexpr (is_same_v) for (size_t i = 0; i < x.size(); ++i) { bool value; rd1(value); x[i] = value; } else for (auto &element : x) rd1(element); } 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) ; 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) { (v.resize(size_t(n)), ...); READnodump(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) { for (auto &vi : v) PRINT(vi); } #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) { for (auto &vi : v) vi += 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) ; #line 3079 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() ; 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) ; 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() ; template static auto set_mod(M m) -> decltype(T::set_mod(m)) ; static void precompute() ; static mint raw(V v) ; 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 ; mint &operator+=(const mint &rhs) ; mint &operator-=(const mint &rhs) ; mint &operator*=(const mint &rhs) ; 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 3441 mint inv() const ; #line 3459 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 3481 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 3614 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 3666 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 3759 template > pair svp2d(const pair &a, const pair &b) ; #line 3797 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 3889 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 3960 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()())); } namespace internal { template vvc union_find_content(const vc &par, const IsRoot &is_root) ; #line 4016 } template struct UnionFind { friend UFData; protected: vc par; vc vdat; public: typename UFData::GData gdat; UnionFind() {} UnionFind(int n) : par(n, -1), vdat(n), gdat(n) { repi(i, n) vdat[i] = typename UFData::VData(i); } void reset(int n) { assert(n >= 0); par.assign(n, -1); vdat.resize(n); gdat = typename UFData::GData(n); repi(i, n) vdat[i] = typename UFData::VData(i); } virtual int leader(int x) { assert(0 <= x && x < SZ(par)); if (par[x] < 0) return x; if constexpr (compress) return par[x] = leader(par[x]); else return leader(par[x]); } template I size(int x) ; typename UFData::VData &get_vdata(int x) ; bool same(int x, int y) ; template I merge(int x, int y, const typename UFData::EWeight &w = 1) { x = leader(x), y = leader(y); if (x == y) { UFData::add_edge_same(*this, x, w); return x; } if (-par[x] < -par[y]) swap(x, y); par[x] += par[y], par[y] = x; UFData::add_edge_diff(*this, x, y, w); return x; } template vc group_ids() ; #line 4097 vvc content() const ; }; template struct UFDataEmpty { struct VData { VData() {} VData(int) {} }; struct GData { GData() {} GData(int) {} }; using EWeight = EWeight_; template static void add_edge_diff(UF &, int, int, EWeight) {} template static void add_edge_same(UF &, int, EWeight) {} }; template struct UFDataEverything { struct VData { VData() {} ll vsum; EWeight_ esum; vc vlist; VData(int i) { vsum = 1; esum = EWeight_{}; if constexpr (need_vlist) vlist = {i}; } }; struct GData { GData() {} ll cmp_cnt; ll min_leader, max_leader; GData(int n) { cmp_cnt = n; min_leader = 0, max_leader = n - 1; } }; using EWeight = EWeight_; template static void add_edge_diff(UF &uf, int x, int y, EWeight w) ; #line 4177 template static void add_edge_same(UF &uf, int x, EWeight w) ; }; #line 4203 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 ; inline iterator end() const ; template inline I size() const { return endi - begi; } inline bool empty() const ; inline reference operator[](int i) const { return *(begi + i); } inline reference at(int i) const ; inline reference front() const ; inline reference back() const ; 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 { return ConstRow(elist.begin() + start[i], elist.begin() + get_last(i)); } Row at(int i) ; ConstRow at(int i) const ; void pop_back(int i) ; int offset(int i) const { assert(0 <= i && i <= n); return start[i]; } void sortunique() ; #line 4387 template I size() const ; vvc to_vv() const ; vvc content() const ; vc &get_elist() ; const vc &get_elist() const { return elist; } }; template CSR(const vvc &) -> CSR; template struct Edge { int from, to; Cost cost; int index; CPP_DUMP_DEFINE_DATA(from, to, cost, index); Edge() : from(-1), to(-1), cost{}, index(-1) {} Edge(int s, int t, Cost c, int i = -1) : from(s), to(t), cost(c), index(i) {} operator int() const { return to; } bool operator<(const Edge &rhs) const ; Edge rev() const ; }; template <> struct Edge { int from, to, index; static constexpr ll cost = 1; CPP_DUMP_DEFINE_DATA(from, to, cost, index); Edge() : from(-1), to(-1), index(-1) {} Edge(int s, int t, int i = -1) : from(s), to(t), index(i) {} operator int() const { return to; } bool operator<(const Edge &) const ; Edge rev() const ; }; template vc> rev_path(const vc> &path) ; template struct Graph { using E = Edge; protected: template > struct InternalEdge { int to, index; C cost; }; template struct InternalEdge { int to, index; static constexpr ll cost = 1; }; using GE = conditional_t>; using Weight = decay_t; int n = 0, m = 0, era = 0; CSR g; vc eid_to_elist_id; static E make_edge(int from, int to, const Weight &cost, int index) { if constexpr (is_void_v) return E(from, to, index); else return E(from, to, cost, index); } struct OutEdgeRow; struct OutEdgeIter { using iterator_category = input_iterator_tag; using value_type = E; using difference_type = ptrdiff_t; using pointer = const E *; using reference = const E &; private: friend struct OutEdgeRow; int from = -1; typename vc::const_iterator it; mutable E e; OutEdgeIter(int from, typename vc::const_iterator it) : from(from), it(it) {} public: OutEdgeIter() = default; reference operator*() const { if constexpr (is_erasable) return *it; else { e = make_edge(from, it->to, it->cost, it->index); return e; } } pointer operator->() const { return &**this; } OutEdgeIter &operator++() { ++it; return *this; } OutEdgeIter operator++(int) ; bool operator==(const OutEdgeIter &rhs) const { return it == rhs.it; } bool operator!=(const OutEdgeIter &rhs) const { return !(*this == rhs); } }; struct OutEdgeRow { private: const Graph *g; int from, l, r; OutEdgeIter iter(int pos) const { return {from, g->g.get_elist().begin() + pos}; } public: OutEdgeRow(const Graph *g, int from) : g(g), from(from), l(g->g.offset(from)), r(l + g->g[from].size()) {} OutEdgeIter begin() const { return iter(l); } OutEdgeIter end() const { return iter(r); } template I size() const ; bool empty() const ; E operator[](int i) const ; E at(int i) const ; E front() const ; E back() const ; vc to_v() const ; }; E get_edge(int from, int pos) const ; template void build(F input_edge) { vc row_sizes(n); repi(i, m) { auto [u, v, w] = input_edge(i); assert(0 <= u && u < n && 0 <= v && v < n); row_sizes[u]++; if constexpr (!is_directed) if (u != v) row_sizes[v]++; } g = CSR(row_sizes); if constexpr (is_erasable) eid_to_elist_id.assign((is_directed ? 1 : 2) * m, -1); vc cnt(n); repi(i, m) { auto [u, v, w] = input_edge(i); int j = cnt[u]++; int k = g.offset(u) + j; if constexpr (is_erasable) g[u][j] = make_edge(u, v, w, i); else if constexpr (is_void_v) g[u][j] = GE{int(v), i}; else g[u][j] = GE{int(v), i, w}; if constexpr (is_erasable) { int id = is_directed ? i : 2 * i + (u <= v); eid_to_elist_id[id] = k; } if constexpr (!is_directed) { if (u != v) { j = cnt[v]++; k = g.offset(v) + j; if constexpr (is_erasable) g[v][j] = make_edge(v, u, w, i); else if constexpr (is_void_v) g[v][j] = GE{int(u), i}; else g[v][j] = GE{int(u), i, w}; if constexpr (is_erasable) eid_to_elist_id[2 * i + (v <= u)] = k; } } } } public: local(auto content() const { return pair{n, edges()}; }) Graph() {} template Graph(int n, const vc> &es) : n(n), m(es.size()), era(0) { build(LMD(i, (tuple{es[i].first, es[i].second, Weight(1)}))); } template , int> = 0> Graph(int n, const vc> &es, const Weight &dflt_cost) : n(n), m(es.size()), era(0) { build(LMD(i, (tuple{es[i].first, es[i].second, dflt_cost}))); } template && !is_void_v, int> = 0> Graph(int n, const vc> &es) : n(n), m(es.size()), era(0) { build(LMD(i, es[i])); } Graph(int n, const vc &es) : n(n), m(es.size()), era(0) { build(LMD(i, (tuple{es[i].from, es[i].to, es[i].cost}))); } template I size() const { return n; } template I num_of_edges() const { return m - era; } auto out_edges(int v) const { return OutEdgeRow(this, v); } template vc out_vertices(int v) const ; vc edges() const { vc res; res.reserve(num_of_edges()); if constexpr (is_directed) { repi(v, n) fec(e : out_edges(v)) { res.eb(e); } } else { repi(v, n) fec(e : out_edges(v)) { if (e.from <= e.to) res.eb(e); } } return res; } vvc adj_list() const ; template vvc adj_matrix_ecnt() const ; template vc indegs() const ; template vc outdegs() const ; void erase_edge(int eid) ; #line 4764 private: void internal_erase(int elist_id) ; #line 4790 }; template Graph(int, const vc> &) -> Graph; template Graph(int, const vc> &) -> Graph; template Graph(int, const vc> &, const Cost &) -> Graph; template Graph(int, const vc> &) -> Graph; template using GraphDirected = Graph; template using GraphUndirected = Graph; template GraphDirected rev_graph(const GraphDirected &g) ; #line 4831 template struct MyDeque { private: vc d; int l = 0, sz = 0; int index(int i) const { i += l; return i < SZ(d) ? i : i - SZ(d); } void extend(int cap) { vc nd(cap); repi(i, sz) nd[i] = std::move((*this)[i]); d.swap(nd), l = 0; } void prepare_push() { if (sz == SZ(d)) extend(max(1, 2 * sz)); } public: void reserve(int n) { assert(n >= 0); if (n > SZ(d)) extend(n); } template I size() const ; bool empty() const { return sz == 0; } void push_front(const T &x) ; void push_back(const T &x) { prepare_push(); d[index(sz)] = x, sz++; } const T &front() const ; T &front() { assert(!empty()); return d[l]; } const T &back() const ; T &back() ; void pop_front() { assert(!empty()); if (++l == SZ(d)) l = 0; sz--; } void pop_back() ; void clear() ; const T &operator[](int i) const ; T &operator[](int i) { return d[index(i)]; } const T &at(int i) const ; T &at(int i) ; vc content() const ; }; namespace internal { template bool spfa_relax(const Graph &g, vc &dists, const vc &sources, const Dist &infty, const Update &update) { const int n = g.size(); MyDeque que; que.reserve(n); vc queued(n, false); vc length(n, 0); for (int v : sources) que.push_back(v), queued[v] = true; bool finite = true; while (!que.empty()) { const int v = que.front(); que.pop_front(); queued[v] = false; fec(e : g.out_edges(v)) { const Dist nd = !stop_on_negative_cycle && dists[v] == -infty ? -infty : dists[v] + e.cost; if (!(nd < dists[e.to])) continue; if constexpr (stop_on_negative_cycle) if (length[v] + 1 >= n) return false; if (!stop_on_negative_cycle && (dists[v] == -infty || length[v] + 1 >= n)) { finite = false; dists[e.to] = -infty; update(e.to, Edge{}); } else { dists[e.to] = nd; length[e.to] = length[v] + 1; update(e.to, e); } if (!queued[e.to]) que.push_back(e.to), queued[e.to] = true; } } return finite; } } template struct MyQueue { private: vc d; int pos = 0; public: void reserve(int n) ; template I size() const ; bool empty() const { return pos == SZ(d); } void push(const T &t) { d.eb(t); } T front() const ; T &front() { return d[pos]; } void clear() ; void pop() { pos++; } T operator[](int i) const ; T &operator[](int i) ; T at(int i) const ; T &at(int i) ; vc content() ; vc content() const ; }; template > class FibonacciHeap { struct Node { Key key{}; int parent = -1, child = -1, prev = -1, next = -1, degree = 0; bool marked = false, present = false; CPP_DUMP_DEFINE_DATA(key, parent, child, prev, next, degree, marked, present); }; vc nodes; vc roots, degrees; Compare comp; int minimum = -1, count = 0; void detach(int v) ; void insert_after(int u, int v) ; void add_root(int v) ; void cut(int v, int p) ; public: CPP_DUMP_DEFINE_DATA(minimum, count, nodes); explicit FibonacciHeap(int n = 0, Compare comp = Compare{}) : nodes(n), comp(std::move(comp)) {} int size() const ; bool empty() const ; bool contains(int id) const ; const Key &key(int id) const ; pair top() const ; void push(int id, const Key &key) ; void decrease_key(int id, const Key &key) ; #line 5148 void push_or_decrease(int id, const Key &key) ; void pop() ; #line 5200 void clear() ; }; //! 参考: https://hitonanode.github.io/cplib-cpp/graph/shortest_path.hpp template struct ShortestPath { using Dist = decay_t::cost)>; private: const Graph &g; static constexpr decltype(auto) inf() { return resolved_infty(); } vc dists; vc> prv; vc sources; bool solved_all = false; template void init_solve(const Starts &starts, int t) { const int n = g.size(); solved_all = (t == -1); dists.assign(n, inf()); prv.assign(n, {}); sources.clear(); for (auto s : starts) { assert(0 <= s && u128(s) < u128(n)); if (dists[s] == inf()) { dists[s] = 0; sources.eb(int(s)); } } } public: CPP_DUMP_DEFINE_DATA(sources, dists, prv, solved_all); explicit ShortestPath(const Graph &g) : g(g) {} ShortestPath(const Graph &&) = delete; vc bfs(int s, int t = -1) ; template ()))> vc bfs(const Starts &s, int t = -1) { init_solve(s, t); MyQueue que; for (int v : sources) que.push(v); while (!que.empty()) { auto v = que.front(); que.pop(); if (v == t) break; fe(e : g.out_edges(v)) { if (chmin(dists[e.to], dists[v] + e.cost)) { prv[e.to] = e; que.push(e.to); } } } return dists; } vc bfs01(int s, int t = -1) ; template ()))> vc bfs01(const Starts &s, int t = -1) { const int n = g.size(); init_solve(s, t); vc cur = sources, nxt; vc used(n, false); while (!cur.empty() || !nxt.empty()) { if (cur.empty()) cur.swap(nxt); int v = cur.back(); cur.pop_back(); if (used[v]) continue; used[v] = true; if (v == t) break; fe(e : g.out_edges(v)) { if (chmin(dists[e.to], dists[v] + e.cost)) { prv[e.to] = e; if (e.cost == 0) cur.eb(e.to); else nxt.eb(e.to); } } } return dists; } vc dial(int s, int max_cost, int t = -1) ; template ()))> vc dial(const Starts &s, int max_cost, int t = -1) { static_assert(is_integral_ext); const int n = g.size(); assert(0 <= max_cost); init_solve(s, t); const int bcnt = max_cost + 1; vc head(bcnt, -1), nxt(n, -2), pre(n, -2); int que_size = 0; auto erase = [&](int v, int b) { const int p = pre[v], q = nxt[v]; if (p == -1) head[b] = q; else nxt[p] = q; if (q != -1) pre[q] = p; nxt[v] = pre[v] = -2; que_size--; }; auto push = [&](int v, int b) { nxt[v] = head[b], pre[v] = -1; if (head[b] != -1) pre[head[b]] = v; head[b] = v, que_size++; }; Dist cur = 0; for (int v : sources) push(v, 0); while (que_size) { int b = int(cur % bcnt); while (head[b] == -1) { cur++; if (++b == bcnt) b = 0; } const int v = head[b]; erase(v, b); assert(dists[v] == cur); if (v == t) break; fec(e : g.out_edges(v)) { Dist nd = dists[v] + e.cost; if (nd < dists[e.to]) { if (pre[e.to] != -2) erase(e.to, int(dists[e.to] % bcnt)); dists[e.to] = nd, prv[e.to] = e; push(e.to, int(nd % bcnt)); } } } return dists; } vc dijkstra(int s, int t = -1) { return dijkstra(array{s}, t); } template ()))> vc dijkstra(const Starts &s, int t = -1) { init_solve(s, t); pql> pque; for (int v : sources) pque.push({0, v}); while (!pque.empty()) { auto [d, v] = pque.top(); pque.pop(); if (v == t) break; if (dists[v] != d) continue; fec(e : g.out_edges(v)) { Dist nd = dists[v] + e.cost; if (chmin(dists[e.to], nd)) { prv[e.to] = e; pque.push({nd, e.to}); } } } return dists; } vc dijkstra_dense(int s, int t = -1) ; template ()))> vc dijkstra_dense(const Starts &s, int t = -1) { const int n = g.size(); init_solve(s, t); vc ok(n, false); repi(_, n) { Dist mn = inf(); int v = -1; repi(u, n) if (!ok[u] && chmin(mn, dists[u])) v = u; if (v == -1) break; if (v == t) break; ok[v] = true; fec(e : g.out_edges(v)) { if (chmin(dists[e.to], dists[v] + e.cost)) prv[e.to] = e; } } return dists; } vc dijkstra_fibonacci(int s, int t = -1) ; template ()))> vc dijkstra_fibonacci(const Starts &s, int t = -1) ; #line 5468 vc bellman_ford(int s) ; template ()))> vc bellman_ford(const Starts &s) { const int n = g.size(); init_solve(s, -1); repi(t, 2 * n) { bool changed = false; repi(v, n) { if (dists[v] == inf()) continue; fec(e : g.out_edges(v)) { Dist nd = dists[v] == -inf() ? -inf() : dists[v] + e.cost; if (dists[e.to] > nd) { changed = true; prv[e.to] = e; if (t == n - 1) dists[e.to] = -inf(); else dists[e.to] = nd; } } } if (!changed) break; } repi(v, n) if (dists[v] == -inf()) prv[v] = {}; return dists; } vc spfa(int s) ; template ()))> vc spfa(const Starts &s) ; vc solve(int s, int t = -1) { return solve(array{s}, t); } template ()))> vc solve(const Starts &s, int t = -1) { if constexpr (is_void_v) return bfs(s, t); else { bool neg = false; int zcnt = 0; Dist wplus1 = -inf(); Dist max_cost = 0; bool wpluscnt_geq2 = false; repi(v, g.size()) fec(e : g.out_edges(v)) { if (e.cost < 0) { neg = true; break; } chmax(max_cost, e.cost); } repi(v, g.size()) fec(e : g.out_edges(v)) { if (e.cost == 0) zcnt++; if (e.cost > 0) { if (wplus1 < 0) wplus1 = e.cost; else if (wplus1 != e.cost) { wpluscnt_geq2 = true; break; } } } if (neg) return bellman_ford(s); else if (wpluscnt_geq2) { const ll n = g.size(), m = g.num_of_edges(); if (n * n < (m << 4)) return dijkstra_dense(s, t); else { if constexpr (is_integral_ext) { const u128 c = u128(max_cost); const ull lg = max(1, bit_width(ull(n)) - 1); if (c <= u128(m) * lg / u128(n)) return dial(s, int(c), t); } return dijkstra(s, t); } } else { if (zcnt == 0) return bfs(s, t); else return bfs01(s, t); } } } vc> prev_edges() const { const int n = g.size(); assert(SZ(dists) == n && "solve(s, t) is not called"); return prv; } optional>> path_edge(int t) const ; #line 5615 optional> path_vertex(int t) const ; #line 5633 template vc count_paths() const ; #line 5679 }; template struct AllPairsShortestPath { using Dist = typename ShortestPath::Dist; using Matrix = vvc; private: using SP = ShortestPath; const Graph &g; static constexpr decltype(auto) inf() { return resolved_infty(); } Matrix dist; vvc prev; vc> by_id; bool negative = false, solved = false; enum class Method { repeated_sssp, floyd_warshall, johnson }; Method select_method() const { if constexpr (is_void_v) return Method::repeated_sssp; bool neg = false, multiple_positive = false, have_positive = false; Dist positive = 0; repi(v, g.size()) fec(e : g.out_edges(v)) { neg |= e.cost < Dist(0); if (e.cost > Dist(0)) { if (have_positive && e.cost != positive) multiple_positive = true; positive = e.cost, have_positive = true; } } if (!neg && !multiple_positive) return Method::repeated_sssp; const ll n = g.size(), m = g.num_of_edges(); if (n * n < 16 * m) return Method::floyd_warshall; if (neg) return Method::johnson; return Method::repeated_sssp; } void init_distances() { const int n = g.size(); dist.assign(n, vc(n, inf())); prev.assign(n, vc(n, -1)); } void init(bool allocate_distances = true) { negative = false, solved = true; dist.clear(), prev.clear(); if (allocate_distances) init_distances(); by_id.resize(g.num_of_edges()); fec(e : g.edges()) by_id[e.index] = e; } optional> potentials() const { const int n = g.size(); bool neg = false; for (int v = 0; v < n && !neg; v++) fec(e : g.out_edges(v)) if (e.cost < Dist(0)) { neg = true; break; } if (!neg) return vc(n, Dist(0)); vc starts(n); iota(starts.begin(), starts.end(), 0); vc h(n, Dist(0)); if (!internal::spfa_relax(g, h, starts, Dist(inf()), [](int, const Edge &) {})) return nullopt; return h; } Edge ending_at(int id, int t) const ; public: CPP_DUMP_DEFINE_DATA(dist, prev, by_id, negative, solved); explicit AllPairsShortestPath(const Graph &g) : g(g) {} AllPairsShortestPath(const Graph &&) = delete; const Matrix &solve() { const auto method = select_method(); if (method == Method::floyd_warshall) return floyd_warshall(); if (method == Method::johnson) return johnson(); return repeated_sssp(); } template bool for_each_source(const F &f) const ; #line 5801 const Matrix &repeated_sssp() { init(); fec(e : by_id) assert(e.cost >= Dist(0)); SP sp(g); repi(s, g.size()) { dist[s] = sp.solve(s); const auto row = sp.prev_edges(); repi(t, g.size()) prev[s][t] = row[t].index; } return dist; } const Matrix &floyd_warshall() { init(); const int n = g.size(); repi(v, n) dist[v][v] = 0; repi(v, n) fec(e : g.out_edges(v)) { if (chmin(dist[v][e.to], e.cost)) prev[v][e.to] = e.index; } if constexpr (is_integral_ext) { bool nonnegative = inf() <= numeric_limits::max() / 2 && ll(n) * n < 16 * ll(by_id.size()); fec(e : by_id) if (e.cost < Dist(0)) nonnegative = false; if (nonnegative) { repi(k, n) repi(i, n) { auto &row = dist[i]; const auto &via = dist[k]; const Dist a = row[k]; if (a == inf()) continue; auto &parent = prev[i]; const auto &via_parent = prev[k]; repi(j, n) if (chmin(row[j], a + via[j])) parent[j] = via_parent[j]; } return dist; } } repi(k, n) repi(i, n) { if (dist[i][k] == inf()) continue; repi(j, n) { if (dist[k][j] == inf()) continue; const Dist &a = dist[i][k], &b = dist[k][j]; Dist nd; if (a == -inf() || b == -inf()) nd = -inf(); else if (b < Dist(0) && a < -inf() - b) nd = -inf(); else if (b > Dist(0) && a > inf() - b) nd = inf(); else nd = a + b; if (chmin(dist[i][j], nd)) prev[i][j] = prev[k][j]; } } repi(k, n) if (dist[k][k] < Dist(0)) { negative = true; repi(s, n) if (dist[s][k] != inf()) repi(t, n) if (dist[k][t] != inf()) dist[s][t] = -inf(), prev[s][t] = -1; } return dist; } const Matrix &johnson() { if constexpr (is_void_v) return repeated_sssp(); else { init(false); const int n = g.size(); const auto potential = potentials(); if (!potential) return floyd_warshall(); const auto &h = *potential; auto reweighted = by_id; for (auto &e : reweighted) e.cost = e.cost + h[e.from] - h[e.to]; Graph reweighted_graph(n, reweighted); SP sp(reweighted_graph); init_distances(); repi(s, n) { dist[s] = sp.dijkstra(s); const auto row = sp.prev_edges(); repi(t, n) { if (dist[s][t] != inf()) dist[s][t] = dist[s][t] - h[s] + h[t]; prev[s][t] = row[t].index; } } return dist; } } bool negative_cycle() const ; vc> prev_edges(int s) const ; optional>> path_edge(int s, int t) const ; #line 5933 optional> path_vertex(int s, int t) const ; #line 5950 }; vl naive(ll N, ll M, ll Q, vl S, vtlll UVW, vpll AB) { vc> E; rep(e, M) { auto [u, v, w] = UVW[e]; ll ww = mul_limited(w, pow_limited(2, e + 1)); E.eb(u, v, ww); } rep(u, N) rep(v, N) E.eb(u, v, S[u] + S[v]); GraphUndirected G(N, E); AllPairsShortestPath apsp(G); auto res = apsp.solve(); vl anss; rep(q, Q) { auto [a, b] = AB[q]; anss.eb(res[a][b]); } return anss; } vl solve(ll N, ll M, ll Q, vl S, vtlll UVW, vpll AB) { UnionFind> uf(N); fec([ u, v, w ] : UVW) if (w == 0) uf.merge(u, v); rep(v, N) chmin(S[uf.leader(v)], S[v]); vl vs; rep(e, min(M, 62LL)) { auto [u, v, w] = UVW[e]; vs.eb(uf.leader(u)), vs.eb(uf.leader(v)); } sortunique(vs); const ll K = vs.size(); vvl D(K, vl(K, INF)); rep(i, K) D[i][i] = 0; rep(i, K) rep(j, K) { chmin(D[i][j], S[vs[i]] + S[vs[j]]); chmin(D[j][i], S[vs[i]] + S[vs[j]]); } rep(e, min(M, 62LL)) { auto [u, v, w] = UVW[e]; u = uf.leader(u), v = uf.leader(v); ll i = LB(vs, u), j = LB(vs, v); ll k = mul_limited(w, 1LL << (e + 1)); chmin(D[i][j], k); chmin(D[j][i], k); } rep(k, K) rep(i, K) rep(j, K) chmin(D[i][j], D[i][k] + D[k][j]); dump(D | cp::index()); vl anss; rep(q, Q) { auto [a, b] = AB[q]; a = uf.leader(a), b = uf.leader(b); ll ans = S[a] + S[b]; if (binary_search(ALL(vs), a) && binary_search(ALL(vs), b)) { ll i = LB(vs, a), j = LB(vs, b); chmin(ans, D[i][j]); } if (binary_search(ALL(vs), a)) { ll i = LB(vs, a); rep(j, K) chmin(ans, S[b] + S[vs[j]] + D[i][j]); } if (binary_search(ALL(vs), b)) { ll j = LB(vs, b); rep(i, K) chmin(ans, S[a] + S[vs[i]] + D[i][j]); } if (a == b) chmin(ans, 0); anss.eb(ans); } return anss; } void main2() { LL(N, M, Q); VEC(ll, N, S); VEC(tlll, M, UVW); offset(UVW, tlll{-1, -1, 0}); VEC(pll, Q, AB); offset(AB, pll{-1, -1}); PRINTV(solve(N, M, Q, S, UVW, AB)); } void test() { //* #line 6114 //*/ } 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 6161 CERR("\n[SINGLE_TESTCASE]\n\n", "36"); main2(); #line 6176 } }; Main main_dummy; int main() {} // submit-code: hash=71434cb5e6ce source=71434cb5e6ce44eb340ea415559df4eab7d1e43e0e2d1739011fd8e00c7f6009 input=04a10350e85ecbc405de56bdff0212b9ff2843cb2fc5ab37195239020fee802d body=c47e2e629419af1033c6657be56e008d0792f1ee44fa55519a387b425a17a85c