結果

問題 No.902 Query ζone
ユーザー kyon2326
提出日時 2023-12-30 00:19:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,038 ms / 5,000 ms
コード長 44,977 bytes
コンパイル時間 6,888 ms
コンパイル使用メモリ 335,164 KB
実行使用メモリ 17,516 KB
最終ジャッジ日時 2024-09-27 16:25:59
合計ジャッジ時間 21,973 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

//#pragma GCC optimize("O2")
//#pragma GCC target("avx2")
#define _USE_MATH_DEFINES
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#include <bits/stdc++.h>
using namespace std;
/*
#include <atcoder/all>
using namespace atcoder;
//*/
/*
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
using bll = boost::multiprecision::cpp_int;
using bdouble = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>;
using namespace boost::multiprecision;
//*/
#define ENV_USE_FASTIO 1
#define ENV_USE_ENDL 0
#if !defined(LOCAL_DEV) && ENV_USE_FASTIO
    #define USE_FASTIO
#endif
#if ENV_USE_ENDL
    #define NEWLINE std::endl
#else
    #define NEWLINE '\n'
#endif
//#define int long long
using ll = long long;
//constexpr ll MOD = (ll)1e9 + 7; //primitive root = 5
constexpr ll MOD = 998244353; //primitive root = 3
//INT_MAX = (1<<31)-1 = 2147483647, INT64_MAX = (1LL<<63)-1 = 9223372036854775807
constexpr ll INF = std::numeric_limits<ll>::max() == INT_MAX ? (ll)1e9 + 7 : (ll)1e18 + 1;
constexpr double EPS = 1e-9;
constexpr int dx[4] = {1, 0, -1, 0};
constexpr int dy[4] = {0, 1, 0, -1};
constexpr int dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1};
constexpr int dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
namespace fastio_impl {
struct IOPre {
    static constexpr int TEN = 10, SZ = TEN * TEN * TEN * TEN;
    std::array<char, 4 * SZ> num;
    constexpr IOPre() : num{} {
        for (int i = 0; i < SZ; i++) { int n = i; for (int j = 3; j >= 0; j--) { num[i * 4 + j] = static_cast<char>(n % TEN + '0'); n /= TEN; } }
    }
};
struct IO_endl {};
struct IO_flush {};
std::ostream& operator<<(std::ostream& os, const IO_endl&) { return os << std::endl; }
std::ostream& operator<<(std::ostream& os, const IO_flush&) { return os << std::flush; }
template <class T> concept is_IO_endl = std::is_same_v<T, IO_endl>;
template <class T> concept is_IO_flush = std::is_same_v<T, IO_flush>;
template <class T> concept is_char = std::is_same_v<T, char>;
template <class T> concept is_bool = std::is_same_v<T, bool>;
template <class> struct is_bounded_char_array_t : std::false_type {};
template <std::size_t N> struct is_bounded_char_array_t<char[N]> : std::true_type {};
template <class T> concept is_bounded_char_array = std::is_bounded_array_v<T> && std::is_base_of_v<std::true_type, is_bounded_char_array_t<T>>;
template <class T> concept is_string = std::is_same_v<T, std::string> || std::is_same_v<T, const char*> || std::is_same_v<T, char*> || 
    is_bounded_char_array<T>;
template <class T> concept is_default = is_char<T> || is_bool<T> || is_string<T> || std::is_integral_v<T>;
template <class T> concept is_inLazy28 = std::is_same_v<T, __int128_t> || std::is_same_v<T, __uint128_t>;
template <class T> concept has_val = requires(T& v) { v.val(); };
template <class T> concept has_to_string = requires(T& v) { v.to_string(); };
template <class T> concept has_str = requires(T& v) { v.str(); };
template <class T> concept has_constructor_string = std::is_constructible_v<T, std::string>;
template <class T> concept has_constructor_ll = std::is_constructible_v<T, long long>;
template <class T> concept is_constructible_istreambuf_iterator = std::is_constructible_v<std::istreambuf_iterator<char>, T>;
template <class T> concept is_custom = requires(T& v) { T::internal_value_type(); };
template <class T> concept is_iterable = requires(T& v) { std::begin(std::declval<T>()); std::end(std::declval<T>()); };
template <class T> concept is_applyable = requires(T& v) { std::tuple_size<T>::type(); std::get<0>(std::declval<T>()); };
template <class T> static constexpr bool needs_newline = (is_iterable<T> || is_applyable<T>) && (!is_default<T>);
template <typename T, typename U> struct any_needs_newline { static constexpr bool value = false; };
template <typename T> struct any_needs_newline<T, std::index_sequence<>> { static constexpr bool value = false; };
template <typename T, std::size_t I, std::size_t... Is> struct any_needs_newline<T, std::index_sequence<I, Is...>> { static constexpr bool value = 
    needs_newline<decltype(std::get<I>(std::declval<T>()))> || any_needs_newline<T, std::index_sequence<Is...>>::value; };
struct IO {
#if !HAVE_DECL_FREAD_UNLOCKED
    #define fread_unlocked fread
#endif
#if !HAVE_DECL_FWRITE_UNLOCKED
    #define fwrite_unlocked fwrite
#endif
    static constexpr int SZ = 1 << 17, LEN = 32, TEN = 10, HUNDRED = TEN * TEN, THOUSAND = HUNDRED * TEN, TENTHOUSAND = THOUSAND * TEN, 
        MAGIC_MULTIPLY = 205, MAGIC_SHIFT = 11, MASK = 15, TWELVE = 12, SIXTEEN = 16;
    static constexpr IOPre io_pre = {};
    std::array<char, SZ> input_buffer, output_buffer;
    int input_ptr_left, input_ptr_right, output_ptr_right, precision_value;
    bool is_sync_with_stdio;
    FILE *infile, *outfile;
    std::istream *instream;
    std::ostream *outstream;
    IO() : input_buffer{}, output_buffer{}, input_ptr_left{}, input_ptr_right{}, output_ptr_right{}, precision_value{20}, is_sync_with_stdio{false}, 
        infile{stdin}, outfile{stdout}, instream{nullptr}, outstream{nullptr} {}
    IO(const IO&) = delete;
    IO(IO&&) = delete;
    IO& operator=(const IO&) = delete;
    IO& operator=(IO&&) = delete;
    ~IO() { flush(); }
    inline void load() {
        memmove(std::begin(input_buffer), std::begin(input_buffer) + input_ptr_left, input_ptr_right - input_ptr_left);
        int bytes_read = static_cast<int>(instream ? instream->read(std::begin(input_buffer) + input_ptr_right - input_ptr_left, SZ - input_ptr_right 
            + input_ptr_left).gcount() : fread_unlocked(std::begin(input_buffer) + input_ptr_right - input_ptr_left, 1, SZ - input_ptr_right + 
            input_ptr_left, infile));
        input_ptr_right = input_ptr_right - input_ptr_left + bytes_read;
        input_ptr_left = 0;
    }
    inline void read_char(char& c) { if (input_ptr_left + LEN > input_ptr_right) { load(); } c = input_buffer[input_ptr_left++]; }
    inline void read_string(std::string& x) { char c; while (read_char(c), c < '!') { continue; } x = c; while (read_char(c), c >= '!') { x += c; } }
    template <class T> inline std::enable_if_t<std::is_floating_point_v<T>, void> read_float(T& x) { std::string s; read_string(s); x = std::stod(s); 
        }
    template <class T> inline std::enable_if_t<std::is_integral_v<T>, void> read_int(T& x) {
        if (input_ptr_left + LEN > input_ptr_right) load();
        char c = 0;
        do c = input_buffer[input_ptr_left++]; while (c < '-');
        [[maybe_unused]] bool minus = false;
        if constexpr (std::is_signed<T>::value) if (c == '-') minus = true, c = input_buffer[input_ptr_left++];
        x = 0;
        while (c >= '0') x = x * TEN + (c & MASK), c = input_buffer[input_ptr_left++];
        if constexpr (std::is_signed<T>::value) if (minus) x = -x;
    }
    inline void skip_space() { if (input_ptr_left + LEN > input_ptr_right) { load(); } while (input_buffer[input_ptr_left] <= ' ') { input_ptr_left
        ++; } }
    inline void flush() {
        if (outstream) for (int i = 0; i < output_ptr_right; ++i) *outstream << output_buffer[i];
        else fwrite_unlocked(std::begin(output_buffer), 1, output_ptr_right, outfile);
        output_ptr_right = 0;
    }
    inline void write_char(char c) { if (output_ptr_right > SZ - LEN) { flush(); } output_buffer[output_ptr_right++] = c; }
    inline void write_bool(bool b) { if (output_ptr_right > SZ - LEN) { flush(); } output_buffer[output_ptr_right++] = b ? '1' : '0'; }
    inline void write_string(const std::string& s) { for (auto x : s) write_char(x); }
    inline void write_string(const char* s) { while (*s) write_char(*s++); }
    inline void write_string(char* s) { while (*s) write_char(*s++); }
    template <typename T> inline std::enable_if_t<std::is_floating_point_v<T>, void> write_float(T x) {
        std::ostringstream s; s.setf(ios::fixed), s.precision(precision_value); s << x; write_string(s.str());
    }
    template <typename T> inline std::enable_if_t<std::is_integral_v<T>, void> write_int(T x) {
        if (output_ptr_right > SZ - LEN) flush();
        if (!x) { output_buffer[output_ptr_right++] = '0'; return; }
        if constexpr (std::is_signed<T>::value == true) if (x < 0) output_buffer[output_ptr_right++] = '-', x = -x;
        int i = TWELVE;
        std::array<char, SIXTEEN> buf{};
        while (x >= TENTHOUSAND) { memcpy(std::begin(buf) + i, std::begin(io_pre.num) + (x % TENTHOUSAND) * 4, 4); x /= TENTHOUSAND; i -= 4; }
        if (x < HUNDRED) {
            if (x < TEN) { output_buffer[output_ptr_right++] = static_cast<char>('0' + x); }
            else {
                std::uint32_t q = (static_cast<std::uint32_t>(x) * MAGIC_MULTIPLY) >> MAGIC_SHIFT, r = static_cast<std::uint32_t>(x) - q * TEN;
                output_buffer[output_ptr_right] = static_cast<char>('0' + q);
                output_buffer[output_ptr_right + 1] = static_cast<char>('0' + r);
                output_ptr_right += 2;
            }
        } else {
            if (x < THOUSAND) memcpy(std::begin(output_buffer) + output_ptr_right, std::begin(io_pre.num) + (x << 2) + 1, 3), output_ptr_right += 3;
            else memcpy(std::begin(output_buffer) + output_ptr_right, std::begin(io_pre.num) + (x << 2), 4), output_ptr_right += 4;
        }
        memcpy(std::begin(output_buffer) + output_ptr_right, std::begin(buf) + i + 4, TWELVE - i);
        output_ptr_right += TWELVE - i;
    }
    template <typename T> IO& operator>>(T& x) {
        static_assert(is_custom<T> or is_default<T> or is_iterable<T> or is_applyable<T> or std::is_floating_point_v<T> or has_constructor_string<T> 
            or has_constructor_ll<T>);
        static_assert(!is_bool<T>);
        if constexpr (is_custom<T>) { typename T::internal_value_type y; read_int(y); x = y; }
        else if constexpr (is_default<T>) {
            if constexpr (is_string<T>) { read_string(x); }
            else if constexpr (is_char<T>) { read_char(x); }
            else if constexpr (std::is_integral_v<T>) { read_int(x); }
        } else if constexpr (is_iterable<T>) { for (auto& y : x) operator>>(y); }
        else if constexpr (is_applyable<T>) { std::apply([this](auto&... y) { ((this->operator>>(y)), ...); }, x); }
        else if constexpr (std::is_floating_point_v<T>) { read_float(x); }
        else if constexpr (has_constructor_string<T>) { std::string y; read_string(y); x = y; }
        else if constexpr (has_constructor_ll<T>) { long long y; read_int(y); x = y; }
        return *this;
    }
    template <typename T_> IO& operator<<(T_&& x) {
        using T = typename std::remove_cv< typename std::remove_reference<T_>::type>::type;
        static_assert(is_IO_endl<T> or is_IO_flush<T> or is_custom<T> or is_default<T> or is_iterable<T> or is_applyable<T> or std
            ::is_floating_point_v<T> or is_inLazy28<T> or has_val<T> or has_to_string<T> or has_str<T> or is_constructible_istreambuf_iterator<T>);
        if constexpr (is_IO_endl<T>) { fastio_endl(); }
        else if constexpr (is_IO_flush<T>) { fastio_flush(); }
        else if constexpr (is_custom<T>) { write_int(x.get()); }
        else if constexpr (is_default<T>) {
            if constexpr (is_bool<T>) { write_bool(x); }
            else if constexpr (is_string<T>) { write_string(x); }
            else if constexpr (is_char<T>) { write_char(x); }
            else if constexpr (std::is_integral_v<T>) { write_int(x); }
        } else if constexpr (is_iterable<T>) {
            constexpr char sep = needs_newline<decltype(*std::begin(x))> ? '\n' : ' '; int i = 0;
            for (const auto& y : x) { if (i++) write_char(sep); operator<<(y); }
        } else if constexpr (is_applyable<T>) {
            constexpr char sep = (any_needs_newline<T, std::make_index_sequence<std::tuple_size_v<T>>>::value) ? '\n' : ' '; int i = 0;
            std::apply([this, &sep, &i](auto const&... y) { (((i++ ? write_char(sep) : void()), this->operator<<(y)), ...); }, x);
        } else if constexpr (std::is_floating_point_v<T>) { write_float(x); }
        else if constexpr (is_inLazy28<T>) { write_string(to_string(x)); }
        else if constexpr (has_val<T>) { write_int(x.val()); }
        else if constexpr (has_to_string<T>) { write_string(x.to_string()); }
        else if constexpr (has_str<T>) { write_string(x.str()); }
        else if constexpr (is_constructible_istreambuf_iterator<T>) { std::istreambuf_iterator<char> it(x), last; std::for_each(it, last, [&](char c) 
            { write_char(c); }); }
        return *this;
    }
    IO* tie(std::nullptr_t) { return this; }
    void sync_with_stdio(bool b) { is_sync_with_stdio = b; }
    void setf(...) {}
    void precision(int n) { precision_value = n; }
    void set_infile(FILE* f) { infile = f; }
    void set_outfile(FILE* f) { outfile = f; }
    void unset_infile() { infile = stdin; }
    void unset_outfile() { outfile = stdout; }
    void set_instream(std::istream* s) { instream = s; }
    void set_outstream(std::ostream* s) { outstream = s; }
    void unset_instream() { instream = nullptr; }
    void unset_outstream() { outstream = nullptr; }
    IO& fastio_endl() { operator<<('\n'); if (is_sync_with_stdio) flush(); return *this; }
    IO& fastio_flush() { flush(); return *this; }
};
} // namespace fastio_impl
#ifdef USE_FASTIO
    namespace std {
        fastio_impl::IO fastio;
        fastio_impl::IO_endl fastio_endl;
        fastio_impl::IO_flush fastio_flush;
    }
    #define cin fastio
    #define cout fastio
    #define endl fastio_endl
    #define flush fastio_flush
