data_structure/internal/tree_dumper.hpp

View this file on GitHub
Last update: 2025-06-27 23:58:00+09:00
Include: #include "data_structure/internal/tree_dumper.hpp"

Depends on

Required by

Verified with

Code

#pragma once


#include <string>


#include "snippet/aliases.hpp"
#include "debugger/debug.hpp"


namespace uni {

namespace internal {


template<class Derived, class Core, bool LEAF_ONLY>
struct dumpable_tree {
  private:
    using node_handler = Core::node_handler;
    using node_pointer = Core::node_pointer;

    using size_type = Core::size_type;

    inline auto _push(const node_pointer& tree) {
        return static_cast<Derived*>(this)->_impl.push(tree);
        // return static_cast<Derived*>(this)->push(tree);
    }

  public:
    debugger::debug_t dump_rich(node_pointer tree, const std::string prefix, const int dir, size_type& index)
        requires (!LEAF_ONLY)
    {
        if(!tree || tree == node_handler::nil) return prefix + "\n";

        this->_push(tree);

        // debug(tree->priority >= tree->left->priority, tree->priority, tree->left->priority);
        // debug(tree->priority >= tree->right->priority, tree->priority, tree->right->priority);
        assert(tree->priority >= tree->left->priority);
        assert(tree->priority >= tree->right->priority);

        const auto left = this->dump_rich(tree->left, prefix + (dir == 1 ? "| " : "  "), -1, index);
        const auto here =
            prefix + "--+ [" +
            debugger::dump(index) + ", " + debugger::dump(index + tree->length) + ") : " +
            "<" + debugger::dump(tree->priority) + "> " +
            debugger::dump(tree->data) + " [" + debugger::dump(tree->length) + "]\n";
        index += tree->length;

        const auto right = this->dump_rich(tree->right, prefix + (dir == -1 ? "| " : "  "), 1, index);

        return left + here + right;
    }

    debugger::debug_t dump_rich(node_pointer tree, const std::string prefix, const int dir, size_type& index)
        requires
            (
                LEAF_ONLY &&
                requires {
                    typename Core::node_colors;
                }
            )
    {
        if(!tree || tree == node_handler::nil) return prefix + "\n";

        this->_push(tree);

        const auto left = this->dump_rich(tree->left, prefix + (dir == 1 ? "| " : "  "), -1, index);
        const auto right = this->dump_rich(tree->right, prefix + (dir == -1 ? "| " : "  "), 1, index);


        const auto color = tree->color == Core::node_colors::BLACK ? "<->" : "<+>";

        const auto here = [&]() -> std::string {
            if(tree->is_leaf()) {
                index += tree->size;

                return
                    prefix + "--+ [" +
                    debugger::dump(index - tree->size) + ", " + debugger::dump(index) + ") : " +
                    debugger::COLOR_STRING + color + debugger::COLOR_INIT + " " +
                    debugger::dump(tree->data) + " [" + debugger::dump(tree->size) + "]\n";
            }
            return "";
        }();

        return left + here + right;
    }


    inline debugger::debug_t dump_rich(const node_pointer& tree, const std::string prefix = "   ", const int dir = 0) {
        size_type index = 0;
        return this->dump_rich(tree, prefix, dir, index);
    }


    debugger::debug_t _debug(node_pointer tree)
        requires (!LEAF_ONLY)
    {
        if(!tree || tree == node_handler::nil) return "";

        this->_push(tree);

        return
            "(" +
            this->_debug(tree->left) + " " +
            debugger::dump(tree->data) + " [" +
            debugger::dump(tree->length) + "] " +
            this->_debug(tree->right) +
            ")";
    }

    debugger::debug_t _debug(node_pointer tree)
        requires LEAF_ONLY
    {
        if(!tree || tree == node_handler::nil) return "";

        this->_push(tree);

        return
            "(" +
            this->_debug(tree->left) + " " +
            (
                tree->is_leaf()
                    ?
                        debugger::dump(tree->data) + " [" +
                        debugger::dump(tree->size) + "] "
                    :
                        ""
            ) +
            this->_debug(tree->right) +
            ")";
    }
};


} // namespace internal


} // namespace uni

