//#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;
}