#endif
#if defined(LOCAL_TEST) || defined(LOCAL_DEV)
    #define BOOST_STACKTRACE_USE_ADDR2LINE
    #define BOOST_STACKTRACE_ADDR2LINE_LOCATION /usr/local/opt/binutils/bin/addr2line
    #define _GNU_SOURCE
    #include <boost/stacktrace.hpp>
#endif
#ifdef LOCAL_TEST
    namespace std {
        template <typename T> class dvector : public std::vector<T> {
        public:
            using std::vector<T>::vector;
            template <typename T_ = T, typename std::enable_if_t<std::is_same_v<T_, bool>, std::nullptr_t> = nullptr> std::vector<bool>::reference 
                operator[](std::size_t n) {
                if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") 
                    >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
            }
            template <typename T_ = T, typename std::enable_if_t<std::is_same_v<T_, bool>, std::nullptr_t> = nullptr> const T_ operator[](std::size_t 
                n) const {
                if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") 
                    >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
            }
            template <typename T_ = T, typename std::enable_if_t<!std::is_same_v<T_, bool>, std::nullptr_t> = nullptr> constexpr T_& operator[](std
                ::size_t n) {
                if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") 
                    >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
            }
            template <typename T_ = T, typename std::enable_if_t<!std::is_same_v<T_, bool>, std::nullptr_t> = nullptr> constexpr const T_& operator[]
                (std::size_t n) const {
                if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") 
                    >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
            }
        };
        template <typename T, std::size_t N> class darray : public std::array<T, N> {
        public:
            using std::array<T, N>::array;
            constexpr darray(std::initializer_list<T> il) {
                *this = {}; int i = 0; for (auto&& x : il) this->operator[](i++) = x;
            }
            constexpr T& operator[](std::size_t n) {
                if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") 
                    >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
            }
            constexpr const T& operator[](std::size_t n) const {
                if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") 
                    >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
            }
        };
        template <typename T, std::size_t N> struct tuple_size<std::darray<T, N>> : integral_constant<std::size_t, N> {};
        template <typename T, std::size_t N, std::size_t I> struct tuple_element<I, std::darray<T, N>> { using type = T; };
        template <typename T, typename Compare = std::less<T>> class dmultiset : public std::multiset<T, Compare> {
        public:
            using std::multiset<T, Compare>::multiset;
            const typename std::multiset<T, Compare>::iterator erase(const typename std::multiset<T, Compare>::iterator it) {
                return std::multiset<T, Compare>::erase(it);
            }
            std::size_t erase([[maybe_unused]] const T& x) {
                std::cerr << boost::stacktrace::stacktrace() << '\n'; assert(false);
            }
            std::size_t erase_all_elements(const T& x) {
                return std::multiset<T, Compare>::erase(x);
            }
        };
        template <typename Lazy, typename T2> std::ostream& operator<<(std::ostream& s, std::pair<Lazy, T2>& p) { return s << "(" << p.first << ", " 
            << p.second << ")"; }
        template <typename Lazy, typename T2> std::ostream& operator<<(std::ostream& s, const std::pair<Lazy, T2>& p) { return s << "(" << p.first << 
            ", " << p.second << ")"; }
        template <typename T, std::size_t N> std::ostream& operator<<(std::ostream& s, std::array<T, N>& v) { s << "{ "; for (std::size_t i = 0; i < 
            N; ++i){ s << v[i] << "\t"; } s << "}"; return s; }
        template <typename T, std::size_t N> std::ostream& operator<<(std::ostream& s, const std::array<T, N>& v) { s << "{ "; for (std::size_t i = 0
            ; i < N; ++i){ s << v[i] << "\t"; } s << "}"; return s; }
        template <typename T, typename Compare> std::ostream& operator<<(std::ostream& s, std::set<T, Compare>& se) { s << "{ "; for (auto it = se
            .begin(); it != se.end(); ++it){ s << *it << "\t"; } s << "}"; return s; }
        template <typename T, typename Compare> std::ostream& operator<<(std::ostream& s, const std::set<T, Compare>& se) { s << "{ "; for (auto it = 
            se.begin(); it != se.end(); ++it){ s << *it << "\t"; } s << "}"; return s; }
        template <typename T, typename Compare> std::ostream& operator<<(std::ostream& s, std::multiset<T, Compare>& se) { s << "{ "; for (auto it = 
            se.begin(); it != se.end(); ++it){ s << *it << "\t"; } s << "}"; return s; }
        template <typename T, typename Compare> std::ostream& operator<<(std::ostream& s, const std::multiset<T, Compare>& se) { s << "{ "; for (auto 
            it = se.begin(); it != se.end(); ++it){ s << *it << "\t"; } s << "}"; return s; }
        template <typename Lazy, typename T2, typename Compare> std::ostream& operator<<(std::ostream& s, std::map<Lazy, T2, Compare>& m) { s << 
            "{\n"; for (auto it = m.begin(); it != m.end(); ++it){ s << "\t" << it->first << " : " << it->second << "\n"; } s << "}"; return s; }
        template <typename Lazy, typename T2, typename Compare> std::ostream& operator<<(std::ostream& s, const std::map<Lazy, T2, Compare>& m) { s 
            << "{\n"; for (auto it = m.begin(); it != m.end(); ++it){ s << "\t" << it->first << " : " << it->second << "\n"; } s << "}"; return s; }
        template <typename T> std::ostream& operator<<(std::ostream& s, std::deque<T>& v) { s << "{ "; for (std::size_t i = 0; i < v.size(); ++i){ s 
            << v[i] << "\t"; } s << "}"; return s; }
        template <typename T> std::ostream& operator<<(std::ostream& s, const std::deque<T>& v) { s << "{ "; for (std::size_t i = 0; i < v.size(); 
            ++i){ s << v[i] << "\t"; } s << "}"; return s; }
        template <typename T> std::ostream& operator<<(std::ostream& s, std::vector<T>& v) { s << "{ "; for (std::size_t i = 0; i < v.size(); ++i){ s 
            << v[i] << "\t"; } s << "}"; return s; }
        template <typename T> std::ostream& operator<<(std::ostream& s, const std::vector<T>& v) { s << "{ "; for (std::size_t i = 0; i < v.size(); 
            ++i){ s << v[i] << "\t"; } s << "}"; return s; }
        template <typename T> std::ostream& operator<<(std::ostream& s, std::vector<std::dvector<T>>& vv) { s << "\\\n"; for (std::size_t i = 0; i < 
            vv.size(); ++i){ s << vv[i] << (i + 1 == vv.size() ? "" : "\n"); } return s; }
        template <typename T> std::ostream& operator<<(std::ostream& s, const std::vector<std::dvector<T>>& vv) { s << "\\\n"; for (std::size_t i = 0
            ; i < vv.size(); ++i){ s << vv[i] << (i + 1 == vv.size() ? "" : "\n"); } return s; }
        template <typename T, std::size_t N, typename std::enable_if_t<!std::is_same_v<T, char> && !std::is_same_v<T, const char>, std::nullptr_t> = 
            nullptr> std::ostream& operator<<(std::ostream& s, T (&v)[N]) { s << "{ "; for (std::size_t i = 0; i < N; ++i){ s << v[i] << "\t"; } s << 
            "}"; return s; }
        template <typename T, std::size_t N, typename std::enable_if_t<!std::is_same_v<T, char> && !std::is_same_v<T, const char>, std::nullptr_t> = 
            nullptr> std::ostream& operator<<(std::ostream& s, const T (&v)[N]) { s << "{ "; for (std::size_t i = 0; i < N; ++i){ s << v[i] << "\t"; 
            } s << "}"; return s; }
        template <typename T, std::size_t N, std::size_t M, typename std::enable_if_t<!std::is_same_v<T, char> && !std::is_same_v<T, const char>, std
            ::nullptr_t> = nullptr> std::ostream& operator<<(std::ostream& s, T (&vv)[N][M]) { s << "\\\n"; for (std::size_t i = 0; i < N; ++i){ s << 
            vv[i] << (i + 1 == N ? "" : "\n"); } return s; }
        template <typename T, std::size_t N, std::size_t M, typename std::enable_if_t<!std::is_same_v<T, char> && !std::is_same_v<T, const char>, std
            ::nullptr_t> = nullptr> std::ostream& operator<<(std::ostream& s, const T (&vv)[N][M]) { s << "\\\n"; for (std::size_t i = 0; i < N; ++i
            ){ s << vv[i] << (i + 1 == N ? "" : "\n"); } return s; }
    } // namespace std
    #define vector dvector
    #define array darray
    #define multiset dmultiset
    class SIGFPE_exception : std::exception {};
    class SIGSEGV_exception : std::exception {};
    void catch_SIGFPE([[maybe_unused]] int e) { std::cerr << boost::stacktrace::stacktrace() << '\n'; throw SIGFPE_exception(); }
    void catch_SIGSEGV([[maybe_unused]] int e) { std::cerr << boost::stacktrace::stacktrace() << '\n'; throw SIGSEGV_exception(); }
    signed convertedmain();
    signed main() { signal(SIGFPE, catch_SIGFPE); signal(SIGSEGV, catch_SIGSEGV); return convertedmain(); }
    #define main() convertedmain()