#line 2 "data_structure/internal/tree_dumper.hpp"


#include <string>


#line 2 "snippet/aliases.hpp"


#include <cstdint>
#include <utility>
#include <vector>
#include <queue>
#include <ranges>

#line 2 "macro/internal/compatibility.hpp"


#line 2 "adaptor/string.hpp"


#line 5 "adaptor/string.hpp"
#include <algorithm>

#line 2 "adaptor/internal/advanced_container.hpp"


#include <cassert>
#line 8 "adaptor/internal/advanced_container.hpp"


#line 2 "snippet/internal/base.hpp"


#line 5 "snippet/internal/base.hpp"


#define until(...) while(!(__VA_ARGS__))

#define CONTINUE(...) { __VA_ARGS__; continue; }
#define BREAK(...) { __VA_ARGS__; break; }

#define ALL(x) std::ranges::begin((x)),std::ranges::end((x))
#define RALL(x) std::ranges::rbegin((x)),std::ranges::rend((x))


#define $F first
#define $S second
#line 2 "snippet/iterations.hpp"

#include <type_traits>
#line 2 "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
#line 2 "macro/basic.hpp"

#define TO_STRING_AUX(x) #x
#define TO_STRING(x) TO_STRING_AUX(x)

#define CONCAT_AUX(x, y) x##y
#define CONCAT(x, y) CONCAT_AUX(x, y)

#define UNPAREN_AUX(...) __VA_ARGS__
#define UNPAREN(...) __VA_ARGS__
#line 6 "snippet/iterations.hpp"


#define LOOP(n) REPI(CONCAT(_$, __COUNTER__), n)

#define REPI(i,n) for(std::remove_cvref_t<decltype(n)> i=0, CONCAT(i, $)=(n); i<CONCAT(i, $); ++i)
#define REPF(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); ++i)
#define REPIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); i+=(s))

#define REPR(i,n) for(auto i=(n); --i>=0;)
#define REPB(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); --i>=CONCAT(i, $);)
#define REPRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l)-1)/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); (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, CONCAT(i, $)=static_cast<int>(n); i<=CONCAT(i, $); ++i)
#define FORI(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); ++i)
#define FORIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); i+=(s))

#define FORRO(i,n) for(auto i=(n); i>=0; --i)
#define FORR(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); i>=CONCAT(i, $); --i)
#define FORRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l))/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); 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__)
#line 12 "adaptor/internal/advanced_container.hpp"

#line 2 "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 // LOCAL_JUDGE


#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
#line 2 "internal/types.hpp"

#line 4 "internal/types.hpp"

namespace uni {

namespace internal {


using size_t = std::int64_t;

using int128_t = __int128_t;
using uint128_t = __uint128_t;


} // namesapce internal

} // namespace uni
#line 2 "internal/concepts.hpp"


#line 5 "internal/concepts.hpp"
#include <concepts>
#line 7 "internal/concepts.hpp"
#include <limits>
#include <functional>


