/*
 * @uni_kakurenbo
 * https://github.com/uni-kakurenbo/competitive-programming-workspace
 *
 * CC0 1.0  http://creativecommons.org/publicdomain/zero/1.0/deed.ja
 */
/* #language C++ 20 GCC */
/* [begin]: template/debug.hpp */
/* [begin]: debugger/debug.hpp */
#include <iostream>
#include <limits>
#include <iterator>
#include <string_view>
#include <sstream>
#include <array>
#include <string>
#include <cstring>
#include <vector>
#include <bitset>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <utility>
#include <iomanip>
#include <ranges>
#include <concepts>
#include <type_traits>
/* [begin]: numeric/int128.hpp */
#include <cctype>
#include <cassert>
#include <algorithm>
/* [begin]: snippet/internal/types.hpp */
#include <cstdint>
namespace uni { using i16 = std::int16_t; using u16 = std::uint16_t; using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t;
#ifdef __GNUC__
using i128 = __int128_t; using u128 = __uint128_t;
#endif
using uint = unsigned; using ll = long long; using ull = unsigned long long; using ld = long double; }
/* [end]: snippet/internal/types.hpp*/
/* [begin]: snippet/iterations.hpp */
/* [begin]: macro/overload.hpp */
#define $OVERLOAD2(arg0, arg1, cmd, ...) cmd
#define $OVERLOAD3(arg0, arg1, arg2, cmd, ...) cmd
#define $OVERLOAD4(arg0, arg1, arg2, arg3, cmd, ...) cmd
#define $OVERLOAD5(arg0, arg1, arg2, arg3, arg4, cmd, ...) cmd
#define $OVERLOAD6(arg0, arg1, arg2, arg3, arg4, arg5, cmd, ...) cmd
/* [end]: macro/overload.hpp*/
#define LOOP(n) REPI(_$, (n))
#define REPI(i,n) for(std::decay_t<decltype(n)> i=0, i##_length=(n); i<i##_length; ++i)
#define REPF(i,l,r) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>> i=(l), i##_last=(r); i<i##_last; ++i)
#define REPIS(i,l,r,s) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>,std::decay_t<decltype(s)>> i=(l), i##_last=(r); i<i##_last; i+=(s))
#define REPR(i,n) for(auto i=(n); --i>=0;)
#define REPB(i,l,r) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>> i=(r), i##_last=(l); --i>=i##_last;)
#define REPRS(i,l,r,s) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>,std::decay_t<decltype(s)>> i=(l)+((r)-(l)-1)/(s)*(s), i##_last=(l); i>=i##_last; (i-=(s)))
#define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__)
#define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__)
#define FORO(i,n) for(int i=0, i##_last=static_cast<int>(n); i<=i##_last; ++i)
#define FORI(i,l,r) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>> i=(l), i##_last=(r); i<=i##_last; ++i)
#define FORIS(i,l,r,s) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>,std::decay_t<decltype(s)>> i=(l), i##_last=(r); i<=i##_last; i+=(s))
#define FORRO(i,n) for(auto i=(n); i>=0; --i)
#define FORR(i,l,r) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>> i=(r), i##_last=(l); i>=i##_last; --i)
#define FORRS(i,l,r,s) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>,std::decay_t<decltype(s)>> i=(l)+((r)-(l))/(s)*(s), i##_last=(l); i>=i##_last; i-=(s))
#define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI, FORO)(__VA_ARGS__)
#define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR, FORRO)(__VA_ARGS__)
#define ITR1(e0,v) for(const auto &e0 : (v))
#define ITRP1(e0,v) for(auto e0 : (v))
#define ITRR1(e0,v) for(auto &e0 : (v))
#define ITR2(e0,e1,v) for(const auto [e0, e1] : (v))
#define ITRP2(e0,e1,v) for(auto [e0, e1] : (v))
#define ITRR2(e0,e1,v) for(auto &[e0, e1] : (v))
#define ITR3(e0,e1,e2,v) for(const auto [e0, e1, e2] : (v))
#define ITRP3(e0,e1,e2,v) for(auto [e0, e1, e2] : (v))
#define ITRR3(e0,e1,e2,v) for(auto &[e0, e1, e2] : (v))
#define ITR4(e0,e1,e2,e3,v) for(const auto [e0, e1, e2, e3] : (v))
#define ITRP4(e0,e1,e2,e3,v) for(auto [e0, e1, e2, e3] : (v))
#define ITRR4(e0,e1,e2,e3,v) for(auto &[e0, e1, e2, e3] : (v))
#define ITR5(e0,e1,e2,e3,e4,v) for(const auto [e0, e1, e2, e3, e4] : (v))
#define ITRP5(e0,e1,e2,e3,e4,v) for(auto [e0, e1, e2, e3, e4] : (v))
#define ITRR5(e0,e1,e2,e3,e4,v) for(auto &[e0, e1, e2, e3, e4] : (v))
#define ITR(...) $OVERLOAD6(__VA_ARGS__, ITR5, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__)
#define ITRP(...) $OVERLOAD6(__VA_ARGS__, ITRP5, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__)
#define ITRR(...) $OVERLOAD6(__VA_ARGS__, ITRR5, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__)
/* [end]: snippet/iterations.hpp*/
/* [begin]: internal/dev_env.hpp */
#ifdef LOCAL_JUDGE
inline constexpr bool DEV_ENV = true; inline constexpr bool NO_EXCEPT = false;
#else
inline constexpr bool DEV_ENV = false; inline constexpr bool NO_EXCEPT = true;
#endif
#if __cplusplus >= 202100L
#define CPP20 true
#define CPP23 true
#elif __cplusplus >= 202002L
#define CPP20 true
#define CPP23 false
#else
#define CPP20 false
#define CPP23 false
#endif
/* [end]: internal/dev_env.hpp*/
namespace std { template<class C, class S> basic_istream<C,S>& operator>>(std::basic_istream<C,S>& in, uni::i128& v) noexcept(NO_EXCEPT) { std::string str; in >> str; v = 0; bool negative = (str[0] == '-'); REP(d, std::next(str.begin(), negative), str.end()) { assert(std::isdigit(*d)); v = v * 10 + *d - '0'; } if(negative) v *= -1; return in; } template<class C, class S> basic_istream<C,S>& operator>>(std::basic_istream<C,S>& in, uni::u128& v) noexcept(NO_EXCEPT) { std::string str; in >> str; v = 0U; assert(str[0] != '-'); REP(d, str.begin(), str.end()) { assert(std::isdigit(*d)); v = v * 10U + *d - '0'; } return in; } template<class C, class S> basic_ostream<C,S>& operator<<(std::basic_ostream<C,S>& out, uni::i128 v) noexcept(NO_EXCEPT) { if(v == 0) return out << 0; if(v < 0) out << '-', v *= -1; std::string str; while(v > 0) str += static_cast<char>(v%10) + '0', v /= 10; std::reverse(str.begin(), str.end()); return out << str; } template<class C, class S> basic_ostream<C,S>& operator<<(std::basic_ostream<C,S>& out, uni::u128 v) noexcept(NO_EXCEPT) { if(v == 0) return out << 0U; std::string str; while(v > 0) str += static_cast<char>(v%10U) + '0', v /= 10U; std::reverse(str.begin(), str.end()); return out << str; } }
/* [end]: numeric/int128.hpp*/
/* [begin]: internal/type_traits.hpp */
namespace uni { namespace internal { template<class... Ts> struct tuple_or_pair { using type = std::tuple<Ts...>; }; template<class T, class U> struct tuple_or_pair<T,U> { using type = std::pair<T, U>; }; template <class... Ts> using tuple_or_pair_t = typename tuple_or_pair<Ts...>::type; template<class T> constexpr std::underlying_type_t<T> to_underlying(const T& v) noexcept(NO_EXCEPT) { return static_cast<std::underlying_type_t<T>>(v); } template<class T, class... Ts> using are_same = std::conjunction<std::is_same<T, Ts>...>; template<class T, class... Ts> inline constexpr bool are_same_v = are_same<T, Ts...>::value; template<class T, class... Ts> using is_same_as_any_of = std::disjunction<std::is_same<T, Ts>...>; template<class T, class... Ts> inline constexpr bool is_same_as_any_of_v = is_same_as_any_of<T, Ts...>::value; template<class T, class... Ts> concept same_as_any_of = is_same_as_any_of_v<T, Ts...>; template<class Base, class... Derived> using is_base_of_all = std::conjunction<std::is_base_of<Base, Derived>...>; template<class Base, class... Derived> inline constexpr bool is_base_of_all_v = is_base_of_all<Base, Derived...>::value; template<class Base, class... Derived> using is_base_of_any = std::disjunction<std::is_base_of<Base, Derived>...>; template<class Base, class... Derived> inline constexpr bool is_base_of_any_v = is_base_of_any<Base, Derived...>::value; template<class T> struct remove_cvref { using type = typename std::remove_cv_t<std::remove_reference_t<T>>; }; template<class T> using remove_cvref_t = typename remove_cvref<T>::type; template<class T> struct literal_operator { static constexpr const char* value = ""; }; template<> struct literal_operator<unsigned> { static constexpr const char* value = "U"; }; template<> struct literal_operator<long> { static constexpr const char* value = "L"; }; template<> struct literal_operator<unsigned long> { static constexpr const char* value = "UL"; }; template<> struct literal_operator<long long> { static constexpr const char* value = "LL"; }; template<> struct literal_operator<unsigned long long> { static constexpr const char* value = "ULL"; }; template<> struct literal_operator<float> { static constexpr const char* value = "F"; }; template<> struct literal_operator<double> { static constexpr const char* value = "D"; }; template<> struct literal_operator<long double> { static constexpr const char* value = "LD"; };
#ifdef __SIZEOF_INT128__
template<> struct literal_operator<__int128_t> { static constexpr const char* value = "LLL"; }; template<> struct literal_operator<__uint128_t> { static constexpr const char* value = "ULLL"; };
#endif
template<class T> inline constexpr auto literal_operator_v = literal_operator<T>::value; template <std::size_t N, typename... Types> struct nth_type {}; template <class Head, class... Tail> struct nth_type<0, Head, Tail...> { using type = Head; }; template <std::size_t N, class Head, class... Tail> struct nth_type<N, Head, Tail...> : public nth_type<N - 1, Tail...> {}; template <std::size_t N, typename... Types> using nth_type_t = typename nth_type<N, Types...>::type; template<template <class...> class, class> struct is_template_of : std::false_type {}; template<template <class...> class Template, class... Args> struct is_template_of<Template, Template<Args...>> : std::true_type {}; template<template <class...> class Template, class Type> inline constexpr bool is_template_of_v = is_template_of<Template, Type>::value; template<class Type, template <class...> class Template> concept substituted_from = is_template_of_v<Template, Type>; template<template <class...> class Base, class Derived> struct _is_basic_tempalte_of { template<class... Ts> static constexpr std::true_type test(const Base<Ts...> *); static constexpr std::false_type test(...); using type = decltype(test(std::declval<Derived*>())); }; template<template <class...> class Base, class Derived> using is_basic_tempalte_of = _is_basic_tempalte_of<Base, Derived>::type; template<template <class...> class Base, class Derived> inline constexpr bool is_basic_tempalte_of_v = is_basic_tempalte_of<Base, Derived>::value; template<class Derived, template <class...> class Base> concept derived_from_template = is_basic_tempalte_of_v<Base, Derived>; template<class T> struct is_loggable { template<class U> static constexpr auto External(U &&v) -> decltype(_debug(v), std::true_type()); static constexpr std::false_type External(...); template<class U> static constexpr auto Member(U &&v) -> decltype(v._debug(), std::true_type()); static constexpr std::false_type Member(...); static constexpr bool value = ( decltype(External(std::declval<T>()))::value || decltype(Member(std::declval<T>()))::value ); }; template<class T> inline constexpr auto is_loggable_v = is_loggable<T>::value; template<class T> concept loggable = is_loggable_v<T>; template<class T> struct _has_iterator { template<class U> static constexpr auto ADL(U &&v) -> decltype(begin(v), end(v), std::true_type()); static constexpr std::false_type ADL(...); template<class U> static constexpr auto STL(U &&v) -> decltype(std::begin(v), std::end(v), std::true_type()); static constexpr std::false_type STL(...); template<class U> static constexpr auto Member(U &&v) -> decltype(v.begin(), v.end(), std::true_type()); static constexpr std::false_type Member(...); }; template<class T> struct has_iterator { struct ADL : decltype(_has_iterator<T>::ADL(std::declval<T>())) {}; struct STL : decltype(_has_iterator<T>::STL(std::declval<T>())) {}; struct Member : decltype(_has_iterator<T>::Member(std::declval<T>())) {}; static constexpr auto adl_v = ADL::value; static constexpr auto stl_v = STL::value; static constexpr auto member_v = Member::value; }; template<class T> struct is_iterable { static constexpr bool value = has_iterator<T>::adl_v || has_iterator<T>::stl_v || has_iterator<T>::member_v; }; template<class T> inline constexpr auto is_iterable_v = is_iterable<T>::value; template<class T> concept iterable = is_iterable_v<T>; namespace iterator_resolver { template<class T> inline constexpr auto begin(T&& v) noexcept(NO_EXCEPT) { static_assert(is_iterable_v<T>); if constexpr(has_iterator<T>::member_v) { return v.begin(); } else { using std::begin; return begin(std::forward<T>(v)); } } template<class T> inline constexpr auto end(T&& v) noexcept(NO_EXCEPT) { static_assert(is_iterable_v<T>); if constexpr(has_iterator<T>::member_v) { return v.end(); } else { using std::end; return end(std::forward<T>(v)); } } }; template<class C> using iterator_t = decltype(iterator_resolver::begin(std::declval<C&>())); template<class C> using container_size_t = decltype(std::size(std::declval<C&>())); template<bool Const, class T> using maybe_const_t = std::conditional_t<Const, const T, T>; template<class T> using with_ref = T&; template<class T> concept can_reference = requires { typename with_ref<T>; }; } }
/* [end]: internal/type_traits.hpp*/
/* [begin]: internal/concepts.hpp */
#include <functional>
namespace uni { namespace internal { template<class Structure> concept available = requires () { typename Structure; }; template< template<class...> class Structure, class... TemplateParameters > concept available_with = available<Structure<TemplateParameters...>>; template<class T> concept arithmetic = std::is_arithmetic_v<T>; template<class T> concept pointer = std::is_pointer_v<T>; template<class T> concept structural = std::is_class_v<T>; template<class Large, class Small> concept has_double_digits_of = (std::numeric_limits<Large>::digits == 2 * std::numeric_limits<Small>::digits); template<class Large, class Small> concept has_more_digits_than = (std::numeric_limits<Large>::digits > std::numeric_limits<Small>::digits); template<class Large, class Small> concept has_or_more_digits_than = (std::numeric_limits<Large>::digits >= std::numeric_limits<Small>::digits); template<class T> concept has_static_zero = requires { T::zero; }; template<class T> concept has_static_one = requires { T::one; }; template<class L, class R = L> concept weakly_addable = requires (L lhs, R rhs) { lhs + rhs; }; template<class L, class R = L> concept weakly_subtractable = requires (L lhs, R rhs) { lhs - rhs; }; template<class L, class R = L> concept weakly_multipliable = requires (L lhs, R rhs) { lhs * rhs; }; template<class L, class R = L> concept weakly_divisable = requires (L lhs, R rhs) { lhs / rhs; }; template<class L, class R = L> concept weakly_remainder_calculable = requires (L lhs, R rhs) { lhs % rhs; }; template<class L, class R = L> concept weakly_addition_assignable = requires (L lhs, R rhs) { lhs += rhs; }; template<class L, class R = L> concept weakly_subtraction_assignable = requires (L lhs, R rhs) { lhs -= rhs; }; template<class L, class R = L> concept weakly_multipliation_assignalbe = requires (L lhs, R rhs) { lhs *= rhs; }; template<class L, class R = L> concept weakly_division_assignable = requires (L lhs, R rhs) { lhs /= rhs; }; template<class L, class R = L> concept weakly_remainder_assignable = requires (L lhs, R rhs) { lhs /= rhs; }; template<class L, class R = L> concept addable = weakly_addable<L, R> && weakly_addable<std::invoke_result_t<std::plus<>&, L, R>, R> && weakly_addable<L, std::invoke_result_t<std::plus<>&, L, R>> && weakly_addable<std::invoke_result_t<std::plus<>&, L, R>, std::invoke_result_t<std::plus<>&, L, R>>; template<class L, class R = L> concept subtractable = weakly_subtractable<L, R> && weakly_subtractable<std::invoke_result_t<std::minus<>&, L, R>, R> && weakly_subtractable<L, std::invoke_result_t<std::minus<>&, L, R>> && weakly_subtractable<std::invoke_result_t<std::minus<>&, L, R>, std::invoke_result_t<std::minus<>&, L, R>>; template<class L, class R = L> concept multipliable = weakly_multipliable<L, R> && weakly_multipliable<std::invoke_result_t<std::multiplies<>&, L, R>, R> && weakly_multipliable<L, std::invoke_result_t<std::multiplies<>&, L, R>> && weakly_multipliable<std::invoke_result_t<std::multiplies<>&, L, R>, std::invoke_result_t<std::multiplies<>&, L, R>>; template<class L, class R = L> concept divisable = weakly_divisable<L, R> && weakly_divisable<std::invoke_result_t<std::divides<>&, L, R>, R> && weakly_divisable<L, std::invoke_result_t<std::divides<>&, L, R>> && weakly_divisable<std::invoke_result_t<std::divides<>&, L, R>, std::invoke_result_t<std::divides<>&, L, R>>; template<class L, class R = L> concept remainder_calculable = weakly_remainder_calculable<L, R> && weakly_remainder_calculable<std::invoke_result_t<std::modulus<>&, L, R>, R> && weakly_remainder_calculable<L, std::invoke_result_t<std::modulus<>&, L, R>> && weakly_remainder_calculable<std::invoke_result_t<std::modulus<>&, L, R>, std::invoke_result_t<std::modulus<>&, L, R>>; template<class L, class R = L> concept addition_assignable = weakly_addition_assignable<L, R> && weakly_addition_assignable<std::decay_t<std::invoke_result_t<std::plus<>&, L, R>>, R> && weakly_addition_assignable<L, std::invoke_result_t<std::plus<>&, L, R>> && weakly_addition_assignable<std::decay_t<std::invoke_result_t<std::plus<>&, L, R>>, std::invoke_result_t<std::plus<>&, L, R>>; template<class L, class R = L> concept subtraction_assignable = weakly_subtraction_assignable<L, R> && weakly_subtraction_assignable<std::decay_t<std::invoke_result_t<std::minus<>&, L, R>>, R> && weakly_subtraction_assignable<L, std::invoke_result_t<std::minus<>&, L, R>> && weakly_subtraction_assignable<std::decay_t<std::invoke_result_t<std::minus<>&, L, R>>, std::invoke_result_t<std::minus<>&, L, R>>; template<class L, class R = L> concept multipliation_assignalbe = weakly_multipliation_assignalbe<L, R> && weakly_multipliation_assignalbe<std::decay_t<std::invoke_result_t<std::multiplies<>&, L, R>>, R> && weakly_multipliation_assignalbe<L, std::invoke_result_t<std::multiplies<>&, L, R>> && weakly_multipliation_assignalbe<std::decay_t<std::invoke_result_t<std::multiplies<>&, L, R>>, std::invoke_result_t<std::multiplies<>&, L, R>>; template<class L, class R = L> concept division_assignable = weakly_division_assignable<L, R> && weakly_division_assignable<std::decay_t<std::invoke_result_t<std::divides<>&, L, R>>, R> && weakly_division_assignable<L, std::invoke_result_t<std::divides<>&, L, R>> && weakly_division_assignable<std::decay_t<std::invoke_result_t<std::divides<>&, L, R>>, std::invoke_result_t<std::divides<>&, L, R>>; template<class L, class R = L> concept remainder_assignable = weakly_remainder_assignable<L, R> && weakly_remainder_assignable<std::decay_t<std::invoke_result_t<std::modulus<>&, L, R>>, R> && weakly_remainder_assignable<L, std::invoke_result_t<std::modulus<>&, L, R>> && weakly_remainder_assignable<std::decay_t<std::invoke_result_t<std::modulus<>&, L, R>>, std::invoke_result_t<std::modulus<>&, L, R>>; template<class T> concept weakly_incrementable = std::movable<T> && requires (T v) { { ++v } -> std::same_as<T&>; v++; }; template<class T> concept weakly_decrementable = std::movable<T> && requires (T v) { { --v } -> std::same_as<T&>; v--; }; template<class T> concept incrementable = std::regular<T> && weakly_incrementable<T> && requires (T v) { { v++ } -> std::same_as<T>; }; template<class T> concept decrementable = std::regular<T> && weakly_decrementable<T> && requires (T v) { { v-- } -> std::same_as<T>; }; template<class L, class R = L> concept weakly_arithmetic_operable = weakly_addable<L, R> && weakly_subtractable<L, R> && weakly_multipliable<L, R> && weakly_divisable<L, R>; template<class L, class R = L> concept weakly_arithmetic_operation_assignable = weakly_addition_assignable<L, R> && weakly_subtraction_assignable<L, R> && weakly_multipliation_assignalbe<L, R> && weakly_division_assignable<L, R>; template<class L, class R = L> concept arithmetic_operable = weakly_arithmetic_operable<L, R> && addable<L, R> && subtractable<L, R> && multipliable<L, R> && divisable<L, R>; template<class L, class R = L> concept arithmetic_operation_assignable = weakly_arithmetic_operation_assignable<L, R> && addition_assignable<L, R> && subtraction_assignable<L, R> && multipliation_assignalbe<L, R> && division_assignable<L, R>; template<class T> concept unary_addable = requires (T v) { { +v } -> std::same_as<T>; }; template<class T> concept unary_subtractable = requires (T v) { { -v } -> std::same_as<T>; }; template<class T> concept numeric = std::regular<T> && arithmetic_operable<T> && arithmetic_operation_assignable<T> && weakly_incrementable<T> && unary_addable<T> && unary_subtractable<T>; } }
/* [end]: internal/concepts.hpp*/
/* [begin]: internal/resolving_rank.hpp */
namespace uni { namespace internal { template<int P> struct resolving_rank : resolving_rank<P-1> {}; template<> struct resolving_rank<0> {}; } }
/* [end]: internal/resolving_rank.hpp*/
/* [begin]: internal/exception.hpp */
namespace uni { namespace internal { template<class... T> inline constexpr bool EXCEPTION = false; template<const int T> inline constexpr bool EXCEPTION_INT = false; } }
/* [end]: internal/exception.hpp*/
#include <typeinfo>
#include <cxxabi.h>
namespace debugger { template<class T> auto _debug (T&& val) -> decltype(val._debug()) { return val._debug(); } std::ostream *cdebug = &std::clog; const std::string COLOR_INIT = "\033[m"; const std::string COLOR_STRING = "\033[33m"; const std::string COLOR_TYPE = "\033[34m"; const std::string COLOR_NUMERIC = "\033[36m"; const std::string COLOR_LITERAL_OPERATOR = "\033[31m"; using Brackets = std::pair<std::string, std::string>; template<class T> std::string dump(T&&); template<class T> const std::string get_type_name(T&& val) { const char* const name = typeid(std::forward<T>(val)).name(); int status = -4; char* const demangled_name = abi::__cxa_demangle(name, NULL, NULL, &status); std::string res{name}; if (status == 0) { res = std::string(demangled_name); free(demangled_name); } return COLOR_TYPE + res + COLOR_INIT; } struct debug_t : std::string { using std::string::string; debug_t(const std::string& str) { this->assign(str); } }; template<size_t N, class T> void dump_tuple_impl([[maybe_unused]] T&& val, std::stringstream &res) { if constexpr(N < std::tuple_size_v<std::decay_t<T>>) { res << dump(std::get<N>(val)); if constexpr(N < std::tuple_size_v<std::decay_t<T>> - 1) res << ", "; dump_tuple_impl<N + 1>(std::forward<T>(val), res); } } template<std::ranges::input_range R> std::string dump_range_impl(R&& range, const Brackets& brcs = { "[", "]" }, const std::string& spl = ", ") { std::stringstream res; res << brcs.first << " "; auto itr = std::ranges::begin(range); auto end = std::ranges::end(std::forward<R>(range)); while(itr != end) { if(std::ranges::next(itr) == end) res << dump(*itr) << " "; else res << dump(*itr) << spl; ++itr; } res << brcs.second ; return res.str(); } std::string dump_debug_t(debug_t info) { return info; } struct dump_primitive_like { std::string operator()(std::nullptr_t) const { return COLOR_INIT; } template<uni::internal::pointer T> std::string operator()(const T ptr) const { return dump(*ptr); } template<class T> requires uni::internal::derived_from_template<std::decay_t<T>, std::basic_string> std::string operator()(T&& val) const { std::stringstream res; res << COLOR_STRING << "`" << val << "`" << COLOR_INIT; return res.str(); } std::string operator()(const char val) const { std::stringstream res; res << COLOR_STRING << "\'" << val << "\'" << COLOR_INIT; return res.str(); } std::string operator()(const char val[]) const { std::stringstream res; res << COLOR_STRING << "\"" << val << "\"" << COLOR_INIT; return res.str(); } std::string operator()(const unsigned char val) const { std::stringstream res; res << COLOR_NUMERIC << static_cast<int>(val) << COLOR_INIT; return res.str(); } std::string operator()(const bool val) const { std::stringstream res; res << COLOR_NUMERIC << (val ? "true" : "false" ) << COLOR_INIT; return res.str(); } template<uni::internal::arithmetic T> std::string operator()(const T val) const { std::stringstream res; res << COLOR_NUMERIC << std::setprecision(std::numeric_limits<T>::digits10); res << val << COLOR_LITERAL_OPERATOR << uni::internal::literal_operator_v<T>; res << COLOR_INIT; return res.str(); }; template<class T> requires uni::internal::derived_from_template<std::decay_t<T>, std::optional> std::string operator()(T&& val) const { if(val.has_value()) return dump(*val); return COLOR_TYPE + "invalid" + COLOR_INIT; } }; struct dump_bitset { template<std::size_t N> std::string operator()(const std::bitset<N>& val) const { std::stringstream res; res << COLOR_NUMERIC << val.to_string() << COLOR_INIT; return res.str(); } }; struct dump_has_val { template<class T> requires requires (T val) { val.val(); } std::string operator()(T&& val) const { return dump(val.val()); } }; struct dump_iterator { template<std::input_or_output_iterator I> std::string operator()(I&& itr) const { return COLOR_TYPE + "<iterator> " + COLOR_INIT+ dump(*itr); } }; struct dump_wrapper { template<class T> requires uni::internal::derived_from_template<std::decay_t<T>, std::map> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::decay_t<T>, std::multimap> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::decay_t<T>, std::unordered_map> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::decay_t<T>, std::unordered_multimap> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::decay_t<T>, std::set> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::decay_t<T>, std::multiset> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::decay_t<T>, std::unordered_set> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::decay_t<T>, std::unordered_multiset> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires uni::internal::derived_from_template<std::decay_t<T>, std::vector> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("[", "]")); } template<class T> requires uni::internal::derived_from_template<std::decay_t<T>, std::deque> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("[", "]")); } template<uni::internal::derived_from_template<std::queue> T> std::string operator()(T val) const { std::vector<typename T::value_type> vec; while(!val.empty()) vec.emplace_back(val.front()), val.pop(); return dump_range_impl(vec, Brackets("<", ">")); } template<uni::internal::derived_from_template<std::stack> T> std::string operator()(T val) const { std::vector<typename T::value_type> vec; while(!val.empty()) vec.emplace_back(val.top()), val.pop(); std::ranges::reverse(vec); return dump_range_impl(vec, Brackets("<", ">")); } template<uni::internal::derived_from_template<std::priority_queue> T> std::string operator()(T val) const { std::vector<typename T::value_type> vec; while(!val.empty()) vec.emplace_back(val.top()), val.pop(); return dump_range_impl(vec, Brackets("<", ">")); } template<class T> requires uni::internal::derived_from_template<std::decay_t<T>, std::pair> std::string operator()(T&& val) const { std::stringstream res; res << "( " << dump(val.first) << ", " << dump(val.second) << " )"; return res.str(); } template<class T> requires uni::internal::derived_from_template<std::decay_t<T>, std::tuple> std::string operator()(T&& val) const { std::stringstream res; res << "( "; dump_tuple_impl<0>(val, res); res << " )"; return res.str(); } }; struct dump_range { template<std::ranges::input_range T> std::string operator()(T&& val) const { return dump_range_impl(val); } }; struct dump_loggable { template<uni::internal::loggable T> std::string operator()(T&& val) const { auto res = _debug(val); if constexpr(std::same_as<decltype(res), debug_t>) { return res; } else { return dump(res); } } }; template<class T> std::string dump(T&& val) { if constexpr(std::same_as<std::remove_cvref_t<T>, debug_t>) { return dump_debug_t(std::forward<T>(val)); } if constexpr(std::invocable<dump_primitive_like, T>) { return dump_primitive_like{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_loggable, T>) { return dump_loggable{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_has_val, T>) { return dump_has_val{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_bitset, T>) { return dump_bitset{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_iterator, T>) { return dump_iterator{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_wrapper, T>) { return dump_wrapper{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_range, T>) {; return dump_range{}(std::forward<T>(val)); } return "== dump error =="; } template<class T> void debug(T&& val, const std::string& endl) { *cdebug << dump(val) << endl << std::flush; } constexpr std::string_view WHITESPACES = " \n\r\t\f\v"; std::string ltrim(const std::string &s) { size_t start = s.find_first_not_of(WHITESPACES); return (start == std::string::npos) ? "" : s.substr(start); } std::string rtrim(const std::string &s) { size_t end = s.find_last_not_of(WHITESPACES); return (end == std::string::npos) ? "" : s.substr(0, end + 1); } std::string trim(const std::string &s) { return rtrim(ltrim(s)); } std::vector<std::string> split(const std::string& str) { static constexpr char SEPARATOR = ','; static constexpr char ESCAPE = '\\'; static constexpr std::string_view QUOTATIONS = "\"\'"; static constexpr std::string_view PARENTHESES = "()[]{}<>"; static constexpr auto PARENTHESES_KINDS = std::ranges::size(PARENTHESES); static_assert(PARENTHESES_KINDS % 2 == 0); std::vector<std::string> res = { "" }; bool quoted = false; std::array<int,(PARENTHESES_KINDS / 2)> enclosed = { 0 }; for(auto itr = std::ranges::begin(str); itr != std::ranges::end(str); ++itr) { if(std::ranges::find(QUOTATIONS, *itr) != std::ranges::end(QUOTATIONS)) { if(itr == std::ranges::begin(str) or *std::ranges::prev(itr) != ESCAPE) { quoted ^= true; } } if(const auto found = std::ranges::find(PARENTHESES, *itr); found != std::ranges::end(PARENTHESES)) { if(not quoted) { auto& target = enclosed[std::ranges::distance(std::begin(PARENTHESES), found) / 2]; target = std::max(0, target - static_cast<int>((std::ranges::distance(std::begin(PARENTHESES), found) % 2) * 2) + 1); } } if( not quoted and static_cast<std::size_t>(std::ranges::count(enclosed, 0)) == std::ranges::size(enclosed) and *itr == SEPARATOR ) { res.push_back(""); } else { res.back() += *itr; } } for(auto&& v : res) v = trim(v); return res; } template<class Arg> void raw(std::nullptr_t, Arg&& arg) { *cdebug << std::forward<Arg>(arg) << std::flush; } template<class Arg> void raw(Arg&& arg) { *cdebug << dump(std::forward<Arg>(arg)) << std::flush; } void debug(std::vector<std::string>, size_t, int) { debug(nullptr, COLOR_INIT + "\n"); } std::map<int, int> count; template<typename Head, typename... Tail> void debug(std::vector<std::string> args, size_t idx, int line, Head&& H, Tail&&... T) { if(idx == 0) { debug(nullptr, "\033[3;35m#" + std::to_string(line) + " (" + std::to_string(count[line]) + ")" + COLOR_INIT); count[line]++; } debug(nullptr, "\n - "); const std::string content = dump(H); const std::string type_name = get_type_name(std::forward<Head>(H)); debug(nullptr, "\033[32m" + args[idx] + COLOR_INIT + " : "); debug(nullptr, content); if(type_name.size() + content.size() >= 300) debug(nullptr, "\n "); debug(nullptr, " " + type_name); debug(args, idx + 1, 0, std::forward<Tail>(T)...); } }
/* [end]: debugger/debug.hpp*/
#ifdef LOCAL_JUDGE
#define DEBUGGER_ENABLED 1
#define debug(...) debugger::debug(debugger::split(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#define debug_(...) do { debugger::raw(nullptr, "\033[3;35m#" + std::to_string(__LINE__) + "\033[m "); debugger::raw(__VA_ARGS__); debugger::raw(nullptr, "\033[m\n"); } while(0);
#define DEBUG if constexpr(true)
#else
#define debug(...) ({ ; })
#define debug_(...) ({ ; })
#define DEBUG if constexpr(false)
#endif
/* [end]: template/debug.hpp*/

void solve();

signed main() {
    debug(__cplusplus);
    int $ = 1;
    // std::cin >> $;
    for(int _ = 0; _ < $; ++_) {
        debug_("Case: #" + std::to_string(_));
        solve();
    }
    return 0;
}

/* [begin]: numeric/boundary_seeker.hpp */
/* [begin]: internal/types.hpp */
namespace uni { namespace internal { using size_t = std::int64_t; using int128_t = __int128_t; using uint128_t = __uint128_t; } }
/* [end]: internal/types.hpp*/
/* [begin]: numeric/limits.hpp */
namespace uni { template<class T> struct numeric_limits : std::numeric_limits<T> { static constexpr long double FLOAT_EPSILON = 1E-14; static constexpr T arithmetic_infinity() noexcept(NO_EXCEPT) { return std::numeric_limits<T>::max() / 2 - 1; } static constexpr T arithmetic_negative_infinity() noexcept(NO_EXCEPT) { return std::numeric_limits<T>::lowest() / 2 + 1; } static constexpr T arithmetic_epsilon() noexcept(NO_EXCEPT) { if constexpr(std::is_floating_point_v<T>) { return numeric_limits::FLOAT_EPSILON; } else { return 0; } } }; constexpr i32 INF32 = numeric_limits<i32>::arithmetic_infinity(); constexpr i64 INF64 = numeric_limits<i64>::arithmetic_infinity(); template<class T> constexpr T INF = numeric_limits<T>::arithmetic_infinity(); template<class T> constexpr T EPSILON = numeric_limits<T>::arithmetic_epsilon(); }
/* [end]: numeric/limits.hpp*/
namespace uni { namespace internal { namespace boundary_seeker_impl { template<class T> struct integal { protected: std::function<bool(T)> _validate; public: integal(std::function<bool(T)> validate) noexcept(NO_EXCEPT) : _validate(validate) {} template<const bool REVERSE = false> T bound(const T _ok, const T _ng) const noexcept(NO_EXCEPT) { T ok = _ok, ng = _ng; if constexpr(REVERSE) std::swap(ng, ok); while(std::abs(ok-ng) > 1) { T mid = ng + (ok - ng) / 2; (this->_validate(mid) ? ok : ng) = mid; } return ok; } template<const bool INVERT = false> T bound(const T ok) const noexcept(NO_EXCEPT) { T ng = INVERT ? -1 : 1; while(this->_validate(ok + ng)) ng += ng; return this->bound(ok, ok + ng); } template<const bool REVERSE = false> T bound() const noexcept(NO_EXCEPT) { return this->bound<REVERSE>( REVERSE ? numeric_limits<T>::arithmetic_infinity(): numeric_limits<T>::arithmetic_negative_infinity() ); } template<const bool REVERSE = false> T bound_or(const T ok, const T ng, const T proxy) const noexcept(NO_EXCEPT) { const T res = this->bound<REVERSE>(ok, ng); return this->_validate(res) ? res : proxy; } template<const bool INVERT = false> T bound_or(const T ok, const T proxy) const noexcept(NO_EXCEPT) { const T res = this->bound<INVERT>(ok); return this->_validate(res) ? res : proxy; } template<const bool REVERSE = false> T bound_or(const T proxy) const noexcept(NO_EXCEPT) { const T res = this->bound<REVERSE>(); return this->_validate(res) ? res : proxy; } }; template<class T> struct floating_point { protected: std::function<bool(T)> _validate; public: floating_point(std::function<bool(T)> validate) noexcept(NO_EXCEPT) : _validate(validate) {} template<const bool REVERSE = false, const internal::size_t ITERATIONS = 200> T bound(const T _ok, const T _ng) const noexcept(NO_EXCEPT) { T ok = _ok, ng = _ng; if constexpr(REVERSE) std::swap(ng, ok); REP(ITERATIONS) { T mid = ng + (ok - ng) / 2; (this->_validate(mid) ? ok : ng) = mid; } return ok; } template<const bool REVERSE = false, const internal::size_t ITERATIONS = 200> T bound(const T ok) const noexcept(NO_EXCEPT) { T ng = ok + REVERSE ? -1 : 1; while(this->_validate(ng)) ng += REVERSE ? -ng : ng; return this->bound<false,ITERATIONS>(ok, ng); } template<const bool REVERSE = false, const internal::size_t ITERATIONS = 200> T bound() const noexcept(NO_EXCEPT) { return this->bound<REVERSE,ITERATIONS>( REVERSE ? numeric_limits<T>::arithmetic_infinity() : numeric_limits<T>::arithmetic_negative_infinity() ); } template<const bool REVERSE = false, const internal::size_t ITERATIONS = 200> T bound_or(const T ok, const T ng, const T proxy) const noexcept(NO_EXCEPT) { const T res = this->bound<REVERSE,ITERATIONS>(ok, ng); return this->_validate(res) ? res : proxy; } template<const bool REVERSE = false, const internal::size_t ITERATIONS = 200> T bound_or(const T ok, const T proxy) const noexcept(NO_EXCEPT) { const T res = this->bound<REVERSE,ITERATIONS>(ok); return this->_validate(res) ? res : proxy; } template<const bool REVERSE = false, const internal::size_t ITERATIONS = 200> T bound_or(const T proxy) const noexcept(NO_EXCEPT) { const T res = this->bound<REVERSE,ITERATIONS>(); return this->_validate(res) ? res : proxy; } }; template<class, bool> struct seeker {}; template<class T> struct seeker<T,true> : integal<T> { using integal<T>::integal; }; template<class T> struct seeker<T,false> : floating_point<T> { using floating_point<T>::floating_point; }; } } template<class T> using boundary_seeker = internal::boundary_seeker_impl::seeker<T,std::is_integral_v<T>>; }
/* [end]: numeric/boundary_seeker.hpp*/
#include <atcoder/lazysegtree>

uni::i64 e() { return 0; }
uni::i64 op(uni::i64 s, uni::i64 t) { return s + t; }

uni::i64 INF64 = std::numeric_limits<uni::i64>::max() / 2 - 1;

void solve() {
    int n; std::cin >> n;
    std::vector<uni::i64> x(n); for(auto& v : x) std::cin >> v;

    std::vector<uni::i64> diff(n);
    REP(i, 1, n) diff[i] = diff[i - 1] + (x[i - 1] != x[i]);

    int q; std::cin >> q;
    REP(q) {
        int l, r; uni::i64 s; std::cin >> l >> r >> s; --l;
        debug(l, r, s);

        auto a = x | std::views::take(r) | std::views::drop(l);
        int m = r - l;

        if(1L << std::min(m - 1, 62) <= s) {
            std::cout << -1 << "\n";
            continue;
        }

        if(m >= 88) {
            int d = diff[r - 1] - diff[l];
            uni::i64 v = 1L << std::min(d, 62);
            std::cout << int(v <= s) << "\n";
        }

        auto f = [&](uni::i64 k) -> uni::i128 {
            if(k == 0) return 0;

            std::vector<uni::i64> max_right(m);
            {
                int j = 0;

                std::unordered_map<uni::i64, int> cnt;
                REP(i, m) {
                    while(j < m) {
                        ++cnt[a[j++]];
                        if(std::ranges::ssize(cnt) > k) {
                            --j;
                            if(--cnt[a[j]] == 0) cnt.erase(a[j]);
                            break;
                        }
                    }
                    max_right[i] = j;
                    if(--cnt[a[i]] == 0) cnt.erase(a[i]);
                }
                debug(max_right, cnt);
            }

            std::vector<uni::i128> dp(m + 1, 0), sum(m + 2, 0);

            dp[0] = 1;
            FOR(i, m) {
                dp[i] += sum[i];
                if(dp[i] > s) return uni::INF32;
                if(i == m) break;

                sum[i + 1] += dp[i];
                sum[max_right[i] + 1] -= dp[i];
                sum[i + 1] += sum[i];
            }

            return dp[m];
        };

        for(uni::i64 k = 1; ; ++k) {
            if(k > m) {
                std::cout << -1 << "\n";
                break;
            }
            uni::i128 v = f(k);
            if(v > s) {
                std::cout << k - 1 << "\n";
                break;
            }
        }
    }
}