#else
    #define erase_all_elements erase
#endif
#ifdef LOCAL_DEV
    void debug_impl() { std::cerr << '\n'; }
    template <typename Head, typename... Tail> void debug_impl(Head& head, Tail&... tail) { std::cerr << " " << head << (sizeof...(Tail) ? "," : ""); 
        debug_impl(tail...); }
    template <typename Head, typename... Tail> void debug_impl(const Head& head, const Tail&... tail) { std::cerr << " " << head << (sizeof...(Tail) 
        ? "," : ""); debug_impl(tail...); }
    #define debug(...) do { std::cerr << ":" << __LINE__ << " (" << #__VA_ARGS__ << ") ="; debug_impl(__VA_ARGS__); } while (false)
    #define debugr(...) do { std::cerr << "\033[31m"; debug(__VA_ARGS__); std::cerr << "\033[0m"; } while (false)
    #define debugy(...) do { std::cerr << "\033[33m"; debug(__VA_ARGS__); std::cerr << "\033[0m"; } while (false)
    constexpr inline long long prodlocal([[maybe_unused]] long long prod, [[maybe_unused]] long long local) { return local; }
#else
    #define debug(...) do {} while (false)
    #define debugr(...) do {} while (false)
    #define debugy(...) do {} while (false)
    constexpr inline long long prodlocal([[maybe_unused]] long long prod, [[maybe_unused]] long long local) { return prod; }