namespace uni {

namespace internal {


template<class R, class T>
concept convertibel_range = std::convertible_to<std::ranges::range_value_t<R>, T>;


template<class T, class V>
concept item_or_convertible_range = std::convertible_to<T, V> || convertibel_range<T, V>;


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 floating_point = std::is_floating_point_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_bitand_calcurable = requires (L lhs, R rhs) { lhs & rhs; };

template<class L, class R = L>
concept weakly_bitor_calcurable = requires (L lhs, R rhs) { lhs | rhs; };

template<class L, class R = L>
concept weakly_bitxor_calcurable = requires (L lhs, R rhs) { lhs ^ rhs; };

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_bitand_assignable = requires (L lhs, R rhs) { lhs += rhs; };

template<class L, class R = L>
concept weakly_bitor_assignable = requires (L lhs, R rhs) { lhs |= rhs; };

template<class L, class R = L>
concept weakly_bitxor_assignable = 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 bitand_calculable =
    weakly_bitand_calcurable<L, R> &&
    weakly_bitand_calcurable<std::invoke_result_t<std::bit_and<>&, L, R>, R> &&
    weakly_bitand_calcurable<L, std::invoke_result_t<std::bit_and<>&, L, R>> &&
    weakly_bitand_calcurable<std::invoke_result_t<std::bit_and<>&, L, R>, std::invoke_result_t<std::bit_and<>&, L, R>>;

template<class L, class R = L>
concept bitor_calculable =
    weakly_bitor_calcurable<L, R> &&
    weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, R> &&
    weakly_bitor_calcurable<L, std::invoke_result_t<std::bit_or<>&, L, R>> &&
    weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, std::invoke_result_t<std::bit_or<>&, L, R>>;

template<class L, class R = L>
concept bitxor_calculable =
    weakly_bitxor_calcurable<L, R> &&
    weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, R> &&
    weakly_bitxor_calcurable<L, std::invoke_result_t<std::bit_xor<>&, L, R>> &&
    weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, std::invoke_result_t<std::bit_xor<>&, L, R>>;

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 bitand_assignable =
    weakly_bitand_assignable<L, R> &&
    weakly_bitand_assignable<std::invoke_result_t<std::bit_and<>&, L, R>, R> &&
    weakly_bitand_assignable<L, std::invoke_result_t<std::bit_and<>&, L, R>> &&
    weakly_bitand_assignable<std::invoke_result_t<std::bit_and<>&, L, R>, std::invoke_result_t<std::bit_and<>&, L, R>>;

template<class L, class R = L>
concept bitor_assignable =
    weakly_bitor_calcurable<L, R> &&
    weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, R> &&
    weakly_bitor_calcurable<L, std::invoke_result_t<std::bit_or<>&, L, R>> &&
    weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, std::invoke_result_t<std::bit_or<>&, L, R>>;

template<class L, class R = L>
concept bitxor_assignable =
    weakly_bitxor_calcurable<L, R> &&
    weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, R> &&
    weakly_bitxor_calcurable<L, std::invoke_result_t<std::bit_xor<>&, L, R>> &&
    weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, std::invoke_result_t<std::bit_xor<>&, L, R>>;

template<class L, class R = L>
concept addition_assignable =
    weakly_addition_assignable<L, R> &&
    weakly_addition_assignable<std::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_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>;


} // namespace internal

} // namespace uni
#line 16 "adaptor/internal/advanced_container.hpp"

#line 2 "numeric/internal/mod.hpp"


#line 6 "numeric/internal/mod.hpp"


namespace uni {


template<class T, class R>
    requires
        internal::remainder_calculable<T, R> &&
        internal::subtractable<T, R> &&
        internal::unary_subtractable<T>
inline T mod(T x, const R& r) noexcept(NO_EXCEPT) {
    if(x >= 0) return x % r;
    x = -x % r;
    if(x != 0) x = r - x;
    return x;
}


} // namespace uni
#line 2 "iterable/internal/operation_base.hpp"


#line 5 "iterable/internal/operation_base.hpp"
#include <iterator>
#include <sstream>
#include <numeric>

#line 2 "internal/exception.hpp"


namespace uni {

namespace internal {


template<class... T> inline constexpr bool EXCEPTION_ON_TYPE = false;
template<auto T> inline constexpr bool EXCEPTION_ON_VALUE = false;


} // namespace internal

} // namespace uni
#line 11 "iterable/internal/operation_base.hpp"


