結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2020-02-09 17:01:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 444 ms / 2,000 ms |
コード長 | 53,320 bytes |
コンパイル時間 | 3,571 ms |
コンパイル使用メモリ | 247,144 KB |
最終ジャッジ日時 | 2025-01-08 23:21:20 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
/****/#define ASSERT_LV 1// header {{{#ifndef ASSERT_LV# define ASSERT_LV 1#endif#if ASSERT_LV == 0# define NDEBUG#endif#if defined(__GNUC__) && !defined(__clang__)#include <bits/stdc++.h>#else#include <cassert>#include <cctype>#include <cerrno>#include <cfloat>#include <ciso646>#include <climits>//#include <clocale>#include <cmath>//#include <csetjmp>//#include <csignal>#include <cstdarg>#include <cstddef>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>//#include <cwchar>//#include <cwctype>#if __cplusplus >= 201103L//#include <ccomplex>#include <cfenv>#include <cinttypes>//#include <cstdalign>//#include <cstdbool>#include <cstdint>//#include <ctgmath>//#include <cuchar>#endif#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <exception>#include <fstream>#include <functional>#include <iomanip>#include <ios>#include <iosfwd>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>//#include <locale>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <set>#include <sstream>#include <stack>#include <stdexcept>#include <streambuf>#include <string>#include <typeinfo>#include <utility>#include <valarray>#include <vector>#if __cplusplus >= 201103L#include <array>//#include <atomic>#include <chrono>//#include <codecvt>//#include <condition_variable>#include <forward_list>//#include <future>#include <initializer_list>//#include <mutex>#include <random>#include <ratio>#include <regex>#include <scoped_allocator>//#include <system_error>#include <thread>#include <tuple>#include <typeindex>#include <type_traits>#include <unordered_map>#include <unordered_set>#endif#if __cplusplus >= 201402L//#include <shared_mutex>#endif#if __cplusplus >= 201703L#include <any>//#include <charconv>//#include <execution>//#include <filesystem>#include <optional>//#include <memory_resource>#include <string_view>#include <variant>#endif#endifusing namespace std;using i8 = int8_t;using u8 = uint8_t;using i16 = int16_t;using u16 = uint16_t;using i32 = int32_t;using u32 = uint32_t;using i64 = int64_t;using u64 = uint64_t;#ifdef __SIZEOF_INT128__using i128 = __int128;using u128 = unsigned __int128;#endifusing f32 = float;using f64 = double;using f80 = long double;template<class T> constexpr T PROCON_INF();template<> constexpr i32 PROCON_INF<i32>() { return 1'010'000'011; }template<> constexpr i64 PROCON_INF<i64>() { return INT64_C(1'010'000'000'000'000'017); }template<> constexpr f32 PROCON_INF<f32>() { return 1e19F; }template<> constexpr f64 PROCON_INF<f64>() { return 1e100; }template<> constexpr f80 PROCON_INF<f80>() { return 1e100L; }// }}}using Int = i64;using Real = f80;constexpr Int MOD = 1'000'000'007;//constexpr Int MOD = 998'244'353;constexpr Real EPS = Real(1e-10L);constexpr int COUT_PREC = 15;constexpr bool COUT_AUTOFLUSH = false;// procon {{{static_assert(is_same<Int,i64>::value || is_same<Int,i32>::value, "");static_assert(is_same<Real,f80>::value || is_same<Real,f64>::value || is_same<Real,f32>::value, "");#define CPP_STR(x) CPP_STR_I(x)#define CPP_CAT(x,y) CPP_CAT_I(x,y)#define CPP_STR_I(args...) #args#define CPP_CAT_I(x,y) x ## y#define SFINAE(pred...) std::enable_if_t<(pred), std::nullptr_t> = nullptr#define ASSERT(expr...) assert((expr))#if defined(PROCON_LOCAL) || ASSERT_LV >= 2# define ASSERT_LOCAL(expr...) assert((expr))#else# define ASSERT_LOCAL(expr...)#endifconstexpr Int INF = PROCON_INF<Int>();constexpr Real FINF = PROCON_INF<Real>();constexpr Real PI = Real(3.141592653589793238462643383279502884197L);template<class T> constexpr T SQRT_MAX();template<> constexpr i32 SQRT_MAX<i32>() { return 46340; }template<> constexpr i64 SQRT_MAX<i64>() { return INT64_C(3037000499); }template<class T, SFINAE(is_signed<T>::value)>constexpr T ABS(T x) noexcept {return x < 0 ? -x : x;}constexpr bool LT_EPS(Real lhs, Real rhs, Real eps=EPS) { return lhs < rhs-eps; }constexpr bool GT_EPS(Real lhs, Real rhs, Real eps=EPS) { return lhs > rhs+eps; }constexpr bool EQ_EPS(Real lhs, Real rhs, Real eps=EPS) { return ABS(lhs-rhs) <= eps; }constexpr bool EQ_EXACT(Real lhs, Real rhs) {#pragma GCC diagnostic push#pragma GCC diagnostic ignored "-Wfloat-equal"return lhs == rhs;#pragma GCC diagnostic pop}#define FOR(i, start, end) for(Int i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)#define REP(i, n) FOR(i, 0, n)#define LOOP(n) REP(CPP_CAT(macro_loop_counter,__COUNTER__), n)#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))#define SLICE(f,c,l,r,...) (([&](decltype((c)) cccc, decltype((l)) llll, decltype((r)) rrrr) {\auto iiii = llll <= rrrr ? std::begin(cccc)+llll : std::end(cccc);\auto jjjj = llll <= rrrr ? std::begin(cccc)+rrrr : std::end(cccc);\return (f)(iiii, jjjj, ## __VA_ARGS__);\})(c,l,r))#define LIFT(f) ([](auto&&... args) -> decltype(auto) { return (f)(std::forward<decltype(args)>(args)...); })template<class C>constexpr Int SIZE(const C& c) noexcept { return Int(c.size()); }template<class T, size_t N>constexpr Int SIZE(const T (&)[N]) noexcept { return Int(N); }constexpr bool is_odd (Int x) { return x%2 != 0; }constexpr bool is_even(Int x) { return x%2 == 0; }constexpr Int PARITY(Int x) { return x%2==0 ? 0 : 1; }template<class T>constexpr Int CMP(T x, T y) noexcept { return (y<x) - (x<y); }template<class T>constexpr Int SGN(T x) noexcept { return CMP(x,T(0)); }template<class T1, class T2, class Comp=less<>,SFINAE(is_integral<T1>::value &&is_integral<T2>::value &&is_signed<T1>::value != is_unsigned<T2>::value)>constexpr auto MAX(T1 x, T2 y, Comp comp={}) {return max<common_type_t<T1,T2>>({x,y}, comp);}template<class T1, class T2, class Comp=less<>,SFINAE(is_floating_point<T1>::value &&is_floating_point<T2>::value)>constexpr auto MAX(T1 x, T2 y, Comp comp={}) {return max<common_type_t<T1,T2>>({x,y}, comp);}template<class T, class Comp=less<>>constexpr const T& MAX(const T& x, const T& y, Comp comp={}) {return max(x, y, comp);}template<class T, class Comp=less<>>constexpr T MAX(initializer_list<T> ilist, Comp comp={}) {return max(ilist, comp);}template<class T1, class T2, class Comp=less<>,SFINAE(is_integral<T1>::value &&is_integral<T2>::value &&is_signed<T1>::value != is_unsigned<T2>::value)>constexpr auto MIN(T1 x, T2 y, Comp comp={}) {return min<common_type_t<T1,T2>>({x,y}, comp);}template<class T1, class T2, class Comp=less<>,SFINAE(is_floating_point<T1>::value &&is_floating_point<T2>::value)>constexpr auto MIN(T1 x, T2 y, Comp comp={}) {return min<common_type_t<T1,T2>>({x,y}, comp);}template<class T, class Comp=less<>>constexpr const T& MIN(const T& x, const T& y, Comp comp={}) {return min(x, y, comp);}template<class T, class Comp=less<>>constexpr T MIN(initializer_list<T> ilist, Comp comp={}) {return min(ilist, comp);}template<class T, class U, class Comp=less<>>constexpr bool chmax(T& xmax, const U& x, Comp comp={}) noexcept {if(comp(xmax, x)) {xmax = x;return true;}return false;}template<class T, class U, class Comp=less<>>constexpr bool chmin(T& xmin, const U& x, Comp comp={}) noexcept {if(comp(x, xmin)) {xmin = x;return true;}return false;}template<class BinaryFunc, class UnaryFunc>auto ON(BinaryFunc&& bf, UnaryFunc&& uf) {return [bf=forward<BinaryFunc>(bf),uf=forward<UnaryFunc>(uf)](const auto& x, const auto& y) {return bf(uf(x), uf(y));};}template<class F>auto LT_ON(F&& f) {return ON(less<>{}, forward<F>(f));}template<class F>auto GT_ON(F&& f) {return ON(greater<>{}, forward<F>(f));}template<class F>auto NOT_FN(F&& f) {return [f=forward<F>(f)](auto&&... args) -> bool { return !f(forward<decltype(args)>(args)...); };}struct IDENTITY {using is_transparent = void;template<class T>constexpr decltype(auto) operator()(T&& x) const { return forward<T>(x); }};// ビット演算 {{{// 引数は [-INF,INF] のみ想定constexpr Int BIT_I(Int i) {return Int(1) << i;}constexpr Int BIT_I_1(Int i) {return BIT_I(i) - 1;}constexpr Int BIT_GET(Int x, Int i) {return x & BIT_I(i);}constexpr bool BIT_TEST(Int x, Int i) {return BIT_GET(x,i) != 0;}constexpr Int BIT_SET(Int x, Int i) {return x | BIT_I(i);}constexpr Int BIT_CLEAR(Int x, Int i) {return x & ~BIT_I(i);}constexpr Int BIT_FLIP(Int x, Int i) {return x ^ BIT_I(i);}constexpr Int BIT_ASSIGN(Int x, Int i, bool b) {return b ? BIT_SET(x,i) : BIT_CLEAR(x,i);}/*constexpr*/ Int BIT_COUNT_LEADING_ZEROS(Int x) {if(is_same<Int,i64>::value)return x==0 ? 64 : __builtin_clzll(u64(x));else if(is_same<Int,i32>::value)return x==0 ? 32 : __builtin_clz(u32(x));ASSERT(false);}/*constexpr*/ Int BIT_COUNT_TRAILING_ZEROS(Int x) {if(is_same<Int,i64>::value)return x==0 ? 64 : __builtin_ctzll(u64(x));else if(is_same<Int,i32>::value)return x==0 ? 32 : __builtin_clz(u32(x));ASSERT(false);}/*constexpr*/ Int BIT_COUNT_ONES(Int x) {if(is_same<Int,i64>::value)return __builtin_popcountll(u64(x));else if(is_same<Int,i32>::value)return __builtin_popcount(u32(x));ASSERT(false);}// 1の個数が奇数なら1, 偶数なら0を返す/*constexpr*/ Int BIT_PARITY(Int x) {if(is_same<Int,i64>::value)return __builtin_parityll(u64(x));else if(is_same<Int,i32>::value)return __builtin_parity(u32(x));ASSERT(false);}// X ⊆ {0,1,...,n-1}, |X| = k なる部分集合 X を昇順に列挙する// comb(n,k) 個//// ```// Int x = BIT_I_1(3);// do {// // ...// } while(BIT_NEXT_SET_SIZED(x, 10));// ```/*constexpr*/ bool BIT_NEXT_SET_SIZED(Int& x, Int n) {if(x == 0) return false;Int t = (x|(x-1)) + 1;x = t | ((~t&(t-1)) >> (BIT_COUNT_TRAILING_ZEROS(x)+1));return x < BIT_I(n);}// 集合 Y の部分集合 X を昇順に列挙する// 2^|Y| 個//// ```// Int y = 0b10101;// Int x = 0;// do {// // ...// } while(BIT_NEXT_SUBSET(x, y));// ```constexpr bool BIT_NEXT_SUBSET(Int& x, Int y) {if(x == y) return false;x = (x-y) & y;return true;}// 集合 Y の部分集合 X を降順に列挙する// 2^|Y| 個//// ```// Int y = 0b10101;// Int x = y;// do {// // ...// } while(BIT_PREV_SUBSET(x, y));// ```constexpr bool BIT_PREV_SUBSET(Int& x, Int y) {if(x == 0) return false;x = (x-1) & y;return true;}// 集合 Y を包含する集合 X ⊆ {0,1,...,n-1} を昇順に列挙する// 2^(n-|Y|) 個//// ```// Int y = 0b00010101;// Int x = y;// do {// // ...// } while(BIT_NEXT_SUPERSET(x, 8, y));// ```constexpr bool BIT_NEXT_SUPERSET(Int& x, Int n, Int y) {x = (x+1) | y;return x < BIT_I(n);}// }}}// lo:OK, hi:NGtemplate<class Pred>/*constexpr*/ Int bisect_integer(Int lo, Int hi, Pred pred) {ASSERT(lo < hi);while(lo+1 < hi) {Int mid = (lo+hi) / 2;if(pred(mid))lo = mid;elsehi = mid;}return lo;}template<class Pred>/*constexpr*/ Real bisect_real(Real lo, Real hi, Pred pred, Real eps=EPS) {ASSERT_LOCAL(!GT_EPS(lo,hi,eps));if(lo > hi) swap(lo, hi);while(!EQ_EPS(lo,hi,eps)) {Real mid = (lo+hi) / 2;if(pred(mid))lo = mid;elsehi = mid;}return lo;}template<class Monoid>/*constexpr*/ Monoid fastpow(const Monoid& x, Int e, const Monoid& unity) {ASSERT(e >= 0);Monoid res = unity;Monoid cur = x;while(e > 0) {if(e & 1)res *= cur;cur *= cur;e >>= 1;}return res;}/*constexpr*/ Int ipow(Int x, Int e) {return fastpow<Int>(x,e,1);}/*constexpr*/ Int sqrt_floor(Int x) {ASSERT(x >= 0);Int lo = 0;Int hi = MIN(x/2+2, SQRT_MAX<Int>()+1);return bisect_integer(lo, hi, [x](Int r) { return r*r <= x; });}/*constexpr*/ Int sqrt_ceil(Int x) {Int r = sqrt_floor(x);return r*r == x ? r : r+1;}/*constexpr*/ Int log2_ceil(Int x) {ASSERT(x > 0);if(is_same<Int,i64>::value)return 64 - BIT_COUNT_LEADING_ZEROS(x-1);else if(is_same<Int,i32>::value)return 32 - BIT_COUNT_LEADING_ZEROS(x-1);ASSERT(false);}/*constexpr*/ Int log2_floor(Int x) {ASSERT(x > 0);if(is_same<Int,i64>::value)return 63 - BIT_COUNT_LEADING_ZEROS(x);else if(is_same<Int,i32>::value)return 31 - BIT_COUNT_LEADING_ZEROS(x);ASSERT(false);}// x > 0/*constexpr*/ Int pow2_ceil(Int x) {return BIT_I(log2_ceil(x));}// x > 0/*constexpr*/ Int pow2_floor(Int x) {return BIT_I(log2_floor(x));}// Haskell の divMod と同じconstexpr pair<Int,Int> divmod(Int a, Int b) {Int q = a / b;Int r = a % b;if((b>0 && r<0) || (b<0 && r>0)) {--q;r += b;}return {q,r};}constexpr Int div_ceil(Int a, Int b) {Int q = a / b;Int r = a % b;if((b>0 && r>0) || (b<0 && r<0))++q;return q;}constexpr Int div_floor(Int a, Int b) {return divmod(a,b).first;}constexpr Int modulo(Int a, Int b) {return divmod(a,b).second;}/*constexpr*/ Int align_ceil(Int x, Int align) {ASSERT(align > 0);return div_ceil(x,align) * align;}/*constexpr*/ Int align_floor(Int x, Int align) {ASSERT(align > 0);return div_floor(x,align) * align;}template<class InputIt, class BinaryOp>auto FOLD(InputIt first, InputIt last,typename iterator_traits<InputIt>::value_type init,BinaryOp op){for(; first != last; ++first)init = op(move(init), *first);return init;}template<class InputIt, class BinaryOp>auto FOLD1(InputIt first, InputIt last, BinaryOp op) {auto init = *first++;return FOLD(first, last, init, op);}template<class InputIt>auto SUM(InputIt first, InputIt last) {return FOLD1(first, last, plus<>{});}template<class C>void UNIQ(C& c) {c.erase(ALL(unique,c), end(c));}template<class C>void SORT_UNIQ(C& c) {ALL(sort, c);UNIQ(c);}[[noreturn]] void EXIT() {cout.flush();#ifdef PROCON_LOCALcerr.flush();exit(0);#else_Exit(0);#endif}// tuple {{{template<Int I=0, class F, class... TS, SFINAE(sizeof...(TS) == I)>void tuple_enumerate(tuple<TS...>&, F&&) {}template<Int I=0, class F, class... TS, SFINAE(sizeof...(TS) > I)>void tuple_enumerate(tuple<TS...>& t, F&& f) {f(I, get<I>(t));tuple_enumerate<I+1>(t, forward<F>(f));}template<Int I=0, class F, class... TS, SFINAE(sizeof...(TS) == I)>void tuple_enumerate(const tuple<TS...>&, F&&) {}template<Int I=0, class F, class... TS, SFINAE(sizeof...(TS) > I)>void tuple_enumerate(const tuple<TS...>& t, F&& f) {f(I, get<I>(t));tuple_enumerate<I+1>(t, forward<F>(f));}// }}}// container {{{template<class T> struct is_container : false_type {};template<class T, size_t N> struct is_container<array<T,N>> : true_type {};template<class... Args> struct is_container<vector<Args...>> : true_type {};template<class... Args> struct is_container<deque<Args...>> : true_type {};template<class... Args> struct is_container<list<Args...>> : true_type {};template<class... Args> struct is_container<forward_list<Args...>> : true_type {};template<class... Args> struct is_container<set<Args...>> : true_type {};template<class... Args> struct is_container<multiset<Args...>> : true_type {};template<class... Args> struct is_container<unordered_set<Args...>> : true_type {};template<class... Args> struct is_container<unordered_multiset<Args...>> : true_type {};template<class... Args> struct is_container<map<Args...>> : true_type {};template<class... Args> struct is_container<multimap<Args...>> : true_type {};template<class... Args> struct is_container<unordered_map<Args...>> : true_type {};template<class... Args> struct is_container<unordered_multimap<Args...>> : true_type {};template<class T, class Enable=void>struct ProconHash {size_t operator()(const T& x) const noexcept {return hash<T>{}(x);}};template<class T>size_t procon_hash_value(const T& x) noexcept {return ProconHash<T>{}(x);}size_t procon_hash_combine(size_t h1, size_t h2) noexcept {constexpr size_t M = UINT64_C(0xc6a4a7935bd1e995);constexpr int R = 47;h2 *= M;h2 ^= h2 >> R;h2 *= M;h1 ^= h2;h1 *= M;h1 += 0xe6546b64;return h1;}template<class T1, class T2>struct ProconHash<pair<T1,T2>> {size_t operator()(const pair<T1,T2>& p) const noexcept {size_t h1 = procon_hash_value(p.first);size_t h2 = procon_hash_value(p.second);return procon_hash_combine(h1, h2);}};template<class... TS>struct ProconHash<tuple<TS...>> {size_t operator()(const tuple<TS...>& t) const noexcept {size_t h = 0;tuple_enumerate(t, [&h](Int, const auto& e) {h = procon_hash_combine(h, procon_hash_value(e));});return h;}};template<class C>struct ProconHash<C,enable_if_t<is_container<C>::value>> {size_t operator()(const C& c) const noexcept {size_t h = 0;for(const auto& e : c)h = procon_hash_combine(h, procon_hash_value(e));return h;}};template<class T, class Hash=ProconHash<T>, class Eq=equal_to<T>>using HashSet = unordered_set<T,Hash,Eq>;template<class K, class V, class Hash=ProconHash<K>, class Eq=equal_to<K>>using HashMap = unordered_map<K,V,Hash,Eq>;template<class T, class Hash=ProconHash<T>, class Eq=equal_to<T>>using HashMultiset = unordered_multiset<T,Hash,Eq>;template<class K, class V, class Hash=ProconHash<K>, class Eq=equal_to<K>>using HashMultimap = unordered_multimap<K,V,Hash,Eq>;template<class T>auto vec_make(Int n, T x) {return vector<T>(n, x);}template<class T, class... Args, SFINAE(sizeof...(Args) >= 2)>auto vec_make(Int n, Args... args) {auto inner = vec_make<T>(args...);return vector<decltype(inner)>(n, inner);}template<class T>auto vec_reserve(Int cap) {vector<T> res;res.reserve(cap);return res;}template<class T=Int>auto vec_iota(Int n, T init={}) {vector<Int> res(n);ALL(iota, res, init);return res;}template<class ForwardIt, class BinaryOp>auto vec_scan(ForwardIt first, ForwardIt last,typename iterator_traits<ForwardIt>::value_type init,BinaryOp op){using T = typename iterator_traits<ForwardIt>::value_type;auto res = vec_reserve<T>(distance(first,last)+1);res.emplace_back(init);for(; first != last; ++first) {init = op(move(init), *first);res.emplace_back(init);}return res;}template<class ForwardIt>auto vec_cum(ForwardIt first, ForwardIt last) {using T = typename iterator_traits<ForwardIt>::value_type;return vec_scan(first, last, T{}, plus<>{});}template<class T, class Comp, class Cont=vector<T>>auto priority_queue_make(const Comp& comp, Cont&& cont={}) {return priority_queue<T,remove_reference_t<Cont>,Comp>(comp, forward<Cont>(cont));}template<class T, class Comp>auto priority_queue_reserve(const Comp& comp, Int cap) {return priority_queue<T,vector<T>,Comp>(comp, vec_reserve<T>(cap));}template<class T, size_t N, size_t... NS>struct ArrayType {using type = array<class ArrayType<T,NS...>::type,N>;};template<class T, size_t N>struct ArrayType<T,N> {using type = array<T,N>;};template<class T, size_t... NS>using Array = typename ArrayType<T,NS...>::type;template<class T, size_t N>T& array_at(Array<T,N>& ary, Int i) {return ary[i];}template<class T, size_t N, size_t... NS, class... Args>T& array_at(Array<T,N,NS...>& ary, Int i, Args... args) {return array_at<T,NS...>(ary[i], args...);}template<class T, size_t N>const T& array_at(const Array<T,N>& ary, Int i) {return ary[i];}template<class T, size_t N, size_t... NS, class... Args>const T& array_at(const Array<T,N,NS...>& ary, Int i, Args... args) {return array_at<T,NS...>(ary[i], args...);}template<class T, class C>T POP(stack<T,C>& stk) {T x = stk.top(); stk.pop();return x;}template<class T, class C>T POP(queue<T,C>& que) {T x = que.front(); que.pop();return x;}template<class T, class C, class Comp>T POP(priority_queue<T,C,Comp>& que) {T x = que.top(); que.pop();return x;}// }}}// fixpoint {{{template<class F>class FixPoint {public:explicit constexpr FixPoint(F&& f) : f_(forward<F>(f)) {}template<class... Args>constexpr decltype(auto) operator()(Args&&... args) const {return f_(*this, forward<Args>(args)...);}private:F f_;};template<class F>constexpr decltype(auto) FIX(F&& f) {return FixPoint<F>(forward<F>(f));}template<class F, size_t... NS>class FixPointMemo {public:explicit FixPointMemo(F&& f) : f_(forward<F>(f)) {}template<class... Args>decltype(auto) operator()(Args... args) const {using R = decltype(f_(*this,args...));static Array<bool,NS...> done {};static Array<R,NS...> memo;if(!array_at<bool,NS...>(done,args...)) {array_at<R,NS...>(memo,args...) = f_(*this,args...);array_at<bool,NS...>(done,args...) = true;}return array_at<R,NS...>(memo,args...);}private:F f_;};template<size_t... NS, class F>decltype(auto) FIXMEMO(F&& f) {return FixPointMemo<F,NS...>(forward<F>(f));}// }}}// math {{{/*constexpr*/ Int GCD(Int a, Int b) noexcept {/*constexpr*/ auto f_gcd = FIX([](auto&& self, Int aa, Int bb) -> Int {if(bb == 0) return aa;return self(bb, aa%bb);});return f_gcd(ABS(a), ABS(b));}/*constexpr*/ Int LCM(Int a, Int b) noexcept {ASSERT(a != 0 && b != 0);/*constexpr*/ auto f_gcd = FIX([](auto&& self, Int aa, Int bb) -> Int {if(bb == 0) return aa;return self(bb, aa%bb);});a = ABS(a);b = ABS(b);return a / f_gcd(a,b) * b;}/*constexpr*/ tuple<Int,Int,Int> EXTGCD(Int a, Int b) noexcept {/*constexpr*/ auto impl = FIX([](auto&& self, Int aa, Int bb, Int& x, Int& y) -> Int {if(bb == 0) {x = 1; y = 0;return aa;}Int g = self(bb, aa%bb, y, x);y -= (aa/bb)*x;return g;});Int x{},y{};Int g = impl(ABS(a), ABS(b), x, y);x *= SGN(a);y *= SGN(b);return make_tuple(g, x, y);}// }}}// string {{{char chr_digit(Int n) { return char('0'+n); }Int ord_digit(char c) { return c-'0'; }char chr_lower(Int n) { return char('a'+n); }Int ord_lower(char c) { return c-'a'; }char chr_upper(Int n) { return char('A'+n); }Int ord_upper(char c) { return c-'A'; }auto str_reserve(Int cap) {string res;res.reserve(cap);return res;}// }}}// input {{{template<class T>struct Integral1 {static_assert(is_integral<T>::value && !is_same<T,bool>::value, "");};using Int1 = Integral1<Int>;template<class T, class Enable=void>struct Scan {using R = T;static R scan(istream& in) {R res;in >> res;return res;}};template<class T>struct Scan<Integral1<T>> {using R = T;static R scan(istream& in) {return Scan<R>::scan(in) - 1;}};template<class T1, class T2>struct Scan<pair<T1,T2>> {using R1 = typename Scan<T1>::R;using R2 = typename Scan<T2>::R;using R = pair<R1,R2>;static R scan(istream& in) {R1 x = Scan<T1>::scan(in);R2 y = Scan<T2>::scan(in);return {x,y};}};template<class T>auto tuple_scan_impl(istream& in) {return make_tuple(Scan<T>::scan(in));}template<class T, class... TS, SFINAE(sizeof...(TS) > 0)>auto tuple_scan_impl(istream& in) {auto head = make_tuple(Scan<T>::scan(in));return tuple_cat(head, tuple_scan_impl<TS...>(in));}template<class... TS>struct Scan<tuple<TS...>> {using R = decltype(tuple_scan_impl<TS...>(cin));static R scan(istream& in) {return tuple_scan_impl<TS...>(in);}};template<class T=Int>auto RD() {return Scan<T>::scan(cin);}template<class T=Int>auto RD1() {return RD<Integral1<T>>();}template<class T=Int>auto RD_VEC(Int n) {auto res = vec_reserve<typename Scan<T>::R>(n);LOOP(n) {res.emplace_back(RD<T>());}return res;}template<class T=Int>auto RD1_VEC(Int n) {return RD_VEC<Integral1<T>>(n);}template<class T=Int>auto RD_VEC2(Int h, Int w) {auto res = vec_reserve<vector<typename Scan<T>::R>>(h);LOOP(h) {res.emplace_back(RD_VEC<T>(w));}return res;}template<class T=Int>auto RD1_VEC2(Int h, Int w) {return RD_VEC2<Integral1<T>>(h, w);}// }}}// output {{{template<class T, class Enable=void>struct Fmt {static void fmt(ostream& out, const T& x) { out << x; }};template<class T>void fmt_write(ostream& out, const T& x) {Fmt<T>::fmt(out, x);}template<class T>string FMT_STR(const T& x) {ostringstream out;fmt_write(out, x);return out.str();}template<class... TS>struct Fmt<tuple<TS...>> {static void fmt(ostream& out, const tuple<TS...>& t) {tuple_enumerate(t, [&out](Int i, const auto& e) {if(i != 0) out << ' ';fmt_write(out, e);});}};template<class T1, class T2>struct Fmt<pair<T1,T2>> {static void fmt(ostream& out, const pair<T1,T2>& p) {return fmt_write(out, make_tuple(p.first,p.second));}};template<class C>struct Fmt<C,enable_if_t<is_container<C>::value>> {static void fmt(ostream& out, const C& c) {for(auto it = begin(c); it != end(c); ++it) {if(it != begin(c)) out << ' ';fmt_write(out, *it);}}};void PRINT() {}template<class T, class... TS>void PRINT(const T& x, const TS&... args) {fmt_write(cout, x);if(sizeof...(args) > 0) {cout << ' ';PRINT(args...);}}template<class... TS>void PRINTLN(const TS&... args) {PRINT(args...);cout << '\n';}// }}}// debug {{{template<class T, class Enable=void>struct Dbg {static void dbg(ostream& out, const T& x) { out << x; }};template<class T>void dbg_write(ostream& out, const T& x) {Dbg<T>::dbg(out, x);}template<class T>string DBG_STR(const T& x) {ostringstream out;dbg_write(out, x);return out.str();}template<>struct Dbg<Int> {static void dbg(ostream& out, Int x) {if(x == INF)out << "INF";else if(x == -INF)out << "-INF";elseout << x;}};template<>struct Dbg<Real> {static void dbg(ostream& out, Real x) {if(EQ_EXACT(x, FINF))out << "FINF";else if(EQ_EXACT(x, -FINF))out << "-FINF";elseout << x;}};template<class T, size_t N>struct Dbg<T[N]> {static void dbg(ostream& out, const T (&ary)[N]) {out << "[";REP(i, N) {if(i != 0) out << ",";dbg_write(out, ary[i]);}out << "]";}};template<size_t N>struct Dbg<char[N]> {static void dbg(ostream& out, const char (&s)[N]) {out << s;}};template<class... TS>struct Dbg<tuple<TS...>> {static void dbg(ostream& out, const tuple<TS...>& t) {out << "(";tuple_enumerate(t, [&out](Int i, const auto& e) {if(i != 0) out << ",";dbg_write(out, e);});out << ")";}};template<class T1, class T2>struct Dbg<pair<T1,T2>> {static void dbg(ostream& out, const pair<T1,T2>& p) {return dbg_write(out, make_tuple(p.first,p.second));}};template<class C>struct Dbg<C,enable_if_t<is_container<C>::value>> {static void dbg(ostream& out, const C& c) {out << "[";for(auto it = begin(c); it != end(c); ++it) {if(it != begin(c)) out << ",";dbg_write(out, *it);}out << "]";}};template<class T, class C>struct Dbg<stack<T,C>> {static void dbg(ostream& out, stack<T,C> stk) {out << "[";while(!stk.empty()) {dbg_write(out,stk.top()); stk.pop();if(!stk.empty()) out << ",";}out << "]";}};template<class T, class C>struct Dbg<queue<T,C>> {static void dbg(ostream& out, queue<T,C> que) {out << "[";while(!que.empty()) {dbg_write(out,que.front()); que.pop();if(!que.empty()) out << ",";}out << "]";}};template<class T, class C, class Comp>struct Dbg<priority_queue<T,C,Comp>> {static void dbg(ostream& out, priority_queue<T,C,Comp> que) {out << "[";while(!que.empty()) {dbg_write(out,que.top()); que.pop();if(!que.empty()) out << ",";}out << "]";}};template<class T>void DBG_IMPL(Int line, const char* expr, const T& value) {cerr << "[L " << line << "]: ";cerr << expr << " = ";dbg_write(cerr, value);cerr << "\n";}void DBG_IMPL_HELPER() {}template<class T, class... TS>void DBG_IMPL_HELPER(const T& x, const TS&... args) {dbg_write(cerr, x);if(sizeof...(args) > 0) {cerr << ",";DBG_IMPL_HELPER(args...);}}template<class... TS>void DBG_IMPL(Int line, const char* expr, const TS&... value) {cerr << "[L " << line << "]: ";cerr << "(" << expr << ") = (";DBG_IMPL_HELPER(value...);cerr << ")\n";}template<size_t N, class T, SFINAE(rank<T>::value == 0)>void DBG_DP_IMPL_HELPER(ostream& out, const T& x, const array<Int,N>&, const array<Int,N>&) {dbg_write(out, x);}template<size_t N, class T, SFINAE(rank<T>::value > 0)>void DBG_DP_IMPL_HELPER(ostream& out, const T& x, const array<Int,N>& sizes, const array<Int,N>& offs) {Int k = N - rank<T>::value;Int off = offs[k];Int siz = sizes[k];if(siz == 0) siz = extent<T>::value - off;out << "[";FOR(i, off, off+siz) {if(i != off) out << ",";DBG_DP_IMPL_HELPER(out, x[i], sizes, offs);}out << "]";}template<class T, SFINAE(rank<T>::value > 0)>void DBG_DP_IMPL(Int line, const char* expr, const T& dp,const array<Int,rank<T>::value>& sizes={},const array<Int,rank<T>::value>& offs={}){cerr << "[L " << line << "]: ";cerr << expr << " = ";DBG_DP_IMPL_HELPER<rank<T>::value>(cerr, dp, sizes, offs);cerr << "\n";}template<class T>void DBG_GRID_IMPL(Int line, const char* expr, const vector<T>& grid) {cerr << "[L " << line << "]: ";cerr << expr << ":\n";for(const auto& row : grid) {dbg_write(cerr, row);cerr << "\n";}cerr << "\n";}#ifdef PROCON_LOCAL#define DBG(args...) DBG_IMPL(__LINE__, CPP_STR_I(args), args)#define DBG_DP(args...) DBG_DP_IMPL(__LINE__, CPP_STR_I(args), args)#define DBG_GRID(args...) DBG_GRID_IMPL(__LINE__, CPP_STR_I(args), args)#else#define DBG(args...)#define DBG_DP(args...)#define DBG_GRID(args...)#endif// }}}// modint {{{template<class Mod>class ModIntT {private:Int v_; // [0,Mod::value)static Int mod() { return Mod::value; }static Int normalize(Int x) {Int res = x % mod();if(res < 0) res += mod();return res;}public:ModIntT() : v_(0) {}ModIntT(Int v) : v_(normalize(v)) {}explicit operator Int() const { return v_; }ModIntT operator-() const { return ModIntT(-v_); }ModIntT& operator+=(ModIntT rhs) {v_ = normalize(v_ + rhs.v_);return *this;}ModIntT& operator-=(ModIntT rhs) {v_ = normalize(v_ - rhs.v_);return *this;}ModIntT& operator*=(ModIntT rhs) {v_ = normalize(v_ * rhs.v_);return *this;}ModIntT& operator++() { return *this += 1; }ModIntT& operator--() { return *this -= 1; }ModIntT operator++(int) { return exchange(*this, *this+1); }ModIntT operator--(int) { return exchange(*this, *this-1); }ModIntT pow(Int e) const {return fastpow(*this, e, ModIntT(1));}ModIntT inv() const {Int g,x; tie(g,x,ignore) = EXTGCD(v_, mod());ASSERT(g == 1);return ModIntT(x);}friend ModIntT operator+(ModIntT lhs, ModIntT rhs) { return ModIntT(lhs) += rhs; }friend ModIntT operator+(ModIntT lhs, Int rhs) { return ModIntT(lhs) += rhs; }friend ModIntT operator+(Int lhs, ModIntT rhs) { return ModIntT(rhs) += lhs; }friend ModIntT operator-(ModIntT lhs, ModIntT rhs) { return ModIntT(lhs) -= rhs; }friend ModIntT operator-(ModIntT lhs, Int rhs) { return ModIntT(lhs) -= rhs; }friend ModIntT operator-(Int lhs, ModIntT rhs) { return ModIntT(rhs) -= lhs; }friend ModIntT operator*(ModIntT lhs, ModIntT rhs) { return ModIntT(lhs) *= rhs; }friend ModIntT operator*(ModIntT lhs, Int rhs) { return ModIntT(lhs) *= rhs; }friend ModIntT operator*(Int lhs, ModIntT rhs) { return ModIntT(rhs) *= lhs; }friend bool operator==(ModIntT lhs, ModIntT rhs) { return Int(lhs) == Int(rhs); }friend bool operator==(ModIntT lhs, Int rhs) { return lhs == ModIntT(rhs); }friend bool operator==(Int lhs, ModIntT rhs) { return ModIntT(lhs) == rhs; }friend bool operator!=(ModIntT lhs, ModIntT rhs) { return !(lhs == rhs); }friend bool operator!=(ModIntT lhs, Int rhs) { return !(lhs == rhs); }friend bool operator!=(Int lhs, ModIntT rhs) { return !(lhs == rhs); }};template<class Mod>struct ProconHash<ModIntT<Mod>> {size_t operator()(ModIntT<Mod> x) const noexcept {return procon_hash_value(Int(x));}};template<class Mod>struct Scan<ModIntT<Mod>> {using R = ModIntT<Mod>;static R scan(istream& in) {Int v = Scan<Int>::scan(in);return ModIntT<Mod>(v);}};template<class Mod>struct Fmt<ModIntT<Mod>> {static void fmt(ostream& out, ModIntT<Mod> x) {fmt_write(out, Int(x));}};template<class Mod>struct Dbg<ModIntT<Mod>> {static void dbg(ostream& out, ModIntT<Mod> x) {dbg_write(out, Int(x));}};template<Int M>using ModIntC = ModIntT<integral_constant<Int,M>>;using ModInt = ModIntC<MOD>;// }}}// rng {{{// http://prng.di.unimi.it/xoroshiro128plus.cstruct ProconUrbg {using result_type = u64;static constexpr result_type min() { return numeric_limits<result_type>::min(); }static constexpr result_type max() { return numeric_limits<result_type>::max(); }ProconUrbg(u64 s0, u64 s1) : state_{s0,s1} {}result_type operator()() {u64 s0 = state_[0];u64 s1 = state_[1];u64 res = s0 + s1;s1 ^= s0;state_[0] = ((s0<<24)|(s0>>40)) ^ s1 ^ (s1<<16);state_[1] = (s1<<37)|(s1>>27);return res;}private:u64 state_[2];};ProconUrbg& PROCON_URBG() {static u64 s0 = u64(chrono::system_clock::now().time_since_epoch().count());static u64 s1 = u64(&s0);static ProconUrbg urbg(s0, s1);return urbg;}// }}}// init {{{struct ProconInit {ProconInit() {cin.tie(nullptr);ios::sync_with_stdio(false);cin.exceptions(ios::failbit | ios::badbit);cout << fixed << setprecision(COUT_PREC);#ifdef PROCON_LOCALcerr << fixed << setprecision(2);#endifif(COUT_AUTOFLUSH)cout << unitbuf;}} PROCON_INIT;// }}}// }}}// graph {{{auto udgraph_list(Int n, const vector<pair<Int,Int>>& es) {vector<vector<Int>> g(n);for(const auto& e : es) {Int a,b; tie(a,b) = e;g[a].emplace_back(b);g[b].emplace_back(a);}return g;}auto digraph_list(Int n, const vector<pair<Int,Int>>& es) {vector<vector<Int>> g(n);for(const auto& e : es) {Int a,b; tie(a,b) = e;g[a].emplace_back(b);}return g;}auto udgraph_matrix(Int n, const vector<pair<Int,Int>>& es) {vector<vector<Int>> g(n, vector<Int>(n,INF));REP(i, n) { g[i][i] = 0; }for(const auto& e : es) {Int a,b; tie(a,b) = e;g[a][b] = g[b][a] = 1;}return g;}auto digraph_matrix(Int n, const vector<pair<Int,Int>>& es) {vector<vector<Int>> g(n, vector<Int>(n,INF));REP(i, n) { g[i][i] = 0; }for(const auto& e : es) {Int a,b; tie(a,b) = e;g[a][b] = 1;}return g;}template<class T>auto wudgraph_list(Int n, const vector<tuple<Int,Int,T>>& es) {vector<vector<pair<Int,T>>> g(n);for(const auto& e : es) {Int a,b; T c; tie(a,b,c) = e;g[a].emplace_back(b, c);g[b].emplace_back(a, c);}return g;}template<class T>auto wdigraph_list(Int n, const vector<tuple<Int,Int,T>>& es) {vector<vector<pair<Int,T>>> g(n);for(const auto& e : es) {Int a,b; T c; tie(a,b,c) = e;g[a].emplace_back(b, c);}return g;}template<class T>auto wudgraph_matrix(Int n, const vector<tuple<Int,Int,T>>& es) {vector<vector<T>> g(n, vector<T>(n,PROCON_INF<T>()));;REP(i, n) { g[i][i] = T{}; }for(const auto& e : es) {Int a,b; T c; tie(a,b,c) = e;g[a][b] = g[b][a] = c;}return g;}template<class T>auto wdigraph_matrix(Int n, const vector<tuple<Int,Int,T>>& es) {vector<vector<T>> g(n, vector<T>(n,PROCON_INF<T>()));;REP(i, n) { g[i][i] = T{}; }for(const auto& e : es) {Int a,b; T c; tie(a,b,c) = e;g[a][b] = c;}return g;}// 単純無向グラフが木かどうか判定する//// g: 隣接リスト表現(頂点数 n > 0)bool graph_is_tree(const vector<vector<Int>>& g) {Int n = SIZE(g);ASSERT(n > 0);Int edge_cnt = 0;vector<bool> visited(n, false);auto dfs = FIX([&g,&edge_cnt,&visited](auto&& self, Int v) -> void {visited[v] = true;for(Int to : g[v]) {if(visited[to]) continue;++edge_cnt;self(to);}});dfs(0);bool connected = ALL(all_of, visited, [](bool b) { return b; });return edge_cnt == n-1 && connected;}// BFSで重みなしグラフ上の単一始点最短経路を求める//// (ds,ps) を返す// ds[i]: start から点 i への最短距離(到達不能な点は INF)// ps[i]: 最短経路木における点 i の親(start および到達不能な点は -1)tuple<vector<Int>,vector<Int>> graph_bfs(const vector<vector<Int>>& g, Int start) {Int n = SIZE(g);vector<Int> ds(n, INF);vector<Int> ps(n, -1);queue<Int> que;que.emplace(start);ds[start] = 0;while(!que.empty()) {Int v = POP(que);for(Int to : g[v]) {if(ds[to] != INF) continue;que.emplace(to);ds[to] = ds[v] + 1;ps[to] = v;}}return make_tuple(ds, ps);}// ダイクストラ法//// (ds,ps) を返す// ds[i]: start から点 i への最短距離(到達不能な点は PROCON_INF<T>())// ps[i]: 最短経路木における点 i の親(start および到達不能な点は -1)template<typename T>tuple<vector<T>,vector<Int>> graph_dijkstra(const vector<vector<pair<Int,T>>>& g, Int start) {Int n = SIZE(g);vector<T> ds(n, PROCON_INF<T>());vector<Int> ps(n, -1);auto que = priority_queue_make<pair<T,Int>>(greater<>{});ds[start] = T{};que.emplace(T{}, start);Int n_remain = n;while(!que.empty()) {T d; Int v; tie(d,v) = POP(que);if(ds[v] < d) continue;if(--n_remain == 0) break;for(const auto& p : g[v]) {Int to; T cost; tie(to,cost) = p;T d_new = d + cost;if(chmin(ds[to], d_new)) {ps[to] = v;que.emplace(d_new, to);}}}return make_tuple(ds, ps);}// 辺のコストが小さい非負整数の場合の最良優先探索(01-BFS の一般化)// 全ての辺のコストは [0,k] であること//// (ds,ps) を返す// ds[i]: start から点 i への最短距離(到達不能な点は INF)// ps[i]: 最短経路木における点 i の親(start および到達不能な点は -1)tuple<vector<Int>,vector<Int>> graph_k_bfs(const vector<vector<pair<Int,Int>>>& g, Int k, Int start) {Int n = SIZE(g);vector<Int> ds(n, INF);vector<Int> ps(n, -1);vector<queue<Int>> ques(k+1);auto enqueue = [&ques](Int to, Int cost) {ques[cost].emplace(to);};auto dequeue = [&ques]() -> Int {for(auto& que : ques)if(!que.empty())return POP(que);return -1;};enqueue(start, 0);ds[start] = 0;Int v;while((v = dequeue()) != -1) {for(const auto& p : g[v]) {Int to,cost; tie(to,cost) = p;Int d_new = ds[v] + cost;if(chmin(ds[to], d_new)) {ps[to] = v;enqueue(to, cost);}}}return make_tuple(ds, ps);}// ベルマンフォード法//// 負閉路が存在する場合、最短距離が負の無限大になる点が生じる。// そのような点を全て検出するため、2*n 回ループしている// (一般的な実装の倍の回数。ただし更新がなくなったら打ち切る)//// (ds,ps) を返す// ds[i]: start から点 i への最短距離(到達不能なら INF, 負の無限大なら -INF)// ps[i]: 最短経路木における点 i の親(start および到達不能な点は -1)template<typename T>tuple<vector<T>,vector<Int>> graph_bellman(const vector<vector<pair<Int,T>>>& g, Int start) {Int n = SIZE(g);vector<T> ds(n, PROCON_INF<T>());vector<Int> ps(n, -1);ds[start] = T{};REP(i, 2*n) {bool update = false;REP(from, n) {#pragma GCC diagnostic push#pragma GCC diagnostic ignored "-Wfloat-equal"if(ds[from] == PROCON_INF<T>()) continue;for(const auto& p : g[from]) {Int to; T cost; tie(to,cost) = p;T d_new = ds[from]==-PROCON_INF<T>() ? -PROCON_INF<T>() : ds[from]+cost;if(d_new < ds[to]) {update = true;ds[to] = i >= n-1 ? -PROCON_INF<T>() : d_new;ps[to] = from;}}#pragma GCC diagnostic pop}if(!update) break;}return make_tuple(ds, ps);}// SPFA (Shortest Path Faster Algorithm)//// 理論上はベルマンフォードより速いはずだが、実際はそうでもなさげ// 最短距離が負の無限大になる点を全て検出するため 2*n 回ループしている// (一般的な実装の倍の回数。ただし更新がなくなったら打ち切る)//// (ds,ps) を返す// ds[i]: start から点 i への最短距離(到達不能なら INF, 負の無限大なら -INF)// ps[i]: 最短経路木における点 i の親(start および到達不能な点は -1)template<typename T>tuple<vector<T>,vector<Int>> graph_spfa(const vector<vector<pair<Int,T>>>& g, Int start) {Int n = SIZE(g);vector<T> ds(n, PROCON_INF<T>());vector<Int> ps(n, -1);queue<Int> que;vector<bool> in_que(n, false);const auto enqueue = [&que,&in_que](Int v) { que.emplace(v); in_que[v] = true; };const auto dequeue = [&que,&in_que]() { Int v = POP(que); in_que[v] = false; return v; };ds[start] = T{};enqueue(start);REP(i, 2*n) {REP(_, que.size()) {Int from = dequeue();for(const auto& p : g[from]) {Int to; T cost; tie(to,cost) = p;#pragma GCC diagnostic push#pragma GCC diagnostic ignored "-Wfloat-equal"T d_new = ds[from]==-PROCON_INF<T>() ? -PROCON_INF<T>() : ds[from]+cost;if(d_new < ds[to]) {ds[to] = i >= n-1 ? -PROCON_INF<T>() : d_new;ps[to] = from;if(!in_que[to]) enqueue(to);}#pragma GCC diagnostic pop}}if(que.empty()) break;}return make_tuple(ds, ps);}// ワーシャルフロイド法//// g は隣接行列 (g[from][to]) で、from == to の場合 0, from != to で辺// がない場合 INF//// g は全点対間最短距離で上書きされる// (ok,nex) を返す// ok: 負閉路が存在しない場合に限り true// nex[i][j]: i から j へ最短経路で行くとき、次に辿るべき点(到達不能なら -1)template<typename T>tuple<bool,vector<vector<Int>>> graph_floyd(vector<vector<T>>& g) {Int n = SIZE(g);vector<vector<Int>> nex(n, vector<Int>(n,-1));#pragma GCC diagnostic push#pragma GCC diagnostic ignored "-Wfloat-equal"REP(i, n) REP(j, n) {if(g[i][j] != PROCON_INF<T>())nex[i][j] = j;}REP(k, n) {REP(i, n) {if(g[i][k] == PROCON_INF<T>()) continue;REP(j, n) {if(g[k][j] == PROCON_INF<T>()) continue;if(chmin(g[i][j], g[i][k] + g[k][j])) {nex[i][j] = nex[i][k];}if(i == j && g[i][j] < 0) return make_tuple(false, nex);}}}#pragma GCC diagnostic popreturn make_tuple(true, nex);}// TODO: 重みあり/なし両対応// トポロジカルソート// queue を MinHeap に変えると辞書順最小のものが求まる//// (ok,res) を返す// ok: DAGであったかどうか// res: 結果tuple<bool,vector<Int>> graph_tsort(const vector<vector<Int>>& g) {Int n = SIZE(g);vector<Int> res;res.reserve(n);vector<Int> deg_in(n, 0);for(const auto& tos : g)for(auto to : tos)++deg_in[to];queue<Int> que;REP(v, n) {if(deg_in[v] == 0)que.emplace(v);}while(!que.empty()) {Int v = POP(que);res.emplace_back(v);for(auto to : g[v]) {if(--deg_in[to] > 0) continue;que.emplace(to);}}bool ok = SIZE(res) == n;return make_tuple(ok, res);}// TODO: 重みあり/なし両対応// (関節点リスト,橋リスト) を返すtuple<vector<Int>,vector<pair<Int,Int>>> graph_lowlink(const vector<vector<Int>>& g) {Int n = SIZE(g);vector<Int> ord(n, -1);vector<Int> low(n, -1);vector<Int> articulations;vector<pair<Int,Int>> bridges;auto dfs = FIX([&g,&ord,&low,&articulations,&bridges](auto&& self, Int v, Int parent, Int k) -> void {low[v] = ord[v] = k;bool arti = false;Int n_child = 0;for(Int to : g[v]) {// 親または後退辺if(ord[to] != -1) {if(to != parent)chmin(low[v], ord[to]);continue;}// 子を辿り、low[v] を更新++n_child;self(to, v, k+1);chmin(low[v], low[to]);// 関節点判定(根でない場合)if(parent != -1 && low[to] >= ord[v])arti = true;// 橋判定if(low[to] > ord[v])bridges.emplace_back(minmax(v,to));}// 関節点判定(根の場合)if(parent == -1 && n_child > 1)arti = true;if(arti)articulations.emplace_back(v);});dfs(0, -1, 0);return make_tuple(articulations, bridges);}// 各頂点の (indegree,outdegree) のリストを返す (隣接リスト版)vector<pair<Int,Int>> graph_degrees_list(const vector<vector<Int>>& g) {Int n = SIZE(g);vector<pair<Int,Int>> res(n, {0,0});REP(from, n) {for(Int to : g[from]) {++res[from].second;++res[to].first;}}return res;}// 各頂点の (indegree,outdegree) のリストを返す (隣接行列版)vector<pair<Int,Int>> graph_degrees_matrix(const vector<vector<Int>>& g) {Int n = SIZE(g);vector<pair<Int,Int>> res(n, {0,0});REP(from, n) REP(to, n) {Int k = g[from][to];res[from].second += k;res[to].first += k;}return res;}// グラフのオイラー路 (隣接リスト版)//// g は破壊される// start: 始点// digraph: 有向グラフか?vector<Int> graph_euler_trail_list(vector<vector<Int>>& g, Int start, bool digraph) {// スタックオーバーフロー回避のため再帰を使わず自前の stack で処理enum Action { CALL, RESUME };vector<Int> res;stack<tuple<Action,Int>> stk;stk.emplace(CALL, start);while(!stk.empty()) {Action act; Int v; tie(act,v) = POP(stk);switch(act) {case CALL:stk.emplace(RESUME, v);while(!g[v].empty()) {Int to = g[v].back(); g[v].pop_back();if(!digraph)g[to].erase(ALL(find, g[to], v));stk.emplace(CALL, to);}break;case RESUME:res.emplace_back(v);break;default: ASSERT(false);}}ALL(reverse, res);return res;}// 無向グラフのオイラー路 (隣接行列版)//// g[v][w]: v,w 間の辺の本数 (破壊される)// start: 始点// digraph: 有向グラフか?vector<Int> graph_euler_trail_matrix(vector<vector<Int>>& g, Int start, bool digraph) {// スタックオーバーフロー回避のため再帰を使わず自前の stack で処理enum Action { CALL, RESUME };Int n = SIZE(g);vector<Int> res;stack<tuple<Action,Int>> stk;stk.emplace(CALL, start);while(!stk.empty()) {Action act; Int v; tie(act,v) = POP(stk);switch(act) {case CALL:stk.emplace(RESUME, v);REP(to, n) {if(g[v][to] == 0) continue;--g[v][to];if(!digraph)--g[to][v];stk.emplace(CALL, to);}break;case RESUME:res.emplace_back(v);break;default: ASSERT(false);}}ALL(reverse, res);return res;}// }}}//--------------------------------------------------------------------struct Lca {explicit Lca(const vector<vector<Int>>& g, Int root) :n_(SIZE(g)), m_(log2_floor(n_)), depths_(n_), pss_(n_,vector<Int>(m_+1,-1)){init_dfs(g, root, -1, 0);FOR(i, 1, m_+1) {REP(v, n_) {Int p = pss_[v][i-1];if(p == -1) continue;pss_[v][i] = pss_[p][i-1];}}}Int get(Int v, Int w) const {if(depths_[v] > depths_[w]) swap(v, w);for(Int i = m_; i >= 0; --i) {Int dd = depths_[w] - depths_[v];if(dd == 0) break;if(BIT_TEST(dd,i))w = pss_[w][i];}if(v == w) return v;for(Int i = m_; i >= 0; --i) {Int pv = pss_[v][i];Int pw = pss_[w][i];if(pv != pw) {v = pv;w = pw;}}return pss_[v][0];}private:void init_dfs(const vector<vector<Int>>& g, Int v, Int p, Int d) {depths_[v] = d;pss_[v][0] = p;for(Int to : g[v]) {if(to == p) continue;init_dfs(g, to, v, d+1);}}Int n_;Int m_;vector<Int> depths_;vector<vector<Int>> pss_;};void solve() {Int N = RD();auto E = RD_VEC<pair<Int,Int>>(N-1);auto G = udgraph_list(N, E);auto U = RD_VEC(N);Int root = 0;vector<Int> costs(N);auto dfs = FIX([&](auto&& self, Int v, Int p, Int c) -> void {c += U[v];costs[v] = c;for(Int to : G[v]) {if(to == p) continue;self(to, v, c);}});dfs(root, -1, 0);DBG(costs);Int ans = 0;auto lca = Lca(G, root);Int M = RD();LOOP(M) {Int a = RD();Int b = RD();Int c = RD();Int z = lca.get(a, b);Int unit = costs[a] + costs[b] - 2*costs[z] + U[z];Int cur = c * unit;DBG(z, unit, cur);ans += cur;}PRINTLN(ans);}signed main() {Int T = 1; //RD();LOOP(T) {solve();}EXIT();}