#endif
#define repoverload3(_1, _2, _3, name, ...) name
#define rep3(i, a, b) for(ll i=(a), i##_length=(b); i<i##_length; ++i)
#define rep2(i, n) rep3(i, 0, n)
#define rep1(n) rep3(i, 0, n)
#define rep(...) repoverload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define repeq3(i, a, b) rep3(i, (a)+1, (b)+1)
#define repeq2(i, n) rep3(i, 1, (n)+1)
#define repeq1(n) rep3(i, 1, (n)+1)
#define repeq(...) repoverload3(__VA_ARGS__, repeq3, repeq2, repeq1)(__VA_ARGS__)
#define rrep3(i, a, b) for(ll i=(b)-1; i>=(a); --i)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep1(n) rrep3(i, 0, n)
#define rrep(...) repoverload3(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rrepeq3(i, a, b) rrep3(i, (a)+1, (b)+1)
#define rrepeq2(i, n) rrep3(i, 1, (n)+1)
#define rrepeq1(n) rrep3(i, 1, (n)+1)
#define rrepeq(...) repoverload3(__VA_ARGS__, rrepeq3, rrepeq2, rrepeq1)(__VA_ARGS__)
#define all(v) std::begin(v), std::end(v)
#define rall(v) std::rbegin(v), std::rend(v)
template <typename T> using priority_queue_rev = std::priority_queue<T, std::vector<T>, std::greater<T>>;
void p() { std::cout << NEWLINE; }
template <typename Head, typename... Tail> void p(Head& head, Tail&... tail) { std::cout << head << (sizeof...(Tail) ? " " : ""); p(tail...); }
template <typename Head, typename... Tail> void p(const Head& head, const Tail&... tail) { std::cout << head << (sizeof...(Tail) ? " " : ""); p(tail
    ...); }