namespace uni {


template<std::input_iterator I, std::sentinel_for<I> S>
std::string join(I first, S last, const char* sep = "") noexcept(NO_EXCEPT) {
    if(first == last) return "";
    std::ostringstream res;
    while(true) {
        res << *first;
        std::ranges::advance(first, 1);
        if(first == last) break;
        res << sep;
    }
    return res.str();
}


template<std::ranges::input_range R>
std::string join(R&& range, const char* sep = "") noexcept(NO_EXCEPT) {
    return join(ALL(range), sep);
}


template<class I, class T = std::iter_value_t<I>>
    requires std::sentinel_for<I, I>
T sum(I first, I last, const T& base = T()) noexcept(NO_EXCEPT) {
    return std::accumulate(first, last, base);
}

template<std::ranges::input_range R, class T = std::ranges::range_value_t<R>>
auto sum(R&& range, T base = T()) noexcept(NO_EXCEPT) {
    auto&& r = range | std::views::common;
    return sum(ALL(r), base);
}


} // namesapce uni
#line 19 "adaptor/internal/advanced_container.hpp"


#define UNI_ADVANCED_CONTAINER_OPERATOR(op_assign, op, concepts) \
    auto& operator op_assign(const value_type& v) noexcept(NO_EXCEPT) \
        requires concepts<value_type> \
    { \
        if constexpr(concepts<Base, value_type>) { \
            this->Base::operator op_assign(v); \
        } \
        else { \
            REP(itr, ALL(*this)) *itr op_assign v; \
        } \
        return *this; \
    } \
    \
    auto& operator op_assign(const advanced_container& rhs) noexcept(NO_EXCEPT) \
        requires concepts<value_type> \
    { \
        if constexpr(concepts<Base>) { \
            this->Base::operator op_assign(*rhs._base()); \
        } \
        else { \
            auto itr = std::ranges::begin(*this), rhs_itr = std::ranges::begin(rhs); \
            auto end = std::ranges::end(*this); \
            for(; itr != end; ++itr, ++rhs_itr) { \
                *itr op_assign *rhs_itr; \
            } \
        } \
        return *this; \
    } \
    \
    template<class T = value_type> \
        requires \
            concepts<value_type> && \
            (std::convertible_to<T, value_type> || std::same_as<T, advanced_container>) \
    friend auto operator op(advanced_container lhs, const T& rhs) noexcept(NO_EXCEPT) { \
        return lhs op_assign rhs; \
    } \
    \
    template<class T = value_type> \
        requires \
            concepts<value_type> && std::convertible_to<T, value_type> \
    friend auto operator op(const T& lhs, advanced_container rhs) noexcept(NO_EXCEPT) { \
        return advanced_container(rhs.size(), lhs) op_assign rhs; \
    }


namespace uni {

namespace internal {


template<class Base>
struct advanced_container : Base {
  private:
    inline Base* _base() noexcept(NO_EXCEPT) {
        return static_cast<Base*>(this);
    }
    inline const Base* _base() const noexcept(NO_EXCEPT) {
        return static_cast<const Base*>(this);
    }

  public:
    using Base::Base;

    advanced_container(const Base& base) : Base(base) {}

    using size_type = decltype(std::ranges::size(std::declval<Base>()));
    using value_type = Base::value_type;

    inline auto ssize() const noexcept(NO_EXCEPT) { return std::ranges::ssize(*this->_base()); }


    inline const auto& operator[](internal::size_t p) const noexcept(NO_EXCEPT) {
        p = p < 0 ? p + this->size() : p;
        assert(0 <= p && p < this->ssize());
        return this->Base::operator[](p);
    }

    inline auto& operator[](internal::size_t p) noexcept(NO_EXCEPT) {
        p = p < 0 ? p + this->size() : p;
        assert(0 <= p && p < this->ssize());
        return this->Base::operator[](p);
    }


    inline auto& fill(const value_type& v) noexcept(NO_EXCEPT) {
        std::ranges::fill(*this, v);
        return *this;
    }

    inline auto& swap(const size_type i, const size_type j) noexcept(NO_EXCEPT) {
        std::swap(this->operator[](i), this->operator[](j));
        return *this;
    }

    inline auto& sort() noexcept(NO_EXCEPT) {
        std::ranges::sort(*this);
        return *this;
    }

    template<class F>
    inline auto& sort(F&& f) noexcept(NO_EXCEPT) {
        std::ranges::sort(*this, std::forward<F>(f));
        return *this;
    }