template <typename T> inline void pv(const T& v) { auto itbegin = std::begin(v), itend = std::end(v); for (auto it = itbegin; it != itend; std
    ::advance(it, 1)) cout << (it == itbegin ? "" : " ") << *it; cout << NEWLINE; }
template <typename T, typename U = typename T::value_type> inline void pv(const T& v, const U& add) { auto itbegin = std::begin(v), itend = std::end
    (v); for (auto it = itbegin; it != itend; std::advance(it, 1)) cout << (it == itbegin ? "" : " ") << *it + add; cout << NEWLINE; }
template <typename T> inline bool chmax(T& a, T b) { return a < b && (a = b, true); }
template <typename T> inline bool chmin(T& a, T b) { return a > b && (a = b, true); }
template <typename T> inline void uniq(T& v) { std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); }
template <typename T> inline int sz(const T& v) { return std::size(v); }
template <typename T> inline T floor(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }
template <typename T> inline T ceil(T a, T b) { return floor(a + b - 1, b); }
template <typename T, std::size_t N> std::vector<T> make_vector_impl(std::vector<ll>& sizes, typename std::enable_if<(N == 1), const T&>::type x) { 
    return std::vector<T>(sizes.front(), x); }
template <typename T, std::size_t N> auto make_vector_impl(std::vector<ll>& sizes, typename std::enable_if<(N > 1), const T&>::type x) { ll size = 
    sizes.back(); sizes.pop_back(); return std::vector<decltype(make_vector_impl<T, N - 1>(sizes, x))>(size, make_vector_impl<T, N - 1>(sizes, x)); }
template <typename T, std::size_t N> auto make_vector(const ll (&sizes)[N], const T& x = T()) { std::vector<ll> s(std::rbegin(sizes), std::rend(sizes
    )); return make_vector_impl<T, N>(s, x); }
template <typename T, std::size_t N> std::array<T, N> make_array() { return std::array<T, N>{}; }
template <typename T, std::size_t Head, std::size_t... Tail, typename std::enable_if_t<(sizeof...(Tail) >= 1), std::nullptr_t> = nullptr> auto 
    make_array() { return std::array<decltype(make_array<T, Tail...>()), Head>(); }
template <typename T = ll> std::pair<T, T> nibutan(T left, T right, const auto&& f) { while (std::abs(right - left) > 1) { T mid = left + (right - 
    left) / 2; (f(mid) ? left : right) = mid; } return {left, right}; }
template <typename T = double> std::pair<T, T> nibutan_double(T threshold, T left, T right, const auto&& f) { int c = std::log2(std::abs(right - left
    ) / threshold) + 3; while (std::abs(right - left) > threshold && c--) { T mid = left + (right - left) / 2; (f(mid) ? left : right) = mid; } 
    return {left, right}; }
namespace std {
    template <typename T, typename std::enable_if_t<std::is_same_v<T, __int128_t> || std::is_same_v<T, __uint128_t>, std::nullptr_t> = nullptr> std
        ::string to_string(T n) { if (n == 0) return "0"; bool minus = n < 0; if (minus) n = -n; std::string r; while (n > 0) r += '0' + n % 10, n /= 
        10; if (minus) r += '-'; reverse(r.begin(), r.end()); return r; }
    template <typename T, typename std::enable_if_t<std::is_same_v<T, __int128_t> || std::is_same_v<T, __uint128_t>, std::nullptr_t> = nullptr> std
        ::ostream& operator<<(std::ostream& s, const T& n) { return s << to_string(n); }
}
template <bool Index, typename... T> class zip_helper {
    template <class Category, class Type, class Diff = ptrdiff_t, class Ptr = Type*, class Ref = Type&> struct basic_iterator {
        using difference_type = Diff;
        using value_type = Type;
        using pointer = Ptr;
        using reference = Ref;
        using iterator_category = Category;
    };
    class zip_iterator : public basic_iterator<std::forward_iterator_tag, std::tuple<decltype(*std::declval<T>().begin())...>> {
    public:
        int idx_;
        std::tuple<decltype(std::declval<T>().begin())...> iters_;
        template <std::size_t... I> auto deref(std::index_sequence<I...>) const { return typename zip_iterator::value_type{*std::get<I>(iters_)...}; 
            }
        template <std::size_t... I> void increment(std::index_sequence<I...>) { [[maybe_unused]] auto l = {(++std::get<I>(iters_), 0)...}; }
        explicit zip_iterator(decltype(iters_) iters) : idx_(0), iters_{std::move(iters)} {}
        zip_iterator& operator++() { ++idx_; increment(std::index_sequence_for<T...>{}); return *this; }
        zip_iterator operator++(int) { auto saved{*this}; ++idx_; increment(std::index_sequence_for<T...>{}); return saved; }
        bool operator!=(const zip_iterator& other) const { return iters_ != other.iters_; }
        template <bool Index_ = Index, typename std::enable_if_t<Index_, std::nullptr_t> = nullptr> auto operator*() const { return std::tuple_cat
            (std::make_tuple(this->idx_), this->deref(std::index_sequence_for<T...>{})); }
        template <bool Index_ = Index, typename std::enable_if_t<!Index_, std::nullptr_t> = nullptr> auto operator*() const { return this->deref(std
            ::index_sequence_for<T...>{}); }
    };
public:
    zip_helper(T&... seqs) : begin_{std::make_tuple(seqs.begin()...)}, end_{std::make_tuple(seqs.end()...)} {}
    zip_iterator begin() const { return begin_; }
    zip_iterator end() const { return end_; }
    zip_iterator begin_, end_;
};
template <typename... T> auto zip(T&&... seqs) { return zip_helper<false, T...>{seqs...}; }
template <typename... T> auto zipindex(T&&... seqs) { return zip_helper<true, T...>{seqs...}; }
#if __has_include(<ext/pb_ds/assoc_container.hpp>)
#include <bits/extc++.h>
class custom_hash {
public:
    constexpr static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15, x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9, x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);
    }
    std::size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM);
    }
    template <typename Lazy, typename T2> std::size_t operator() (const std::pair<Lazy, T2>& x) const {
        std::size_t lhs = operator()(x.first), rhs = operator()(x.second); return lhs ^ (rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2));
    }
    template <typename C, typename T = std::decay_t<decltype(*begin(std::declval<C>()))>> std::size_t operator()(const C& container) const {
        std::size_t h = container.size(); for (auto&& k : container) h ^= operator()(k) + 0x9e3779b9 + (h << 6) + (h >> 2); return h;
    }
};
template <typename Key, typename Mapped, typename Hash = custom_hash> using fmapbase = __gnu_pbds::gp_hash_table<Key, Mapped, Hash, equal_to<Key>, 
    __gnu_pbds::direct_mask_range_hashing<>, __gnu_pbds::linear_probe_fn<>, __gnu_pbds::hash_standard_resize_policy<__gnu_pbds
    ::hash_exponential_size_policy<>, __gnu_pbds::hash_load_check_resize_trigger<>, true>>;