    inline auto& stable_sort() noexcept(NO_EXCEPT) {
        std::ranges::stable_sort(*this);
        return *this;
    }

    template<class F>
    inline auto& stable_sort(F&& f) noexcept(NO_EXCEPT) {
        std::ranges::stable_sort(*this, std::forward<F>(f));
        return *this;
    }

    inline auto& reverse() noexcept(NO_EXCEPT) {
        std::ranges::reverse(*this);
        return *this;
    }

    inline auto count(const value_type& v) const noexcept(NO_EXCEPT) {
        return std::ranges::count(*this, v);
    }

    inline auto contains(const value_type& v) const noexcept(NO_EXCEPT) {
        return this->count(v) > 0;
    }

    template<class F>
    inline auto count_if(F&& f) const noexcept(NO_EXCEPT) {
        return std::ranges::count_if(*this, std::forward<F>(f));
    }

    inline auto& resize(const size_type k) noexcept(NO_EXCEPT) {
        this->Base::resize(k);
        return *this;
    }
    inline auto& resize(const size_type k, const value_type& v) noexcept(NO_EXCEPT) {
        this->Base::resize(k, v);
        return *this;
    }

    template<class F>
    inline auto& shuffle(F&& f) noexcept(NO_EXCEPT) {
        std::ranges::shuffle(*this, std::forward<F>(f));
        return *this;
    }

    inline auto& unique() noexcept(NO_EXCEPT) {
        const auto rest = std::ranges::unique(*this);
        this->erase(ALL(rest));
        return *this;
    }

    template<class T>
    inline auto binary_search(T&& v) const noexcept(NO_EXCEPT) {
        return std::ranges::binary_search(*this, std::forward<T>(v));
    }

    template<class T>
    inline auto lower_bound(T&& v) const noexcept(NO_EXCEPT) {
        return std::ranges::lower_bound(*this, std::forward<T>(v));
    }

    template<class T>
    inline auto upper_bound(T&& v) const noexcept(NO_EXCEPT) {
        return std::ranges::upper_bound(*this, std::forward<T>(v));
    }

    template<class T>
    inline auto find(T&& v) const noexcept(NO_EXCEPT) {
        return std::ranges::find(*this, std::forward<T>(v));
    }

    template<class T>
    inline auto index(T&& v) const noexcept(NO_EXCEPT) {
        return this->find(std::forward<T>(v)) - this->begin();
    }

    inline auto join(const char* sep = "") const noexcept(NO_EXCEPT) {
        return uni::join(*this, sep);
    }


    inline auto sum() const noexcept(NO_EXCEPT) { return uni::sum(*this); }


    inline auto max() const noexcept(NO_EXCEPT) { return std::ranges::max(*this->_base()); }
    inline auto min() const noexcept(NO_EXCEPT) { return std::ranges::min(*this); }


    inline auto begin() noexcept(NO_EXCEPT) { return std::ranges::begin(*this->_base()); }
    inline auto begin() const noexcept(NO_EXCEPT) { return std::ranges::begin(*this->_base()); }

    inline auto end() noexcept(NO_EXCEPT) { return std::ranges::end(*this->_base()); }
    inline auto end() const noexcept(NO_EXCEPT) { return std::ranges::end(*this->_base()); }


    UNI_ADVANCED_CONTAINER_OPERATOR(+=, +, internal::weakly_addition_assignable)
    UNI_ADVANCED_CONTAINER_OPERATOR(-=, -, internal::weakly_subtraction_assignable)
    UNI_ADVANCED_CONTAINER_OPERATOR(*=, *, internal::weakly_multipliation_assignalbe)
    UNI_ADVANCED_CONTAINER_OPERATOR(/=, /, internal::weakly_division_assignable)
    UNI_ADVANCED_CONTAINER_OPERATOR(%=, %, internal::weakly_remainder_assignable)
    UNI_ADVANCED_CONTAINER_OPERATOR(&=, &, internal::weakly_bitand_assignable)
    UNI_ADVANCED_CONTAINER_OPERATOR(|=, |, internal::weakly_bitor_assignable)
    UNI_ADVANCED_CONTAINER_OPERATOR(^=, ^, internal::weakly_bitxor_assignable)
};


} // namespace internal

} // namespace uni

#undef UNI_ADVANCED_CONTAINER_OPERATOR
#line 8 "adaptor/string.hpp"


namespace uni {


using string = internal::advanced_container<std::string>;


} // namespace uni


namespace std {


template<>
struct hash<uni::string> {
    inline auto operator()(const uni::string& key) const noexcept(NO_EXCEPT) {
        return std::hash<std::string>{}(static_cast<std::string>(key));
    }
};



}
#line 6 "macro/internal/compatibility.hpp"


#if __GNUG__ >= 13
#   define UNI_CONSTEXPR_STD_STRING constexpr std::string
#   define UNI_CONSTEXPR_STRING constexpr uni::string
#else
#   define UNI_CONSTEXPR_STD_STRING const std::string
#   define UNI_CONSTEXPR_STRING const uni::string
#endif
#line 11 "snippet/aliases.hpp"

#line 13 "snippet/aliases.hpp"

#line 2 "snippet/internal/types.hpp"

#line 4 "snippet/internal/types.hpp"

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;

using f128 = __float128;

#endif

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;


} // namespace uni
#line 16 "snippet/aliases.hpp"

#line 18 "snippet/aliases.hpp"


namespace uni {


constexpr char LN = '\n';
constexpr char SPC = ' ';


UNI_CONSTEXPR_STRING DIRECTIONS = "URDL";

constexpr std::pair<int,int> DIRS4[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
constexpr std::pair<int,int> DIRS4P[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }, { 0, 0 } };
constexpr std::pair<int,int> DIRS8[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } };
constexpr std::pair<int,int> DIRS8P[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 }, { 0, 0 } };


template<class T>
using spair = std::pair<T,T>;


template<class T>
using priority_queue_rev = std::priority_queue<T, std::vector<T>, std::greater<T>>;


}  // namespace uni


namespace std {

using bit_reference = std::vector<bool>::reference;

bit_reference operator |= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a | b; }
bit_reference operator &= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a & b; }

}
#line 2 "debugger/debug.hpp"


#include <iostream>
#line 7 "debugger/debug.hpp"
#include <string_view>
#line 9 "debugger/debug.hpp"
#include <array>
#line 11 "debugger/debug.hpp"
#include <cstring>
#line 13 "debugger/debug.hpp"
#include <bitset>
#include <deque>
#line 16 "debugger/debug.hpp"
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#line 22 "debugger/debug.hpp"
#include <iomanip>
#line 26 "debugger/debug.hpp"
#include <typeinfo>
#include <cxxabi.h>


#line 31 "debugger/debug.hpp"

#line 2 "numeric/int128.hpp"


#include <cctype>
#line 9 "numeric/int128.hpp"

#line 12 "numeric/int128.hpp"

#line 14 "numeric/int128.hpp"


namespace std {


template<class C, class S>
auto& 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::ranges::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>
auto& 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>
auto& 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>
auto& 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;
}


}
#line 33 "debugger/debug.hpp"

#line 2 "internal/type_traits.hpp"


#line 9 "internal/type_traits.hpp"


#line 12 "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>
using nth_type_t = std::tuple_element_t<N, std::tuple<Types...>>;


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 {  // ADL
        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 {  // ADL
        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>; };


} // namespace internal

}  // namespace uni
#line 2 "internal/resolving_rank.hpp"


namespace uni {

namespace internal {


template<int P> struct resolving_rank : resolving_rank<P-1> {};
template<> struct resolving_rank<0> {};


} // namespace internal

} // namespace uni
#line 38 "debugger/debug.hpp"