template <typename Key, typename Mapped, typename Hash = custom_hash> class fmap : public fmapbase <Key, Mapped, Hash> {
public:
    using fmapbase<Key, Mapped, Hash>::gp_hash_table;
    template <typename Mapped_ = Mapped, typename std::enable_if_t<std::is_same_v<Mapped_, __gnu_pbds::null_type>, std::nullptr_t> = nullptr> fmap
        (std::initializer_list<Key> il) : fmapbase<Key, Mapped, Hash>(il.begin(), il.end()) {}
    template <typename Mapped_ = Mapped, typename std::enable_if_t<!std::is_same_v<Mapped_, __gnu_pbds::null_type>, std::nullptr_t> = nullptr> fmap
        (std::initializer_list<std::pair<Key, Mapped>> il) : fmapbase<Key, Mapped, Hash>(il.begin(), il.end()) {}
    void reserve(std::size_t n) {
        fmapbase<Key, Mapped, Hash>::resize(n);
    }
    template <typename T> int count(const T& x) const {
        return fmapbase<Key, Mapped, Hash>::find(x) != fmapbase<Key, Mapped, Hash>::end();
    }
};
template <typename Key, typename Hash = custom_hash> using fset = fmap<Key, __gnu_pbds::null_type, Hash>;
#ifdef LOCAL_TEST
template <typename Key, typename Mapped, typename Hash> std::ostream& operator<<(std::ostream& s, fmapbase<Key, Mapped, Hash>& m) { s << "{\n"; for 
    (auto it = m.begin(); it != m.end(); ++it){ s << "\t" << it->first << " : " << it->second << "\n"; } s << "}"; return s; }
template <typename Key, typename Mapped, typename Hash> std::ostream& operator<<(std::ostream& s, const fmapbase<Key, Mapped, Hash>& m) { s << "{\n"; 
    for (auto it = m.begin(); it != m.end(); ++it){ s << "\t" << it->first << " : " << it->second << "\n"; } s << "}"; return s; }
template <typename Key, typename Hash> std::ostream& operator<<(std::ostream& s, fmapbase<Key, __gnu_pbds::null_type, Hash>& se) { s << "{ "; for 
    (auto it = se.begin(); it != se.end(); ++it){ s << *it << "\t"; } s << "}"; return s; }
template <typename Key, typename Hash> std::ostream& operator<<(std::ostream& s, const fmapbase<Key, __gnu_pbds::null_type, Hash>& se) { s << "{ "; 
    for (auto it = se.begin(); it != se.end(); ++it){ s << *it << "\t"; } s << "}"; return s; }