namespace debugger {


template<class T>
auto _debug (T&& val) -> decltype(val._debug()) {
    return val._debug();
}


std::ostream *cdebug = &std::clog;


#ifdef DEBUGGER_COLORED_OUTPUT

UNI_CONSTEXPR_STD_STRING COLOR_LINE = "\033[3;35m";
UNI_CONSTEXPR_STD_STRING COLOR_IDENTIFIER = "\033[32m";
UNI_CONSTEXPR_STD_STRING COLOR_INIT = "\033[m";
UNI_CONSTEXPR_STD_STRING COLOR_STRING = "\033[33m";
UNI_CONSTEXPR_STD_STRING COLOR_TYPE = "\033[34m";
UNI_CONSTEXPR_STD_STRING COLOR_NUMERIC = "\033[36m";
UNI_CONSTEXPR_STD_STRING COLOR_LITERAL_OPERATOR = "\033[31m";

#else

UNI_CONSTEXPR_STD_STRING COLOR_LINE = "";
UNI_CONSTEXPR_STD_STRING COLOR_IDENTIFIER = "";
UNI_CONSTEXPR_STD_STRING COLOR_INIT = "";
UNI_CONSTEXPR_STD_STRING COLOR_STRING = "";
UNI_CONSTEXPR_STD_STRING COLOR_TYPE = "";
UNI_CONSTEXPR_STD_STRING COLOR_NUMERIC = "";
UNI_CONSTEXPR_STD_STRING COLOR_LITERAL_OPERATOR = "";

#endif

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::remove_cvref_t<T>>) {
        res << dump(std::get<N>(val));
        if constexpr(N < std::tuple_size_v<std::remove_cvref_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::remove_cvref_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 << std::setprecision(std::numeric_limits<T>::digits10) << val;

        auto str = res.str();

        std::string dst = "";

        if constexpr(std::integral<T>) {
            while(str.length() > 3) {
                dst = ',' + str.substr(str.length() - 3, 3) + dst;
                str = str.substr(0, str.length() - 3);
            }
        }

        return COLOR_NUMERIC + str + dst + COLOR_LITERAL_OPERATOR + uni::internal::literal_operator_v<T> + COLOR_INIT;
    };

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_t<T>, std::valarray>
    std::string operator()(T&& val) const {
        return dump_range_impl(val, Brackets("[", "]"));
    }

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_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::remove_cvref_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::remove_cvref_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::remove_cvref_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 "debug_t";
        return dump_debug_t(std::forward<T>(val));
    }

    if constexpr(std::invocable<dump_primitive_like, T>) {
        // return "primitive";
        return dump_primitive_like{}(std::forward<T>(val));
    }
    if constexpr(std::invocable<dump_loggable, T>) {
        // return "loggable";
        return dump_loggable{}(std::forward<T>(val));
    }
    if constexpr(std::invocable<dump_has_val, T>) {
        // return "has val";
        return dump_has_val{}(std::forward<T>(val));
    }

    if constexpr(std::invocable<dump_bitset, T>) {
        // return "bitset";
        return dump_bitset{}(std::forward<T>(val));
    }
    if constexpr(std::invocable<dump_iterator, T>) {
        // return "iterator";
        return dump_iterator{}(std::forward<T>(val));
    }

    if constexpr(std::invocable<dump_wrapper, T>) {
        // return "wrapper";
        return dump_wrapper{}(std::forward<T>(val));
    }

    if constexpr(std::invocable<dump_range, T>) {;
        // return "range";
        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(const std::vector<std::string>, const size_t, const int, const std::string) { debug(nullptr, COLOR_INIT + "\n"); }


std::map<std::pair<std::string, int>, int> count;

template<class Head, class... Tail>
void debug(
    const std::vector<std::string> args, const size_t idx,
    const int line, const std::string path,
    Head&& H, Tail&&... T
) {
    if(idx == 0) {
        std::string file = path.substr(path.find_last_of("/") + 1);
        debug(nullptr, COLOR_LINE + file + " #" + std::to_string(line) + " (" + std::to_string(count[{ file, line }]++) + ")" + COLOR_INIT);
    }
    debug(nullptr, "\n - ");


    const std::string content = dump(H);
    const std::string type_name = get_type_name(std::forward<Head>(H));


    debug(nullptr, COLOR_IDENTIFIER + 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, path, std::forward<Tail>(T)...);
}


} // namespace debugger
#line 9 "data_structure/internal/tree_dumper.hpp"


namespace uni {

namespace internal {


template<class Derived, class Core, bool LEAF_ONLY>
struct dumpable_tree {
  private:
    using node_handler = Core::node_handler;
    using node_pointer = Core::node_pointer;

    using size_type = Core::size_type;

    inline auto _push(const node_pointer& tree) {
        return static_cast<Derived*>(this)->_impl.push(tree);
        // return static_cast<Derived*>(this)->push(tree);
    }

  public:
    debugger::debug_t dump_rich(node_pointer tree, const std::string prefix, const int dir, size_type& index)
        requires (!LEAF_ONLY)
    {
        if(!tree || tree == node_handler::nil) return prefix + "\n";

        this->_push(tree);

        // debug(tree->priority >= tree->left->priority, tree->priority, tree->left->priority);
        // debug(tree->priority >= tree->right->priority, tree->priority, tree->right->priority);
        assert(tree->priority >= tree->left->priority);
        assert(tree->priority >= tree->right->priority);

        const auto left = this->dump_rich(tree->left, prefix + (dir == 1 ? "| " : "  "), -1, index);
        const auto here =
            prefix + "--+ [" +
            debugger::dump(index) + ", " + debugger::dump(index + tree->length) + ") : " +
            "<" + debugger::dump(tree->priority) + "> " +
            debugger::dump(tree->data) + " [" + debugger::dump(tree->length) + "]\n";
        index += tree->length;

        const auto right = this->dump_rich(tree->right, prefix + (dir == -1 ? "| " : "  "), 1, index);

        return left + here + right;
    }

    debugger::debug_t dump_rich(node_pointer tree, const std::string prefix, const int dir, size_type& index)
        requires
            (
                LEAF_ONLY &&
                requires {
                    typename Core::node_colors;
                }
            )
    {
        if(!tree || tree == node_handler::nil) return prefix + "\n";

        this->_push(tree);

        const auto left = this->dump_rich(tree->left, prefix + (dir == 1 ? "| " : "  "), -1, index);
        const auto right = this->dump_rich(tree->right, prefix + (dir == -1 ? "| " : "  "), 1, index);


        const auto color = tree->color == Core::node_colors::BLACK ? "<->" : "<+>";

        const auto here = [&]() -> std::string {
            if(tree->is_leaf()) {
                index += tree->size;

                return
                    prefix + "--+ [" +
                    debugger::dump(index - tree->size) + ", " + debugger::dump(index) + ") : " +
                    debugger::COLOR_STRING + color + debugger::COLOR_INIT + " " +
                    debugger::dump(tree->data) + " [" + debugger::dump(tree->size) + "]\n";
            }
            return "";
        }();

        return left + here + right;
    }


    inline debugger::debug_t dump_rich(const node_pointer& tree, const std::string prefix = "   ", const int dir = 0) {
        size_type index = 0;
        return this->dump_rich(tree, prefix, dir, index);
    }


    debugger::debug_t _debug(node_pointer tree)
        requires (!LEAF_ONLY)
    {
        if(!tree || tree == node_handler::nil) return "";

        this->_push(tree);

        return
            "(" +
            this->_debug(tree->left) + " " +
            debugger::dump(tree->data) + " [" +
            debugger::dump(tree->length) + "] " +
            this->_debug(tree->right) +
            ")";
    }

    debugger::debug_t _debug(node_pointer tree)
        requires LEAF_ONLY
    {
        if(!tree || tree == node_handler::nil) return "";

        this->_push(tree);

        return
            "(" +
            this->_debug(tree->left) + " " +
            (
                tree->is_leaf()
                    ?
                        debugger::dump(tree->data) + " [" +
                        debugger::dump(tree->size) + "] "
                    :
                        ""
            ) +
            this->_debug(tree->right) +
            ")";
    }
};


} // namespace internal


} // namespace uni