#endif
#else
template <typename Key, typename Mapped> using fmap = std::unordered_map<Key, Mapped>;
template <typename Key> using fset = std::unordered_set<Key>;
#endif
/*-----8<-----template-----8<-----*/
//[lib]linkcuttreeパス3.cpp
//https://xuzijian629.hatenablog.com/entry/2019/10/28/151212
// Data: 元の配列のモノイド
// Lazy: Dataに対する作用素モノイド
template <typename Monoid>
class LinkCutTree {
    using Data = typename Monoid::Data;
    using Lazy = typename Monoid::Lazy;
    //const Data u0;
    //const Lazy u1;
    // Data上の演算、単位元
    //virtual Data f0(Data, Data) = 0;
    // Dataに対するLazyの作用
    //virtual Data g(Data, Lazy) = 0;
    // Lazy上の演算、単位元
    //virtual Lazy f1(Lazy, Lazy) = 0;
    // 多数のLazy(Lazy)に対するf1の合成
    //virtual Lazy p(Lazy, int) = 0;
    class Node {
    public:
        int idx, cnt;
        Data val, acc;
        Lazy lazy;
        Node *left, *right, *par;
        Node(int idx, const Data& val, const Data& u0, const Lazy& u1)
            : idx(idx), cnt(1), val(val), acc(u0), lazy(u1), left(nullptr), right(nullptr), par(nullptr) {}
        bool is_root() { return (!par) || (par->left != this && par->right != this); }
    };
    void push(Node* t) {
        if (t->cnt < 0) {
            swap(t->left, t->right);
            if (t->left) t->left->cnt = -(t->left->cnt);
            if (t->right) t->right->cnt = -(t->right->cnt);
            t->cnt = -t->cnt;
        }
        if (t->lazy != Monoid::unitLazy()) {
            t->val = Monoid::g(t->val, t->lazy, 1);
            t->acc = Monoid::g(t->acc, t->lazy, t->cnt);
            if (t->left) t->left->lazy = Monoid::g(t->left->lazy, t->lazy, 1);
            if (t->right) t->right->lazy = Monoid::g(t->right->lazy, t->lazy, 1);
            t->lazy = Monoid::unitLazy();
        }
    }
    void eval(Node* t) {
        bool flag = (t->cnt < 0);
        t->cnt = 1, t->acc = t->val;
        if (t->left) push(t->left), t->cnt += _abs(t->left->cnt), t->acc = Monoid::f(t->left->acc, t->acc);
        if (t->right) push(t->right), t->cnt += _abs(t->right->cnt), t->acc = Monoid::f(t->acc, t->right->acc);
        if (flag) t->cnt = -t->cnt;
    }
    vector<Node*> nodes;
    inline static int _abs(int val) { return val & 0x7fffffff; }
    // 回転
    void rotate(Node* u, bool right) {
        Node *p = u->par, *g = p->par;
        if (right) {
            if ((p->left = u->right)) u->right->par = p;
            u->right = p, p->par = u;
        } else {
            if ((p->right = u->left)) u->left->par = p;
            u->left = p, p->par = u;
        }
        eval(p), eval(u), u->par = g;
        if (!g) return;
        if (g->left == p) g->left = u;
        if (g->right == p) g->right = u;
        eval(g);
    }
    // uをsplay木の根にする
    void splay(Node* u) {
        while (!(u->is_root())) {
            Node *p = u->par, *gp = p->par;
            if (p->is_root()) {  // zig
                push(p), push(u);
                rotate(u, (u == p->left));
            } else {
                push(gp), push(p), push(u);
                bool flag = (u == p->left);
                if ((u == p->left) == (p == gp->left)) {  // zig-zig
                    rotate(p, flag), rotate(u, flag);
                } else {  // zig-zag
                    rotate(u, flag), rotate(u, !flag);
                }
            }
        }
        push(u);
    }
    Node* expose(Node* u) {
        Node* last = nullptr;
        for (Node* v = u; v; v = v->par) {
            splay(v);
            v->right = last;
            eval(v);
            last = v;
        }
        splay(u);
        return last;
    }
    bool is_connected(Node* u, Node* v) {
        expose(u), expose(v);
        return u->par;
    }
    // u(child)とv(parent)を結ぶ
    void link(Node* u, Node* v) {
        assert(!is_connected(u, v));
        evert(u), u->par = v;
    }
    // uと親を切り離す
    void cut(Node* u) {
        expose(u);
        assert(u->left);
        u->left->par = nullptr, u->left = nullptr, eval(u);
    }
    Node* lca(Node* u, Node* v) {
        // assert(is_connected(u, v));
        expose(u);
        return expose(v);
    }
    Node* get_kth(Node* v, int k) {
        expose(v);
        while (v) {
            eval(v);
            if (v->right && v->right->cnt > k) {
                v = v->right;
            } else {
                if (v->right) k -= v->right->cnt;
                if (k == 0) return v;
                k--;
                v = v->left;
            }
        }
        return nullptr;
    }
    Node* get_root(Node* v) {
        expose(v);
        while (v->left) {
            eval(v);
            v = v->left;
        }
        return v;
    }
    void evert(Node* u) { expose(u), u->cnt = -(u->cnt); }
    int depth(Node* u) {
        expose(u);
        return _abs(u->cnt) - 1;
    }
    void update(Node* u, Node* v, const Lazy x) {
        evert(u), expose(v);
        v->lazy = Monoid::h(v->lazy, x), push(v);
    }
    Data query(Node* u, Node* v) {
        evert(u), expose(v);
        return v->acc;
    }
public:
    LinkCutTree() {}
    ~LinkCutTree() {
        for(int i = 0; i < (int)nodes.size(); ++i) delete nodes[i];
    }
    LinkCutTree(LinkCutTree&& r) noexcept { *this = std::move(r); }
    inline LinkCutTree& operator=(LinkCutTree&& r) noexcept {
        for(int i = 0; i < (int)nodes.size(); ++i) delete nodes[i];
        nodes = std::move(r.nodes);
        return *this;
    }
    int make_new_node(const Data& v) {
        int idx = nodes.size();
        nodes.push_back(new Node(idx, v, Monoid::unitData(), Monoid::unitLazy()));
        return idx;
    }
    bool is_connected(int a, int b) { return is_connected(nodes[a], nodes[b]); }
    // uとvをつなぐ(evertせずに使える)
    void link(int u, int v) { return link(nodes[u], nodes[v]); }
    // vを親と切り離す
    void cut(int v) { cut(nodes[v]); }
    void cut(int u, int v) { evert(u); cut(nodes[v]); }
    int lca(int u, int v) { return lca(nodes[u], nodes[v])->idx; }
    // vから根にk個たどった頂点を返す。とくにget_kth(v, 0)はv
    int get_kth(int v, int k) { return get_kth(nodes[v], k)->idx; }
    int get_kth(int from, int to, int k) { evert(to); return get_kth(nodes[from], k)->idx; }
    int get_root(int v) { return get_root(nodes[v])->idx; }
    // vを根にもってくる
    void evert(int v) { evert(nodes[v]); }
    int depth(int v) { return depth(nodes[v]); }
    // uvパスに現れるすべての頂点にxを作用させる
    void update(int u, int v, const Lazy& x) { update(nodes[u], nodes[v], x); }
    void update(int v, const Lazy& x) { update(v, v, x); }
    // uvパスに現れるすべての頂点の累積を求める
    Data query(int u, int v) { return query(nodes[u], nodes[v]); }
    Data query(int v) { return query(v, v); }
};
template <class Data_, class Lazy_>
class MaxAddQuery {
public:
    using Data = Data_;
    using Lazy = Lazy_;
    static inline constexpr Data unitData() { return numeric_limits<Data>::min(); }
    static inline constexpr Lazy unitLazy() { return 0; }
    static inline constexpr Data f(const Data& x, const Data& y) { return max(x, y); }
    static inline constexpr Data g(const Data& x, const Lazy& y, int len) { return x + y; }
    static inline constexpr Lazy h(const Lazy& x, const Lazy& y) { return x + y; }
};
template <class Data_, class Lazy_>
class MaxReplaceQuery {
public:
    using Data = Data_;
    using Lazy = Lazy_;
    static inline constexpr Data unitData() { return numeric_limits<Data>::min(); }
    static inline constexpr Lazy unitLazy() { return numeric_limits<Lazy>::max(); }
    static inline constexpr Data f(const Data& x, const Data& y) { return max(x, y); }
    static inline constexpr Data g(const Data& x, const Lazy& y, int) { return y == unitLazy() ? x : y; }
    static inline constexpr Lazy h(const Lazy& x, const Lazy& y) { return y == unitLazy() ? x : y; }
};
template <class Data_, class Lazy_>
class MinAddQuery {
public:
    using Data = Data_;
    using Lazy = Lazy_;
    static inline constexpr Data unitData() { return numeric_limits<Data>::max(); }
    static inline constexpr Lazy unitLazy() { return 0; }
    static inline constexpr Data f(const Data& x, const Data& y) { return min(x, y); }
    static inline constexpr Data g(const Data& x, const Lazy& y, int len) { return x + y; }
    static inline constexpr Lazy h(const Lazy& x, const Lazy& y) { return x + y; }
};
template <class Data_, class Lazy_>
class MinReplaceQuery {
public:
    using Data = Data_;
    using Lazy = Lazy_;
    static inline constexpr Data unitData() { return numeric_limits<Data>::max(); }
    static inline constexpr Lazy unitLazy() { return numeric_limits<Lazy>::min(); }
    static inline constexpr Data f(const Data& x, const Data& y) { return min(x, y); }
    static inline constexpr Data g(const Data& x, const Lazy& y, int) { return y == unitLazy() ? x : y; }
    static inline constexpr Lazy h(const Lazy& x, const Lazy& y) { return y == unitLazy() ? x : y; }
};
template <class Data_, class Lazy_>
class SumAddQuery {
public:
    using Data = Data_;
    using Lazy = Lazy_;
    static inline constexpr Data unitData() { return 0; }
    static inline constexpr Lazy unitLazy() { return 0; }
    static inline constexpr Data f(const Data& x, const Data& y) { return x + y; }
    static inline constexpr Data g(const Data& x, const Lazy& y, int len) { return x + y * len; }
    static inline constexpr Lazy h(const Lazy& x, const Lazy& y) { return x + y; }
};
template <class Data_, class Lazy_>
class SumReplaceQuery {
public:
    using Data = Data_;
    using Lazy = Lazy_;
    static inline constexpr Data unitData() { return 0; }
    static inline constexpr Lazy unitLazy() { return numeric_limits<Lazy>::min(); }
    static inline constexpr Data f(const Data& x, const Data& y) { return x + y; }
    static inline constexpr Data g(const Data& x, const Lazy& y, int len) { return y == unitLazy() ? x : y * len; }
    static inline constexpr Lazy h(const Lazy& x, const Lazy& y) { return y == unitLazy() ? x : y; }
};
template <class Data_>
class SumAffineQuery {
public:
    using Data = Data_;
    using Lazy = pair<Data_, Data_>;  // first * x + second
    static inline constexpr Data unitData() { return 0; }
    static inline constexpr Lazy unitLazy() { return {1, 0}; }
    static inline constexpr Data f(const Data& x, const Data& y) { return x + y; }
    static inline constexpr Data g(const Data& x, const Lazy& y, int len) { return y.first * x + y.second * len; }
    static inline constexpr Lazy h(const Lazy& x, const Lazy& y) { return {x.first * y.first, x.second * y.first + y.second}; }
    // update(i, j, {a, b}); // [i, j)にax + bを作用
    // update(i, j, {0, a}); // update
    // update(i, j, {1, a}); // 加算
    // update(i, j, {a, 0}); // 倍
};
template <class T>
class MinmaxAffineQuery {
public:
    using Data = pair<T, T>;  // {min, max}
    using Lazy = pair<T, T>;  // first * x + second
    // TODO: _u1を使うとコンパイル通らない原因不明
    static inline constexpr Data unitData() { return {numeric_limits<T>::max(), -numeric_limits<T>::max()}; }
    static inline constexpr Lazy unitLazy() { return {1, 0}; }
    static inline constexpr Data f(const Data& x, const Data& y) { return {min(x.first, y.first), max(x.second, y.second)}; }
    static inline constexpr Data g(const Data& x, const Lazy& y, int) {
        Data ret = {x.first * y.first + y.second, x.second * y.first + y.second};
        if (y.first < 0) swap(ret.first, ret.second);
        return ret;
    }
    static inline constexpr Lazy h(const Lazy& x, const Lazy& y) { return {x.first * y.first, x.second * y.first + y.second}; }
    // update(i, j, {a, b}); // [i, j)にax + bを作用
    // update(i, j, {0, a}); // update
    // update(i, j, {1, a}); // 加算
    // update(i, j, {a, 0}); // 倍
};
/*-----8<-----library-----8<-----*/
void solve() {
    /*
    頂点に値を持たせたいとき
    →特に考慮不要
    辺に値を持たせたいとき
    →頂点数を 2*N-1 個用意
    a,b間を繋ぐときは、 a-ダミー頂点-b で繋ぐ
    辺の値はダミー頂点に持たせる
    */
    LinkCutTree<SumReplaceQuery<ll, ll>> lct;
    ll N;
    cin >> N;
    for (int i = 0; i < N * 2 - 1; i++) lct.make_new_node(0);
    rep(i, N-1) {
        ll u, v, w;
        cin >> u >> v >> w;
        ll dummy = N + i;
        lct.link(u, dummy);
        lct.link(v, dummy);
        lct.update(dummy, w);
    }
    ll Q;
    cin >> Q;
    while (Q--) {
        ll type;
        cin >> type;
        if (type == 1) {
            ll u, v, w, x;
            cin >> u >> v >> w >> x;
            ll dummy = lct.get_kth(u, v, 1);
            lct.cut(u, dummy);
            lct.link(w, dummy);
            lct.update(dummy, x);
        } else {
            ll K;
            cin >> K;
            vector<ll> X(K);
            rep(i, K) cin >> X[i];
            ll r = X[0];
            sort(all(X), [&](auto a, auto b) -> bool {
                if (a == b) return false;
                lct.evert(r);
                int c = lct.lca(a, b);
                if (a == c) return true;
                if (b == c) return false;
                int x = lct.get_kth(c, a, 1);
                int y = lct.get_kth(c, b, 1);
                return x < y;
            });
            X.emplace_back(r);
            ll ans = 0;
            rep(i, K) {
                ll t = lct.query(X[i], X[i + 1]);
                ans += t;
            }
            ans /= 2;
            cout << ans << endl;
        }
    }
}
signed main() {
#ifdef LOCAL_DEV
    /*
    std::ifstream in("in.txt");
    std::cin.rdbuf(in.rdbuf());
    //*/
#else
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
#endif
    /*
    ll Q; cin >> Q; while(Q--)solve();
    /*/
    solve();
    //*/
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0