data_structure/fenwick_tree.hpp

View this file on GitHub
Last update: 2024-07-27 23:01:00+09:00
Include: #include "data_structure/fenwick_tree.hpp"

Depends on

Required by

Verified with

Code

#pragma once


#include <cassert>
#include <vector>
#include <iterator>
#include <utility>
#include <type_traits>
#include <concepts>
#include <ranges>
#include <bit>


#include "internal/dev_env.hpp"
#include "internal/concepts.hpp"
#include "internal/types.hpp"
#include "internal/iterator.hpp"
#include "internal/point_reference.hpp"
#include "internal/range_reference.hpp"
#include "internal/unconstructible.hpp"

#include "snippet/iterations.hpp"
#include "numeric/bit.hpp"

#include "action/base.hpp"
#include "algebraic/internal/concepts.hpp"


namespace uni {

namespace internal {

namespace fenwick_tree_impl {


// Thanks to: atcoder::fenwick_tree
template<algebraic::internal::monoid Operand>
struct core {
    using operand = Operand;
    using size_type = internal::size_t;

  private:
    size_type _n = 0, _bit_ceil = 0;
    std::vector<operand> _data;

    inline void _init() noexcept(NO_EXCEPT) {
        FOR(i, 1, this->_n) {
            size_type j = i + (i & -i);
            if(j <= this->_n) this->_data[j-1] = this->_data[j-1] + this->_data[i-1];
        }
    }

  public:
    core() noexcept(NO_EXCEPT) {}

    explicit core(const size_type n) noexcept(NO_EXCEPT)
      : _n(n), _bit_ceil(std::bit_ceil<std::make_unsigned_t<size_type>>(n)), _data(n, operand{})
    {}

    inline size_type size() const noexcept(NO_EXCEPT) { return this->_n; }


    template<std::input_iterator I, std::sentinel_for<I> S>
    inline void assign(I first, S last) noexcept(NO_EXCEPT) {
        if constexpr(std::sized_sentinel_for<S, I>) {
            assert(std::ranges::distance(first, last) == this->size());
        }
        for(size_type i = 0; first < last; ++i, ++first) this->_data[i] = *first;
        this->_init();
    }


    inline void add(size_type p, const operand& x) noexcept(NO_EXCEPT) {
        for(p++; p<=this->_n; p += p & -p) this->_data[p-1] = this->_data[p-1] + x;
    }

    inline void set(const size_type p, const operand& x) noexcept(NO_EXCEPT) {
        assert(this->get(p) == this->fold(p, p+1));
        this->add(p, x + -this->get(p));
    }

    inline operand fold(size_type r) const noexcept(NO_EXCEPT) {
        operand s = operand{};
        for(; r>0; r -= r & -r) s = s + this->_data[r-1];
        return s;
    }
    inline operand fold(size_type l, size_type r) const noexcept(NO_EXCEPT) {
        operand s = operand{};
        for(; l < r; r -= r & -r) s = s + this->_data[r-1];
        for(; r < l; l -= l & -l) s = s + -this->_data[l-1];
        return s;
    }

    inline operand get(size_type p) const noexcept(NO_EXCEPT) {
        return this->fold(p, p+1);
    }

    template<class F>
    inline size_type max_right(size_type l, F&& f) const noexcept(NO_EXCEPT)
        requires algebraic::internal::invertible<operand>
    {
        assert(0 <= l && l <= this->_n);
        assert(f(operand{}));
        if(l == this->_n) return this->_n;
        operand inv = -this->fold(l);
        size_type p = 0, q = this->_bit_ceil;
        for(size_type k=q; k>0; k >>= 1) {
            if(p+k <= this->_n and f(this->_data[p+k-1] + inv)) {
                inv = inv + this->_data[(p+=k)-1];
            }
        }
        return p;
    }

    template<class F> inline size_type min_left(size_type r, F&& f) const noexcept(NO_EXCEPT)
        requires algebraic::internal::invertible<operand>
    {
        assert(0 <= r && r <= this->_n);
        assert(f(operand{}));
        if(r == 0) return 0;
        operand acc = this->fold(r);
        size_type p = 0, q = std::bit_ceil<std::make_unsigned_t<size_type>>(r);
        for(size_type k=q; k>0; k >>= 1) {
            if(p+k < r and !f(acc + -this->_data[p+k-1])) {
                acc = acc + -this->_data[(p+=k)-1];
            }
        }
        if(p == 0 and f(acc)) return 0;
        return p + 1;
    }
};


} // namespace fenwick_tree_impl

} // namespace internal


template<class Value>
struct fenwick_tree : internal::unconstructible {};


template<algebraic::internal::monoid Monoid>
struct fenwick_tree<Monoid> : internal::fenwick_tree_impl::core<Monoid> {
    static_assert(algebraic::internal::commutative<Monoid>);

  private:
    using core = typename internal::fenwick_tree_impl::core<Monoid>;

    core _impl;

  public:
    using value_type = typename core::operand;
    using size_type = typename core::size_type;

  protected:
    inline size_type _positivize_index(const size_type p) const noexcept(NO_EXCEPT) {
        return p < 0 ? this->_impl.size() + p : p;
    }

  public:
    fenwick_tree() noexcept(NO_EXCEPT) : _impl() {}

    explicit fenwick_tree(const size_type n) noexcept(NO_EXCEPT) : _impl(n) {}
    explicit fenwick_tree(const size_type n, const value_type& v) noexcept(NO_EXCEPT) : _impl(n) { this->_impl.fill(v); }

    template<std::convertible_to<value_type> T>
    fenwick_tree(const std::initializer_list<T>& init_list) noexcept(NO_EXCEPT) : fenwick_tree(ALL(init_list)) {}

    template<std::input_iterator I, std::sized_sentinel_for<I> S>
    explicit fenwick_tree(I first, S last) noexcept(NO_EXCEPT)
      : fenwick_tree(static_cast<size_type>(std::ranges::distance(first, last)))
    { this->assign(first, last); }

    template<std::ranges::input_range R>
    explicit fenwick_tree(R&& range) noexcept(NO_EXCEPT) : fenwick_tree(ALL(range)) {}


    template<std::convertible_to<value_type> T>
    inline auto& assign(const std::initializer_list<T>& init_list) noexcept(NO_EXCEPT){ return this->assign(ALL(init_list)); }

    template<std::input_iterator I, std::sentinel_for<I> S>
    inline auto& assign(I first, S last) noexcept(NO_EXCEPT) {
        this->_impl.assign(first, last);
        return *this;
    }

    template<std::ranges::input_range R>
    inline auto& assign(R&& range) noexcept(NO_EXCEPT) { return this->assign(ALL(range)); }

    inline auto& fill(const value_type& v = value_type()) noexcept(NO_EXCEPT) {
        std::fill(this->data(), this->data() + this->_impl.size(), v);
        this->_init();
        return *this;
    }

    inline auto size() const noexcept(NO_EXCEPT) { return this->_impl.size(); }
    inline bool empty() const noexcept(NO_EXCEPT) { return this->_impl.size() == 0; }

    struct point_reference : internal::point_reference<fenwick_tree> {
        point_reference(fenwick_tree *const super, const size_type p) noexcept(NO_EXCEPT)
          : internal::point_reference<fenwick_tree>(super, super->_positivize_index(p))
        {
            assert(0 <= this->_pos && this->_pos < this->_super->size());
        }

        operator value_type() const noexcept(NO_EXCEPT) { return this->_super->get(this->_pos); }
        auto val() const noexcept(NO_EXCEPT) { return this->_super->get(this->_pos); }

        inline auto& operator=(const value_type& v) noexcept(NO_EXCEPT) {
            this->_super->set(this->_pos, v);
            return *this;
        }

        inline auto& operator+=(const value_type& v) noexcept(NO_EXCEPT) {
            this->_super->add(this->_pos, v);
            return *this;
        }
    };

    struct range_reference : internal::range_reference<fenwick_tree> {
        range_reference(fenwick_tree *const super, const size_type l, const size_type r) noexcept(NO_EXCEPT)
          : internal::range_reference<fenwick_tree>(super, super->_positivize_index(l), super->_positivize_index(r))
        {
            assert(0 <= this->_begin && this->_begin <= this->_end && this->_end <= this->_super->size());
        }

        inline auto fold() noexcept(NO_EXCEPT) {
            if(this->_begin == 0 and this->_end == this->_super->size()) return this->_super->fold();
            if(this->_begin == 0) return this->_super->fold(this->_end);
            return this->_super->fold(this->_begin, this->_end);
        }
    };


    inline auto& add(const size_type p, const value_type& x) noexcept(NO_EXCEPT) {
        assert(0 <= p && p < this->_impl.size());
        this->_impl.add(p, x);
         return *this;
    }

    inline auto& set(const size_type p, const value_type& x) noexcept(NO_EXCEPT)
        requires algebraic::internal::invertible<value_type>
    {
        assert(0 <= p && p < this->_impl.size());
        this->_impl.set(p, x);
         return *this;
    }

    inline value_type get(const size_type p) const noexcept(NO_EXCEPT)
        requires algebraic::internal::invertible<value_type>
    {
        assert(0 <= p && p < this->_impl.size());
        return this->_impl.get(p);
    }

    inline auto operator[](const size_type p) noexcept(NO_EXCEPT) { return point_reference(this, p); }

    inline const auto operator()(const size_type l, const size_type r) const noexcept(NO_EXCEPT) {
        return range_reference(this, l, r);
    }

    inline auto operator()(const size_type l, const size_type r) noexcept(NO_EXCEPT) {
        return range_reference(this, l, r);
    }

    inline auto fold(const size_type l, const size_type r) const noexcept(NO_EXCEPT)
        requires algebraic::internal::invertible<value_type>
    {
        assert(0 <= l && l <= r && r <= this->_impl.size());
        return this->_impl.fold(l, r);
    }

    inline auto fold(const size_type r) const noexcept(NO_EXCEPT) {
        assert(0 <= r && r <= this->_impl.size());
        return this->_impl.fold(r);
    }

    inline auto fold() const noexcept(NO_EXCEPT) {
        return this->_impl.fold(this->_impl.size());
    }

    struct iterator;

  protected:
    using iterator_interface = internal::container_iterator_interface<value_type, const fenwick_tree, iterator>;

  public:
    struct iterator : iterator_interface {
        using iterator_interface::iterator_interface;
    };

    inline auto begin() const noexcept(NO_EXCEPT) { return iterator(this, 0); }
    inline auto end() const noexcept(NO_EXCEPT) { return iterator(this, this->_impl.size()); }

    inline auto rbegin() const noexcept(NO_EXCEPT) { return std::make_reverse_iterator(this->end()); }
    inline auto rend() const noexcept(NO_EXCEPT) { return std::make_reverse_iterator(this->begin()); }
};


template<actions::internal::operatable_action Action>
struct fenwick_tree<Action> : fenwick_tree<typename Action::operand> {
    using fenwick_tree<typename Action::operand>::fenwick_tree;
};


} // namespace uni

#line 2 "data_structure/fenwick_tree.hpp"


#include <cassert>
#include <vector>
#include <iterator>
#include <utility>
#include <type_traits>
#include <concepts>
#include <ranges>
#include <bit>


#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/concepts.hpp"


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

#include <cstdint>

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/iterator.hpp"


#line 7 "internal/iterator.hpp"
#include <variant>
#include <compare>
#line 10 "internal/iterator.hpp"


#line 13 "internal/iterator.hpp"

#line 2 "internal/type_traits.hpp"


#include <iostream>
#line 7 "internal/type_traits.hpp"
#include <algorithm>
#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>
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 {  // 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 16 "internal/iterator.hpp"


namespace uni {

namespace internal {


template<class T>
struct iterator_interface {
    using iterator_category = std::output_iterator_tag;

    using difference_type = size_t;
    using value_type = T;

    using pointer = T*;
    using reference = T&;

    // virtual T operator*() const noexcept(NO_EXCEPT) { return 0; };
};

template<class T>
struct forward_iterator : iterator_interface<T> {
    using iterator_category = std::forward_iterator_tag;

    // virtual bidirectional_iterator_interface& operator++() = 0;
};

template<class T>
struct bidirectional_iterator_interface : forward_iterator<T> {
    using iterator_category = std::bidirectional_iterator_tag;

    // virtual bidirectional_iterator_interface& operator--() = 0;
};

template<class T>
struct random_access_iterator_base : bidirectional_iterator_interface<T> {
    using iterator_category = std::random_access_iterator_tag;
    using difference_type = typename bidirectional_iterator_interface<T>::difference_type;

  public:
    // virtual random_access_iterator_base& operator+=(const difference_type count) = 0;
    // virtual random_access_iterator_base& operator-=(const difference_type count) = 0;

    friend inline random_access_iterator_base operator+(random_access_iterator_base itr, const difference_type count) noexcept(NO_EXCEPT) { return itr += count, itr; }
    friend inline random_access_iterator_base operator-(random_access_iterator_base itr, const difference_type count) noexcept(NO_EXCEPT) { return itr -= count, itr; }

};

template<class T, class Container, class Derived>
struct container_iterator_interface : random_access_iterator_base<T> {
    using difference_type = std::make_signed_t<typename Container::size_type>;

  private:
    using derived = std::remove_cvref_t<Derived>;

    Container* _ref;
    difference_type _pos;

    static_assert(std::three_way_comparable<difference_type>);

    inline auto* _derived() noexcept(NO_EXCEPT) {
        return static_cast<derived*>(this);
    }
    inline const auto* _derived() const noexcept(NO_EXCEPT) {
        return static_cast<const derived*>(this);
    }

  public:
    container_iterator_interface() noexcept = default;
    container_iterator_interface(Container *const ref, const difference_type pos) noexcept(NO_EXCEPT) : _ref(ref), _pos(pos) {}

    inline auto ref() const noexcept(NO_EXCEPT) { return this->_ref; }

    inline auto pos() const noexcept(NO_EXCEPT) { return this->_pos; }
    inline auto& pos() { return this->_pos; }

    inline auto& operator++() noexcept(NO_EXCEPT) { return ++this->_pos, *this->_derived(); }
    inline auto& operator--() noexcept(NO_EXCEPT) { return --this->_pos, *this->_derived(); }

    inline auto operator++(int) noexcept(NO_EXCEPT) { auto res = *this->_derived(); return ++this->_pos, res; }
    inline auto operator--(int) noexcept(NO_EXCEPT) { auto res = *this->_derived(); return --this->_pos, res; }

    inline auto& operator+=(const difference_type count) noexcept(NO_EXCEPT) { return this->_pos += count, *this->_derived(); }
    inline auto& operator-=(const difference_type count) noexcept(NO_EXCEPT) { return this->_pos -= count, *this->_derived(); }

    inline auto operator*() const noexcept(NO_EXCEPT) { return this->ref()->get(this->_pos); }
    inline auto operator[](const difference_type count) const noexcept(NO_EXCEPT) { return *(*this->_derived() + count); }

    inline auto operator-(const derived& other) const noexcept(NO_EXCEPT) { return this->_pos - other._pos; }


    friend inline bool operator==(const derived& lhs, const derived& rhs) noexcept(NO_EXCEPT) {
        if(lhs.ref() == rhs.ref()) return lhs._pos == rhs._pos;
        return false;
    }

    friend inline std::partial_ordering operator<=>(const derived& lhs, const derived& rhs) noexcept(NO_EXCEPT) {
        if(lhs.ref() != rhs.ref()) return std::partial_ordering::unordered;
        return lhs._pos <=> rhs._pos;
    }
};


namespace iterator_impl {


template<class... Tags>
using is_all_random_access_iterator = is_base_of_all<std::random_access_iterator_tag,Tags...>;

template<class... Tags>
using is_all_bidirectional_iterator = is_base_of_all<std::bidirectional_iterator_tag,Tags...>;

template<class... Tags>
using is_all_forward_iterator = is_base_of_all<std::forward_iterator_tag,Tags...>;

template<class... Tags>
using is_all_input_iterator = is_base_of_all<std::input_iterator_tag,Tags...>;


template<class... Tags>
constexpr auto _most_primitive_iterator_tag() {
    if constexpr(is_all_random_access_iterator<Tags...>::value) {
        return std::random_access_iterator_tag{};
    }
    else if constexpr(is_all_bidirectional_iterator<Tags...>::value) {
        return std::bidirectional_iterator_tag{};
    }
    else if constexpr(is_all_forward_iterator<Tags...>::value) {
        return std::forward_iterator_tag{};
    }
    else {
        return std::input_iterator_tag{};
    }
}


} // namespace iterator_impl


template<class... Tags>
using most_primitive_iterator_tag = decltype(iterator_impl::_most_primitive_iterator_tag<Tags...>());


template<class T, class = void>
struct is_iterator {
   static constexpr bool value = false;
};

template<class T>
struct is_iterator<T, typename std::enable_if<!std::is_same<typename std::iterator_traits<T>::value_type, void>::value>::type> {
   static constexpr bool value = true;
};

template<class T>
inline constexpr bool is_iterator_v = is_iterator<T>::value;

template<class T>
using is_iterator_t = std::enable_if_t<is_iterator_v<T>>;

template<class T>
using iota_diff_t = std::make_signed_t<T>;


} // namespace internal

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


#line 6 "internal/point_reference.hpp"


#line 9 "internal/point_reference.hpp"

#line 2 "global/constants.hpp"


#line 7 "global/constants.hpp"
#include <cmath>


#line 2 "snippet/aliases.hpp"


#line 8 "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 12 "snippet/aliases.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


namespace uni {


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


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>;


}  // 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 11 "global/constants.hpp"

#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 14 "global/constants.hpp"

#line 2 "numeric/limits.hpp"


#line 6 "numeric/limits.hpp"


#line 9 "numeric/limits.hpp"

#line 11 "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();


} // namespace uni
#line 16 "global/constants.hpp"


namespace uni {


namespace internal {
    template<class T>
    consteval auto get_pi() {
        if constexpr(std::integral<T>) {
            return static_cast<T>(3);
        }
        else if constexpr(std::same_as<T, float>) {
            return M_PIf;
        }
        else if constexpr(std::same_as<T, double>) {
            return M_PI;
        }
        else if constexpr(std::same_as<T, ld>) {
            return M_PIl;
        }
        else {
            static_assert(EXCEPTION_ON_TYPE<T>);
        }
    }
} // namespace internal


template<class T = ld>
constexpr auto PI = internal::get_pi<T>();


enum class comparison : std::uint8_t {
    equal_to,
    not_equal_to,

    equals = equal_to,
    eq = equal_to,

    under,
    over,
    or_under,
    or_over,

    less = under,
    more = over,

    less_than = under,
    more_than = over,
    not_less_than = or_over,
    not_more_than = or_under,

    leq = or_under,
    geq = or_over
};


enum class interval_notation : std::uint8_t {
    right_open,
    left_open,
    open,
    closed,
};


enum class replacement_policy : std::uint8_t {
    insert_sync,
    overwrite_sync,
    overwrite_async
};


enum class rotation : std::int8_t {
    clockwise,

    counter_clockwise,
    anti_clockwise = counter_clockwise,
};


enum class positional_relation : std::int8_t {
    clockwise,

    counter_clockwise,
    anti_clockwise = counter_clockwise,

    backward,
    forward,

    in,
    on,
    out,

    included = in,
    inscribed,
    intersecting,
    circumscribed,
    distant,
};


enum class alignment : std::int8_t {
    left,
    center,
    right
};


} // namespace uni
#line 11 "internal/point_reference.hpp"


namespace uni {

namespace internal {


template<class Super, std::integral SizeType = typename Super::size_type>
struct point_reference {
    using size_type = SizeType;
    using iterator = typename Super::iterator;

  protected:
    Super *const _super;
    const size_type _pos;

    point_reference(Super *const super, const size_type pos) noexcept(NO_EXCEPT) : _super(super), _pos(pos) {}

    inline auto index() noexcept(NO_EXCEPT) { return this->_pos; }
};


} // namespace internal

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


#line 8 "internal/range_reference.hpp"


#line 11 "internal/range_reference.hpp"

#line 13 "internal/range_reference.hpp"


namespace uni {

namespace internal {


template<class Super, std::integral SizeType = typename Super::size_type>
struct range_reference {
    using size_type = SizeType;
    using iterator = Super::iterator;

  protected:
    Super *const _super;
    const size_type _begin, _end;

    range_reference(Super *const super, const size_type begin, const size_type end) noexcept(NO_EXCEPT) : _super(super), _begin(begin), _end(end) {}

  public:
    inline auto begin() const noexcept(NO_EXCEPT) { return std::ranges::next(std::ranges::begin(*this->_super), this->_begin); }
    inline auto end() const noexcept(NO_EXCEPT) { return std::ranges::next(std::ranges::begin(*this->_super), this->_end); }

    inline auto size() const noexcept(NO_EXCEPT) { return this->_end - this->_begin; }

    inline auto interval() const noexcept(NO_EXCEPT) { return std::make_pair(this->_begin, this->_end); }

  protected:
    inline auto sub_range(size_type l, size_type r) const noexcept(NO_EXCEPT) {
        l = _super->_positivize_index(l), r = _super->_positivize_index(r);
        assert(0 <= l and l <= r and r <= this->size());

        return range_reference(_super, this->_begin + l, this->_begin + r);
    }

  public:
    template<uni::interval_notation rng = uni::interval_notation::right_open>
    inline auto range(const size_type l, const size_type r) const noexcept(NO_EXCEPT) {
        if constexpr(rng == uni::interval_notation::right_open) return this->sub_range(l, r);
        if constexpr(rng == uni::interval_notation::left_open) return this->sub_range(l+1, r+1);
        if constexpr(rng == uni::interval_notation::open) return this->sub_range(l+1, r);
        if constexpr(rng == uni::interval_notation::closed) return this->sub_range(l, r+1);
    }
    inline auto range() const noexcept(NO_EXCEPT) { return range_reference(this->_begin, this->_end); }

    inline auto operator()(const size_type l, const size_type r) const noexcept(NO_EXCEPT) { return this->sub_range(l, r); }

    inline auto subseq(const size_type p, const size_type c) const noexcept(NO_EXCEPT) { return this->sub_range(p, p+c); }
    inline auto subseq(const size_type p) const noexcept(NO_EXCEPT) { return this->sub_range(p, this->size()); }
};


} // namespace internal

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


namespace uni {

namespace internal {


struct unconstructible  {
  private:
    template<class... Args>
    unconstructible(Args...) = delete;
};


} // namespace internal

} // namespace uni
#line 21 "data_structure/fenwick_tree.hpp"

#line 2 "snippet/iterations.hpp"

#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 2 "numeric/bit.hpp"


#include <immintrin.h>

#line 8 "numeric/bit.hpp"
#include <cstddef>
#line 13 "numeric/bit.hpp"


#line 16 "numeric/bit.hpp"

#line 2 "numeric/arithmetic.hpp"


#line 5 "numeric/arithmetic.hpp"
#include <cstring>
#line 7 "numeric/arithmetic.hpp"
#include <string>
#line 10 "numeric/arithmetic.hpp"
#include <optional>
#line 14 "numeric/arithmetic.hpp"


#include <atcoder/math>


#line 21 "numeric/arithmetic.hpp"

#line 25 "numeric/arithmetic.hpp"

#line 2 "utility/internal/functional_base.hpp"


namespace uni {


template<class P>
    requires
        requires(P p) {
            p.first;
            p.second;
        }
inline P swapped(P& pair) {
    return P{ pair.second, pair.first };
}


} // namespace uni
#line 27 "numeric/arithmetic.hpp"

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


#line 6 "numeric/internal/number_base.hpp"
#include <string_view>
#line 14 "numeric/internal/number_base.hpp"


#line 18 "numeric/internal/number_base.hpp"

#line 2 "adaptor/string.hpp"


#line 6 "adaptor/string.hpp"

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


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

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

#line 15 "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 6 "iterable/internal/operation_base.hpp"
#include <sstream>
#include <numeric>


#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 18 "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);
    }

    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(const T& v) noexcept(NO_EXCEPT) {
        return std::ranges::binary_search(*this, v);
    }

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

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

    inline auto join(const char* sep = "") 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 2 "adaptor/vector.hpp"


#line 6 "adaptor/vector.hpp"


#line 9 "adaptor/vector.hpp"


namespace uni {


template<class... Args>
using vector = internal::advanced_container<std::vector<Args...>>;


} // namespace uni
#line 21 "numeric/internal/number_base.hpp"


namespace uni {


template<std::size_t B, class T>
uni::string to_base_n_string(T v) noexcept(NO_EXCEPT) {
    constexpr std::string_view CHARS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    static_assert(0 < B and B <= std::ranges::size(CHARS));
    assert(0 <= v);

    uni::string res;
    while(v > 0) {
        res += CHARS[v%B];
        v /= B;
    }
    std::reverse(ALL(res));

    return res;
}


template<class T>
uni::string to_base_n_string(T v, const uni::internal::size_t b) noexcept(NO_EXCEPT) {
    constexpr std::string_view CHARS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    assert(1 < b && b <= std::ranges::ssize(CHARS));
    assert(0 <= v);

    if(v == 0) return "0";

    uni::string res;

    while(v > 0) {
        res += CHARS[v % b];
        v /= b;
    }
    std::reverse(ALL(res));

    return res;
}

template<class T>
uni::vector<T> to_base_n_vector(T v, const uni::internal::size_t b) noexcept(NO_EXCEPT) {
    assert(1 < b);
    assert(0 <= v);

    uni::vector<T> res;

    while(v > 0) {
        res.push_back(v%b);
        v /= b;
    }


    return res;
}

template<std::bidirectional_iterator I, class T = typename std::iterator_traits<I>::value_type>
T from_base_n_sequence(I begin, I end, const uni::internal::size_t b) noexcept(NO_EXCEPT) {
    assert(1 < b);

    if(begin == end) return 0;

    T res = 0;
    for(auto itr=end; itr-- != begin; ) {
        res *= b;
        res += *itr;
    }

    return res;
}

template<class T, std::forward_iterator I>
T from_base_n_string(I begin, I end, const uni::internal::size_t b) noexcept(NO_EXCEPT) {
    assert(1 < b);

    if(begin == end) return 0;

    T sgn = 1;
    if(*begin == '-') {
        sgn = -1;
        ++begin;
    }

    T res = 0;
    for(auto itr=begin; itr != end; ++itr) {
        res *= b;
        if('0' <= *itr && *itr <= '9') {
            res += *itr - '0';
        }
        else if('a' <= *itr && *itr <= 'z') {
            res += *itr - 'a' + 10;
        }
        else if('A' <= *itr && *itr <= 'Z'){
            res += *itr - 'A' + 10;
        }
        else {
            assert(false);
        }
    }

    return res * sgn;
}


template<std::ranges::bidirectional_range R, class T = std::ranges::range_value_t<R>>
    requires std::ranges::common_range<R>
T from_base_n_sequence(R range, const uni::internal::size_t b) noexcept(NO_EXCEPT) {
    return from_base_n_sequence(std::ranges::begin(range), std::ranges::end(range), b);
}

template<class T, std::ranges::bidirectional_range R>
    requires std::ranges::common_range<R>
T from_base_n_string(R range, const uni::internal::size_t b) noexcept(NO_EXCEPT) {
    return from_base_n_string<T>(std::ranges::begin(range), std::ranges::end(range), b);
}



} // namespace uni
#line 29 "numeric/arithmetic.hpp"

#line 2 "iterable/operation.hpp"


#line 6 "iterable/operation.hpp"
#include <initializer_list>
#line 9 "iterable/operation.hpp"
#include <valarray>
#line 17 "iterable/operation.hpp"


#line 21 "iterable/operation.hpp"

#line 2 "internal/ranges.hpp"


#line 6 "internal/ranges.hpp"
#include <tuple>


#line 11 "internal/ranges.hpp"


namespace uni {

namespace internal {


template<class Range>
concept resizable_range
  = std::ranges::range<Range> &&
    requires (Range& r) { r.resize(0); };

template<class range>
concept simple_view
  = std::ranges::view<range> && std::ranges::range<const range> &&
    std::same_as<std::ranges::iterator_t<range>, std::ranges::iterator_t<const range>> &&
    std::same_as<std::ranges::sentinel_t<range>, std::ranges::sentinel_t<const range>>;


template<class... Ranges>
concept zip_is_common = (sizeof...(Ranges) == 1 && (std::ranges::common_range<Ranges> && ...))
    || (!(std::ranges::bidirectional_range<Ranges> && ...) && (std::ranges::common_range<Ranges> && ...))
    || ((std::ranges::random_access_range<Ranges> && ...) && (std::ranges::sized_range<Ranges> && ...));


template<bool Const, class... Views>
concept all_contiguous = (std::ranges::contiguous_range<maybe_const_t<Const, Views>> && ...);

template<bool Const, class... Views>
concept all_random_access = (std::ranges::random_access_range<maybe_const_t<Const, Views>> && ...);

template<bool Const, class... Views>
concept all_bidirectional = (std::ranges::bidirectional_range<maybe_const_t<Const, Views>> && ...);

template<bool Const, class... Views>
concept all_forward = (std::ranges::forward_range<maybe_const_t<Const, Views>> && ...);


template<bool Const, class... Views> struct zip_view_iterator_category {};

template<bool Const, class... Views>
    requires all_forward<Const, Views...>
struct zip_view_iterator_category<Const, Views...> {
    using iterator_category = std::input_iterator_tag;
};


template<bool Const, class... Views>
static auto _most_primitive_iterator_concept() noexcept(NO_EXCEPT) {
    if constexpr(all_random_access<Const, Views...>)
        return std::random_access_iterator_tag{};
    else if constexpr(all_bidirectional<Const, Views...>)
        return std::bidirectional_iterator_tag{};
    else if constexpr(all_forward<Const, Views...>)
        return std::forward_iterator_tag{};
    else
        return std::input_iterator_tag{};
}

template<bool Const, class... Views>
using most_primitive_iterator_concept = decltype(_most_primitive_iterator_concept<Const, Views...>());


template<class Range, bool Const>
using range_iterator_category = typename std::iterator_traits<
        std::ranges::iterator_t<maybe_const_t<Const, Range>>
    >::iterator_category;



template<class Range>
static constexpr auto _iterator_concept() noexcept(NO_EXCEPT) {
    if constexpr(std::ranges::random_access_range<Range>)
        return std::random_access_iterator_tag{};
    else if constexpr(std::ranges::bidirectional_range<Range>)
        return std::bidirectional_iterator_tag{};
    else if constexpr(std::ranges::forward_range<Range>)
        return std::forward_iterator_tag{};
    else
        return std::input_iterator_tag{};
}

template<class Range>
using iterator_concept = decltype(_iterator_concept<Range>());



template<std::ranges::range Range> struct cached_position {
    constexpr bool has_value() const { return false; }

    constexpr std::ranges::iterator_t<Range> get(const Range&) const {
        __builtin_unreachable();
    }

    constexpr void set(const Range &, const std::ranges::iterator_t<Range> &) const {}
};

template<std::ranges::forward_range Range>
struct cached_position<Range> : protected std::optional<std::ranges::iterator_t<Range>> {
    using std::optional<std::ranges::iterator_t<Range>>::optioanl;
    using std::optional<std::ranges::iterator_t<Range>>::has_value;

    constexpr std::ranges::iterator_t<Range> get(const Range&) const {
        assert(this->has_value());
        return **this;
    }

    constexpr void set(const Range&, const std::ranges::iterator_t<Range>& itr) {
        assert(!this->has_value());
        this->emplace(*itr);
    }
};


template<std::ranges::random_access_range Range>
    requires(sizeof(std::ranges::range_difference_t<Range>) <= sizeof(std::ranges::iterator_t<Range>))
struct cached_position<Range> {
  private:
    std::ranges::range_difference_t<Range> _offset = -1;

  public:
    cached_position() = default;

    constexpr cached_position(const cached_position &) = default;

    constexpr cached_position(cached_position &&other) noexcept {
        *this = std::move(other);
    }

    constexpr cached_position &operator=(const cached_position &) = default;

    constexpr cached_position &operator=(cached_position &&other) noexcept {
        // Propagate the cached offset, but invalidate the source.
        this->_offset = other._offset;
        other._offset = -1;
        return *this;
    }

    constexpr bool has_value() const { return this->_offset >= 0; }

    constexpr std::ranges::iterator_t<Range> get(Range& range) const {
        assert(this->has_value());
        return std::ranges::begin(range) + this->_offset;
    }

    constexpr void set(Range &range, const std::ranges::iterator_t<Range> &itr) {
        assert(!this->has_value());
        this->_offset = itr - std::ranges::begin(range);
    }
};


template<typename T, int Disc>
struct absent { };

template<bool PRESENT, class T, int Disc = 0>
using maybe_present_t = std::conditional_t<PRESENT, T, absent<T, Disc>>;


} // namespace internal


namespace views::adaptor {


template<class Adaptor, class... Args>
concept adaptor_invocable = requires { std::declval<Adaptor>()(std::declval<Args>()...); };

template<class Adaptor, class... Args>
concept adaptor_partial_app_viable =
    (Adaptor::arity > 1) && (sizeof...(Args) == Adaptor::arity - 1) &&
    (std::constructible_from<std::remove_cvref_t<Args>, Args> && ...);

template<class Adaptor, class... Args> struct partial;

template<class, class> struct pipe;


template<class Derived> struct range_adaptor_closure {};


template<class T, class U>
    requires(!std::same_as<T, range_adaptor_closure<U>>)
void is_range_adaptor_closure_fn(const T &, const range_adaptor_closure<U> &);


template<class T>
concept is_range_adaptor_closure = requires(T t) { adaptor::is_range_adaptor_closure_fn(t, t); };


template<class Self, class Range>
    requires is_range_adaptor_closure<Self> && adaptor_invocable<Self, Range>
constexpr auto operator|(Range&& range, Self&& self) {
    return std::forward<Self>(self)(std::forward<Range>(range));
}


template<class Lhs, class Rhs>
    requires is_range_adaptor_closure<Lhs> && is_range_adaptor_closure<Rhs>
constexpr auto operator|(Lhs&& lhs, Rhs&& rhs) {
    return pipe<std::remove_cvref_t<Lhs>, std::remove_cvref_t<Rhs>>{ std::forward<Lhs>(lhs), std::forward<Rhs>(rhs)};
}


template<class Derived> struct range_adaptor {
    template<class... Args>
        requires adaptor_partial_app_viable<Derived, Args...>
    inline constexpr auto operator()(Args&& ..._args) const noexcept(NO_EXCEPT) {
        return partial<Derived, std::remove_cvref_t<Args>...>{
            std::forward<Args>(_args)...
        };
    }
};

template<class Adaptor>
concept closure_has_simple_call_op = Adaptor::has_simple_call_op;

template<class Adaptor, class... Args>
concept adaptor_has_simple_extra_args =
    Adaptor::has_simple_extra_args ||
    Adaptor::template has_simple_extra_args<Args...>;

template<class Adaptor, class... Args>
struct partial : range_adaptor_closure<partial<Adaptor, Args...>> {
    std::tuple<Args...> args;

    constexpr partial(Args... _args) noexcept(NO_EXCEPT) : args(std::move(_args)...) {}

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, const Args &...>
    inline constexpr auto operator()(Range&& range) const & noexcept(NO_EXCEPT) {
        const auto forwarder = [&range](const auto &..._args) constexpr noexcept(NO_EXCEPT) {
            return Adaptor{}(std::forward<Range>(range), _args...);
        };
        return std::apply(forwarder, this->args);
    }

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, Args...>
    inline constexpr auto operator()(Range&& range) && noexcept(NO_EXCEPT) {
        const auto forwarder = [&range](auto &..._args) constexpr noexcept(NO_EXCEPT) {
            return Adaptor{}(std::forward<Range>(range), std::move(_args)...);
        };
        return std::apply(forwarder, this->args);
    }

    template<class Range>
    inline constexpr auto operator()(Range&& range) const && = delete;
};

template<class Adaptor, class Arg>
struct partial<Adaptor, Arg> : range_adaptor_closure<partial<Adaptor, Arg>> {
    Arg arg;

    constexpr partial(Arg _arg) noexcept(NO_EXCEPT) : arg(std::move(_arg)) {}

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, const Arg &>
    inline constexpr auto operator()(Range&& range) const & noexcept(NO_EXCEPT) {
        return Adaptor{}(std::forward<Range>(range), this->arg);
    }

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, Arg>
    inline constexpr auto operator()(Range&& range) && noexcept(NO_EXCEPT) {
        return Adaptor{}(std::forward<Range>(range), std::move(this->arg));
    }

    template<class Range>
    inline constexpr auto operator()(Range&& range) const && = delete;
};

template<class Adaptor, class... Args>
    requires adaptor_has_simple_extra_args<Adaptor, Args...> && (std::is_trivially_copyable_v<Args> && ...)
struct partial<Adaptor, Args...> : range_adaptor_closure<partial<Adaptor, Args...>> {
    std::tuple<Args...> args;

    constexpr partial(Args... _args) noexcept(NO_EXCEPT) : args(std::move(_args)...) {}

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, const Args &...>
    inline constexpr auto operator()(Range&& range) const noexcept(NO_EXCEPT) {
        const auto forwarder = [&range](const auto &..._args) constexpr noexcept(NO_EXCEPT) {
            return Adaptor{}(std::forward<Range>(range), _args...);
        };
        return std::apply(forwarder, this->args);
    }

    static constexpr bool has_simple_call_op = true;
};

template<class Adaptor, class Arg>
    requires adaptor_has_simple_extra_args<Adaptor, Arg> &&
             std::is_trivially_copyable_v<Arg>
struct partial<Adaptor, Arg> : range_adaptor_closure<partial<Adaptor, Arg>> {
    Arg arg;

    constexpr partial(Arg _arg) noexcept(NO_EXCEPT) : arg(std::move(_arg)) {}

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, const Arg &>
    inline constexpr auto operator()(Range&& range) const noexcept(NO_EXCEPT) {
        return Adaptor{}(std::forward<Range>(range), this->arg);
    }

    static constexpr bool has_simple_call_op = true;
};

template<class Lhs, class Rhs, class Range>
concept pipe_invocable = requires {
    std::declval<Rhs>()(std::declval<Lhs>()(std::declval<Range>()));
};

template<class Lhs, class Rhs> struct pipe : range_adaptor_closure<pipe<Lhs, Rhs>> {
    [[no_unique_address]] Lhs lhs;
    [[no_unique_address]] Rhs rhs;

    constexpr pipe(Lhs _lhs, Rhs _rhs) noexcept(NO_EXCEPT) : lhs(std::move(_lhs)), rhs(std::move(_rhs)) {}

    template<class Range>
        requires pipe_invocable<const Lhs &, const Rhs &, Range>
    inline constexpr auto operator()(Range&& range) const & noexcept(NO_EXCEPT) {
        return rhs(lhs(std::forward<Range>(range)));
    }

    template<class Range>
        requires pipe_invocable<Lhs, Rhs, Range>
    inline constexpr auto operator()(Range&& range) && noexcept(NO_EXCEPT) {
        return std::move(rhs)(std::move(lhs)(std::forward<Range>(range)));
    }

    template<class Range>
    inline constexpr auto operator()(Range&& range) const && = delete;
};


template<class Lhs, class Rhs>
    requires closure_has_simple_call_op<Lhs> && closure_has_simple_call_op<Rhs>
struct pipe<Lhs, Rhs> : range_adaptor_closure<pipe<Lhs, Rhs>> {
    [[no_unique_address]] Lhs lhs;
    [[no_unique_address]] Rhs rhs;

    constexpr pipe(Lhs _lhs, Rhs _rhs) noexcept(NO_EXCEPT) : lhs(std::move(_lhs)), rhs(std::move(_rhs)) {}

    template<class Range>
        requires pipe_invocable<const Lhs &, const Rhs &, Range>
    inline constexpr auto operator()(Range&& range) const noexcept(NO_EXCEPT) {
        return rhs(lhs(std::forward<Range>(range)));
    }

    static constexpr bool has_simple_call_op = true;
};


} // namespace views::adaptor


} // namespace uni
#line 28 "iterable/operation.hpp"

#line 2 "iterable/z_array.hpp"


#line 6 "iterable/z_array.hpp"


#line 9 "iterable/z_array.hpp"

#line 2 "adaptor/valarray.hpp"


#line 11 "adaptor/valarray.hpp"

#line 14 "adaptor/valarray.hpp"

#line 16 "adaptor/valarray.hpp"


namespace uni {


template<class T> struct valarray : internal::advanced_container<std::valarray<T>> {
  private:
    using base = internal::advanced_container<std::valarray<T>>;

  public:
    using size_type = internal::size_t;

    using iterator = T*;
    using const_iterator = const T*;

  protected:
    inline bool _validate_index_in_right_open([[maybe_unused]] const size_type p) const noexcept(NO_EXCEPT) {
        return 0 <= p and p < this->size();
    }
    inline bool _validate_index_in_closed([[maybe_unused]] const size_type p) const noexcept(NO_EXCEPT) {
        return 0 <= p and p <= this->size();
    }
    inline bool _validate_rigth_open_interval([[maybe_unused]] const size_type l, [[maybe_unused]] const size_type r) const noexcept(NO_EXCEPT) {
        return 0 <= l and l <= r and r <= this->size();
    }

    inline size_type _positivize_index(const size_type p) const noexcept(NO_EXCEPT) {
        return p < 0 ? this->size() + p : p;
    }

  public:
    valarray() noexcept(NO_EXCEPT) {}

    explicit valarray(const std::size_t length, const T& val = T{}) noexcept(NO_EXCEPT) : base(val, length) {}

    template<std::input_iterator I, std::sentinel_for<I> S>
    valarray(I first, S last) noexcept(NO_EXCEPT) : base(std::ranges::distance(first, last)) { std::ranges::copy(first, last, std::ranges::begin(*this)); }

    template<class U> valarray(const U* pointer, const size_t n) noexcept(NO_EXCEPT) : base(pointer, n) {};

    valarray(const std::slice_array<T>& arr) noexcept(NO_EXCEPT) : base(arr) {};
    valarray(const std::gslice_array<T>& arr) noexcept(NO_EXCEPT) : base(arr) {};
    valarray(const std::mask_array<T>& arr) noexcept(NO_EXCEPT) : base(arr) {};
    valarray(const std::indirect_array<T>& arr) noexcept(NO_EXCEPT) : base(arr) {};
    valarray(const std::initializer_list<T>& init) noexcept(NO_EXCEPT) : base(init) {}
    valarray(const internal::advanced_container<std::valarray<T>>& arr) noexcept(NO_EXCEPT) : base(arr) {}

  #ifdef __GNUC__
    template<class Dom> valarray(const std::_Expr<Dom,T>& expr) noexcept(NO_EXCEPT) : base(expr) {}
  #endif

    inline auto size() const noexcept(NO_EXCEPT) { return static_cast<size_type>(this->base::size()); }

    inline void reserve(const size_type) noexcept(NO_EXCEPT) { /* do nothing */ }

    template<std::input_iterator I, std::sentinel_for<I> S>
    inline void assign(I first, S last) noexcept(NO_EXCEPT) {
        this->resize(std::ranges::distance(first, last));
        std::ranges::copy(first, last, std::ranges::begin(*this));
    }

    inline void assign(const std::size_t length, const T& val = T{}) noexcept(NO_EXCEPT) {
        this->base::resize(length, val);
    }

    inline void resize(const std::size_t length, const T& val = T{}) noexcept(NO_EXCEPT) {
        base temp = *this;
        this->assign(length, val);
        std::move(std::begin(temp), std::min(std::end(temp), std::next(std::begin(temp), length)), std::begin(*this));
    }

    inline const T& operator[](size_type pos) const noexcept(NO_EXCEPT) {
        pos = this->_positivize_index(pos), assert(this->_validate_index_in_right_open(pos));
        return this->base::operator[](pos);
    }
    inline T& operator[](size_type pos) noexcept(NO_EXCEPT) {
        pos = this->_positivize_index(pos), assert(this->_validate_index_in_right_open(pos));
        return this->base::operator[](pos);
    }

    inline const T& back() const noexcept(NO_EXCEPT) { return *std::prev(this->end()); }
    inline T& back() noexcept(NO_EXCEPT) { return *std::prev(this->end()); }

    inline const T& front() const noexcept(NO_EXCEPT) { return *this->begin(); }
    inline T& front() noexcept(NO_EXCEPT) { return *this->begin(); }

    inline auto rbegin() noexcept(NO_EXCEPT) { return std::make_reverse_iterator(std::ranges::end(*this)); }
    inline auto rend() noexcept(NO_EXCEPT) { return std::make_reverse_iterator(std::ranges::begin(*this)); }

    inline auto rbegin() const noexcept(NO_EXCEPT) { return std::make_reverse_iterator(std::ranges::end(*this)); }
    inline auto rend() const noexcept(NO_EXCEPT) { return std::make_reverse_iterator(std::ranges::begin(*this)); }
};


} // namespace uni
#line 11 "iterable/z_array.hpp"


namespace uni {


// Thanks to: atcoder::z_algorithm
template<class SizeType = internal::size_t, class Container = valarray<SizeType>>
struct z_array : Container {
    using size_type = SizeType;

    template<std::input_iterator I, std::sentinel_for<I> S>
    z_array(I first, S last) : Container(std::ranges::distance(first, last), {}) {
        const size_type n = static_cast<size_type>(std::ranges::distance(first, last));
        if(n == 0) return;
        for(size_type i = 1, j = 0; i < n; ++i) {
            size_type& k = this->operator[](i);
            k = (j + this->operator[](j) <= i) ? 0 : std::ranges::min(j + this->operator[](j) - i, this->operator[](i - j));
            while(i + k < n and first[k] == first[i + k]) ++k;
            if(j + this->operator[](j) < i + this->operator[](i)) j = i;
        }
        *this->begin() = n;
    }

    template<std::ranges::input_range R>
    explicit z_array(R&& range) : z_array(ALL(range)) {}
};


} // namespace uni
#line 31 "iterable/operation.hpp"

#line 2 "view/concat.hpp"


#line 11 "view/concat.hpp"


#line 18 "view/concat.hpp"



namespace uni {

namespace internal {

namespace view_impl {


template<std::ranges::input_range V0, std::ranges::input_range V1>
    requires std::ranges::view<V0> && std::ranges::view<V1>
struct concat_view : std::ranges::view_interface<concat_view<V0, V1>> {
  private:
    V0 _b0;
    V1 _b1;

    template<bool Const> using B0 = internal::maybe_const_t<Const, V0>;
    template<bool Const> using B1 = internal::maybe_const_t<Const, V1>;

    template<bool Const> struct iterator_tag {};

    template<bool Const>
        requires std::ranges::forward_range<B0<Const>> && std::ranges::forward_range<B1<Const>>
    struct iterator_tag<Const> {
      public:
        using iterator_category = uni::internal::most_primitive_iterator_tag<
            typename std::iterator_traits<std::ranges::iterator_t<B0<Const>>>::iterator_category,
            typename std::iterator_traits<std::ranges::iterator_t<B1<Const>>>::iterator_category
        >;
    };

  public:
    template<bool> class iterator;

    constexpr explicit concat_view(V0 v0, V1 v1) noexcept(NO_EXCEPT)
      : _b0(std::move(v0)), _b1(std::move(v1))
    {}

    inline constexpr std::pair<V0, V1> base() const & noexcept(NO_EXCEPT)
        requires std::copy_constructible<V0> && std::copy_constructible<V0>
    {
        return { this->_b0, this->_b1 };
    }

    inline constexpr std::pair<V0,V1> base() && noexcept(NO_EXCEPT) {
        return { std::move(this->_b0), std::move(this->_b1) };
    }

    inline constexpr auto begin() noexcept(NO_EXCEPT)
        requires (!internal::simple_view<V0> && !internal::simple_view<V1>)
    {
        return iterator<false>(this, std::ranges::begin(this->_b0), std::ranges::begin(this->_b1), 0);
    }

    inline constexpr auto begin() const noexcept(NO_EXCEPT)
        requires std::ranges::range<const V0> && std::ranges::range<const V1>
    {
        return iterator<true>(this, std::ranges::begin(this->_b0), std::ranges::begin(this->_b1), 0);
    }

    inline constexpr auto end() noexcept(NO_EXCEPT)
        requires (!internal::simple_view<V0> && !internal::simple_view<V1>)
    {
        if constexpr(std::ranges::common_range<V0> && std::ranges::common_range<V1>) {
            return iterator<false>(this, std::ranges::end(this->_b0), std::ranges::end(this->_b1), 1);
        }
        else {
            return std::default_sentinel;
        }
    }

    inline constexpr auto end() const noexcept(NO_EXCEPT)
        requires std::ranges::range<const V0> && std::ranges::range<const V1>
    {
        if constexpr(std::ranges::common_range<const V0> && std::ranges::common_range<const V1>) {
            return iterator<true>(this, std::ranges::end(this->_b0), std::ranges::end(this->_b1), 1);
        }
        else {
            return std::default_sentinel;
        }
    }

    inline constexpr auto size() noexcept(NO_EXCEPT)
        requires std::ranges::sized_range<V0> && std::ranges::sized_range<V1>
    {
        return static_cast<std::size_t>(std::ranges::distance(this->_b0) + std::ranges::distance(this->_b1));
    }

    inline constexpr auto size() const noexcept(NO_EXCEPT)
        requires std::ranges::sized_range<const V0> && std::ranges::sized_range<const V1>
    {
        return static_cast<std::size_t>(std::ranges::distance(this->_b0) + std::ranges::distance(this->_b1));
    }
};

template<std::ranges::input_range V0, std::ranges::input_range V1>
    requires std::ranges::view<V0> && std::ranges::view<V1>
template<bool Const>
struct concat_view<V0, V1>::iterator : iterator_tag<Const> {
  private:
    using Parent = internal::maybe_const_t<Const, concat_view>;

    using B0 = concat_view::B0<Const>;
    using B1 = concat_view::B1<Const>;

    std::ranges::iterator_t<B0> _c0 = std::ranges::iterator_t<B0>();
    std::ranges::iterator_t<B0> _b0 = std::ranges::iterator_t<B0>();
    std::ranges::sentinel_t<B0> _e0 = std::ranges::sentinel_t<B0>();

    std::ranges::iterator_t<B1> _c1 = std::ranges::iterator_t<B1>();
    std::ranges::iterator_t<B1> _b1 = std::ranges::iterator_t<B1>();
    std::ranges::sentinel_t<B1> _e1 = std::ranges::sentinel_t<B1>();

    int _block = 0;

    constexpr iterator(Parent *const parent, const std::ranges::iterator_t<B0> c0, const std::ranges::iterator_t<B1> c1, const int block) noexcept(NO_EXCEPT)
      : _c0(std::move(c0)), _b0(std::ranges::begin(parent->_b0)), _e0(std::ranges::end(parent->_b0)),
        _c1(std::move(c1)), _b1(std::ranges::begin(parent->_b1)), _e1(std::ranges::end(parent->_b1)),
        _block(block || std::ranges::empty(parent->_b0))
    {}

    friend concat_view;

  public:
    using difference_type = std::common_type_t<std::ranges::range_difference_t<B0>, std::ranges::range_difference_t<B1>>;

    using value_type = std::common_type_t<std::ranges::range_value_t<B0>, std::ranges::range_value_t<B1>>;
    using reference_type = std::common_reference_t<std::ranges::range_reference_t<B0>, std::ranges::range_reference_t<B1>>;

    using iterator_concept = most_primitive_iterator_concept<Const, V0, V1>;

    iterator() noexcept(NO_EXCEPT)
        requires std::default_initializable<std::ranges::iterator_t<B0>> &&
                 std::default_initializable<std::ranges::iterator_t<B0>>
    = default;

    constexpr iterator(iterator<!Const> itr) noexcept(NO_EXCEPT)
        requires
            Const &&
            std::convertible_to<std::ranges::iterator_t<V0>, std::ranges::iterator_t<B0>> &&
            std::convertible_to<std::ranges::sentinel_t<V0>, std::ranges::sentinel_t<B0>> &&
            std::convertible_to<std::ranges::iterator_t<V1>, std::ranges::iterator_t<B1>> &&
            std::convertible_to<std::ranges::sentinel_t<V1>, std::ranges::sentinel_t<B1>>
      : _c0(std::move(itr._c0)), _b0(std::move(itr._b0)), _e0(std::move(itr._e0)),
        _c1(std::move(itr._c0)), _b1(std::move(itr._b0)), _e1(std::move(itr._e1)),
        _block(itr._block)
    {}

    inline constexpr std::variant<std::ranges::iterator_t<B0>, std::ranges::iterator_t<B1>>
    base() && noexcept(NO_EXCEPT) {
        if(this->_block == 0) return std::move(this->_c0);
        else return std::move(this->_C1);
    }

    inline constexpr
        std::variant<
            std::reference_wrapper<const std::ranges::iterator_t<B0>>,
            std::reference_wrapper<const std::ranges::iterator_t<B1>>
        >
    base() const & noexcept {
        if(this->_block == 0) return std::move(this->_c0);
        else return std::move(this->_c1);
    }

    inline constexpr reference_type operator*() const noexcept(NO_EXCEPT)
    {

        if(this->_block == 0) return *this->_c0;
        else return *this->_c1;
    }

    inline constexpr iterator& operator++() noexcept(NO_EXCEPT)
    {
        assert(this->_c0 != this->_e0 or this->_c1 != this->_e1);

        if(this->_block == 0) {
            if(++this->_c0 == this->_e0) {
                this->_block = 1;
                assert(this->_c1 == this->_b1);
            }
        }
        else {
            ++this->_c1;
        }

        return *this;
    }

    inline constexpr void operator++(int) noexcept(NO_EXCEPT) { ++*this; }

    inline constexpr iterator operator++(int) noexcept(NO_EXCEPT)
        requires std::ranges::forward_range<B0> && std::ranges::forward_range<B1>
    {
        const auto res = *this; ++*this; return res;
    }

    inline constexpr iterator& operator--() noexcept(NO_EXCEPT)
        requires
            std::ranges::bidirectional_range<B0> && std::ranges::bidirectional_range<B1> &&
            std::bidirectional_iterator<std::ranges::sentinel_t<B0>>
    {
        if(this->_block == 1) {
            if(this->_c1 == this->_b1) {
                this->_block = 0;
                this->_c0 = std::ranges::prev(this->_e0);
            }
            else {
                --this->_c1;
            }
        }
        else {
            --this->_c0;
        }

        return *this;
    }

    inline constexpr iterator operator--(int) noexcept(NO_EXCEPT)
        requires std::ranges::bidirectional_range<B0> && std::ranges::bidirectional_range<B1>
    {
        const auto res = *this; --*this; return res;
    }

    inline constexpr iterator& operator+=(const difference_type diff) noexcept(NO_EXCEPT)
        requires
            std::ranges::random_access_range<B0> && std::ranges::random_access_range<B1>
    {
        if(diff > 0) {
            if(this->_block == 0) {
                const auto missing = std::ranges::advance(this->_c0, diff, this->_e0);
                if(this->_c0 == this->_e0) {
                    this->_block = 1;
                    assert(this->_c1 == this->_b1);
                    std::ranges::advance(this->_c1, missing, this->_e1);
                }
            }
            else {
                std::ranges::advance(this->_c1, diff, this->_e1);
            }
        }
        if(diff < 0) {
            if(this->_block == 1) {
                const auto missing = std::ranges::advance(this->_c1, diff, this->_b1);
                if(missing < 0) {
                    this->_block = 0;
                    assert(this->_c0 == this->_e0);
                    std::ranges::advance(this->_c0, missing, this->_b0);
                }
            }
            else {
                std::ranges::advance(this->_c0, diff, this->_b0);
            }
        }

        return *this;
    }

    inline constexpr iterator& operator-=(const difference_type diff) noexcept(NO_EXCEPT)
        requires std::ranges::random_access_range<B0> && std::ranges::random_access_range<B1>
    {
        return *this += -diff;
    }

    inline constexpr decltype(auto) operator[](const difference_type diff) const noexcept(NO_EXCEPT)
        requires std::ranges::random_access_range<B0> && std::ranges::random_access_range<B1>
    {
        return *(*this + diff);
    }

    friend inline constexpr bool operator==(const iterator& lhs, std::default_sentinel_t) noexcept(NO_EXCEPT)
    {
        if(lhs._block == 0) return false;
        if(lhs._block == 1) return lhs._c1 == lhs._e1;
        assert(false);
    }

    friend inline constexpr bool operator==(const iterator& lhs, const iterator& rhs) noexcept(NO_EXCEPT)
        requires
            std::equality_comparable<std::ranges::iterator_t<B0>> &&
            std::equality_comparable<std::ranges::iterator_t<B1>>
    {
        if(lhs._block != rhs._block) return false;
        return lhs._block == 0 ? lhs._c0 == rhs._c0 : lhs._c1 == rhs._c1;
    }

    friend inline constexpr auto operator<=>(const iterator& lhs, const iterator& rhs) noexcept(NO_EXCEPT)
        requires std::ranges::random_access_range<B0> && std::ranges::random_access_range<B1>
    {
        if(lhs._block != rhs._block) return lhs._block <=> rhs._block;
        return lhs._block == 0 ? lhs._c0 <=> rhs._c0 : lhs._c1 <=> rhs._c1;
    }

    friend inline constexpr iterator operator+(const iterator& itr, const difference_type diff) noexcept(NO_EXCEPT)
        requires std::ranges::random_access_range<B0> && std::ranges::random_access_range<B1>
    {
        auto res = itr; res += diff; return res;
    }

    friend inline constexpr iterator operator+(const difference_type diff, const iterator& itr) noexcept(NO_EXCEPT)
        requires std::ranges::random_access_range<B0> && std::ranges::random_access_range<B1>
    {
        return itr + diff;
    }

    friend inline constexpr iterator operator-(const iterator& itr, const difference_type diff) noexcept(NO_EXCEPT)
        requires std::ranges::random_access_range<B0> && std::ranges::random_access_range<B1>
    {
        auto res = itr; res -= diff; return res;
    }

    friend inline constexpr const difference_type operator-(const iterator& lhs, const iterator& rhs) noexcept(NO_EXCEPT)
        requires
            std::sized_sentinel_for<std::ranges::iterator_t<B0>, std::ranges::iterator_t<B0>> &&
            std::sized_sentinel_for<std::ranges::iterator_t<B1>, std::ranges::iterator_t<B1>>
    {
        if(lhs._block == rhs._block) {
            return lhs._block == 0 ? std::ranges::distance(rhs._c0, lhs._c0) : std::ranges::distance(rhs._c1, lhs._c1);
        }
        if(lhs._block > rhs._block) return std::ranges::distance(rhs._c0, rhs._e0) + std::ranges::distance(lhs._b1, lhs._c1);
        if(lhs._block < rhs._block) return -(rhs - lhs);
        assert(false);
    }

    friend inline constexpr const difference_type operator-(std::default_sentinel_t, const iterator& rhs) noexcept(NO_EXCEPT)
        requires
            std::sized_sentinel_for<std::ranges::sentinel_t<B0>, std::ranges::iterator_t<B0>> &&
            std::sized_sentinel_for<std::ranges::sentinel_t<B1>, std::ranges::iterator_t<B1>>
    {
        if(rhs._block == 0) return std::ranges::distance(rhs._c0, rhs._e0) + std::ranges::distance(rhs._b1, rhs._e1);
        if(rhs._block == 1) return std::ranges::distance(rhs._c1, rhs._e1);
        assert(false);
    }

    friend inline constexpr const difference_type operator-(const iterator& lhs, std::default_sentinel_t rhs) noexcept(NO_EXCEPT)
        requires
            std::sized_sentinel_for<std::ranges::sentinel_t<B0>, std::ranges::iterator_t<B0>> &&
            std::sized_sentinel_for<std::ranges::sentinel_t<B1>, std::ranges::iterator_t<B1>>
    {
        return -(rhs - lhs);
    }

    friend inline constexpr
    std::common_reference_t<
        std::ranges::range_rvalue_reference_t<B0>,
        std::ranges::range_rvalue_reference_t<B1>
    >
    iter_move(const iterator& itr) noexcept(NO_EXCEPT)
    {
        if(itr._block == 0) return std::ranges::iter_move(itr._c0);
        if(itr._block == 1) return std::ranges::iter_move(itr._c1);
        assert(false);
    }

    friend inline constexpr void iter_swap(const iterator& lhs, const iterator& rhs) noexcept(NO_EXCEPT)
        requires
            std::indirectly_swappable<std::ranges::iterator_t<B0>> &&
            std::indirectly_swappable<std::ranges::iterator_t<B1>> &&
            std::indirectly_swappable<std::ranges::iterator_t<B0>, std::ranges::iterator_t<B1>>
    {
        if(lhs._block == 0 && rhs._block == 0) std::ranges::iter_swap(lhs._c0, rhs._c0);
        if(lhs._block == 0 && rhs._block == 1) std::ranges::iter_swap(lhs._c0, rhs._c1);
        if(lhs._block == 1 && rhs._block == 0) std::ranges::iter_swap(lhs._c1, rhs._c0);
        if(lhs._block == 1 && rhs._block == 1) std::ranges::iter_swap(lhs._c1, rhs._c1);
        assert(false);
    }
};


} // namespace view_impl

} // namespace internal


template<class...> struct concat_view;

template<class T>
struct concat_view<T> : std::views::all_t<T> {
    using std::views::all_t<T>::all_t;
};

template<class T0, class T1>
struct concat_view<T0, T1> : internal::view_impl::concat_view<std::views::all_t<T0>, std::views::all_t<T1>> {
    explicit concat_view(T0&& v0, T1&& v1) noexcept(NO_EXCEPT)
      : internal::view_impl::concat_view<std::views::all_t<T0>, std::views::all_t<T1>>(std::forward<T0>(v0), std::forward<T1>(v1))
    {}
};

template<class T0, class T1, class... Ts>
struct concat_view<T0, T1, Ts...> : concat_view<concat_view<T0, T1>, Ts...> {
    explicit concat_view(T0&& v0, T1&& v1, Ts&&... vs) noexcept(NO_EXCEPT)
      : concat_view<concat_view<T0, T1>, Ts...>(
            concat_view<T0, T1>(std::forward<T0>(v0), std::forward<T1>(v1)), std::forward<Ts>(vs)...
        )
    {}
};

namespace views {

namespace internal {


template<class... Ts>
concept can_concat_view = requires { concat_view<Ts...>(std::declval<Ts>()...); };


} // namespace internal


struct Concat {
    template<class... Ts>
        requires (sizeof...(Ts) == 0 || internal::can_concat_view<Ts...>)
    inline constexpr auto operator() [[nodiscard]] (Ts&&... vs) const {
        if constexpr(sizeof...(Ts) == 0) return std::views::empty<std::nullptr_t>;
        else return concat_view<std::views::all_t<Ts>...>(std::forward<Ts>(vs)...);
    }
};


inline constexpr Concat concat;


} // namespace views

} // namespace uni.


namespace std::ranges {


template<class... Views>
inline constexpr bool enable_borrowed_range<uni::concat_view<Views...>> = (enable_borrowed_range<Views> && ...);


}
#line 35 "iterable/operation.hpp"


namespace uni {


template<std::ranges::input_range R0, std::ranges::input_range R1>
    requires std::constructible_from<
        R0, std::common_type_t<std::ranges::range_size_t<R0>,std::ranges::range_size_t<R1>>
    >
R0 concat(R0&& r0, R1&& r1) noexcept(NO_EXCEPT) {
    R0 res(std::ranges::size(r0) + std::ranges::size(r1));
    std::ranges::copy(r0, std::ranges::begin(res));
    std::ranges::copy(r1, std::ranges::next(std::ranges::begin(res), std::ranges::size(r0)));
    return res;
}

template<std::ranges::input_range R, std::ranges::input_range... Rs>
R concat(R&& range, Rs&&... tails) noexcept(NO_EXCEPT) {
    return uni::concat(range, uni::concat(tails...));
}


template<std::ranges::input_range R>
    requires
        requires(R r) {
            r.erase(std::ranges::unique(ALL(r)), std::ranges::end(r));
        }
inline auto unique(R range) noexcept(NO_EXCEPT) {
    std::ranges::sort(range);
    range.erase(std::ranges::unique(ALL(range)), std::ranges::end(range));
    return range;
}


template<
    std::input_iterator I,
    std::sentinel_for<I> S,
    class T = std::iter_value_t<I>
>
T mex(I first, S last, const T& base = T()) noexcept(NO_EXCEPT) {
    std::vector<T> val(first, last);
    std::ranges::sort(val);
    {
        auto range = std::ranges::unique(val);
        val.erase(ALL(range));
    }
    val.erase(val.begin(), std::ranges::lower_bound(val, base));

    T i = 0;
    while(i < std::ranges::ssize(val) && val[i] == i + base) ++i;

    return T{i} + base;
}

template<std::ranges::input_range R>
auto mex(R&& range, const std::ranges::range_value_t<R>& base = std::ranges::range_value_t<R>()) noexcept(NO_EXCEPT) {
    return mex(ALL(range), base);
}

template<class T>
auto mex(const std::initializer_list<T> v, const T& base = T()) noexcept(NO_EXCEPT) {
    return mex(ALL(v), base);
}


template<std::input_iterator I, std::sentinel_for<I> S, class T>
inline constexpr auto gcd(I first, S last) noexcept(NO_EXCEPT) {
    T res = T{0};
    for(auto itr=first; itr!=last; ++itr) res = std::gcd(res, *itr);
    return res;
}

template<std::input_iterator I, std::sentinel_for<I> S, class T>
inline constexpr auto lcm(I first, S last) noexcept(NO_EXCEPT) {
    T res = T{1};
    for(auto itr=first; itr!=last; ++itr) res = std::lcm(res, *itr);
    return res;
}


template<std::ranges::input_range R, class T = std::ranges::range_value_t<R>>
auto mex(R&& range, const T& base) noexcept(NO_EXCEPT) {
    return mex(ALL(range), base);
}


template<std::ranges::input_range R>
auto gcd(R&& range) noexcept(NO_EXCEPT) {
    return gcd(ALL(range));
}

template<std::ranges::input_range R>
auto lcm(R&& range) noexcept(NO_EXCEPT) {
    return lcm(ALL(range));
}


template<class R, std::input_iterator I, std::sentinel_for<I> S, class D>
    requires
        requires (R r, I itr) {
            r.emplace_back(itr, itr);
        }
auto split(I first, S last, const D& delim = ' ') noexcept(NO_EXCEPT) {
    R res;

    for(auto itr=first, fnd=first; ; itr=std::ranges::next(fnd)) {
        fnd = std::find(itr, last, delim);
        res.emplace_back(itr, fnd);
        if(fnd == last) break;
    }

    return res;
}


template<class R, std::ranges::input_range V, class D>
    requires (!std::ranges::input_range<D>)
auto split(V&& v, D&& d) noexcept(NO_EXCEPT) { return split<R>(ALL(v), d); }


template<class R, std::ranges::input_range V, std::ranges::input_range Ds>
auto split(V&& v, Ds&& ds) noexcept(NO_EXCEPT) {
    R res = { v };
    ITR(d, ds) {
        R tmp;
        ITR(p, res) tmp = concat(tmp, split<R>(p, d));
        res = std::move(tmp);
    }
    return res;
}


template<class R, std::ranges::input_range V, class T>
auto split(V&& v, const std::initializer_list<T> ds) noexcept(NO_EXCEPT){
    return split<R,V>(v, std::vector<T>(ALL(ds)));
}


template<std::ranges::sized_range Source, std::ranges::sized_range Qeury>
auto find(Source&& source,  Qeury&& query) noexcept(NO_EXCEPT) {
    z_array z_arr(views::concat(query, source));
    const auto query_size = std::ranges::ssize(query);

    vector<std::ranges::iterator_t<Source>> res;
    {
        auto itr = std::ranges::begin(source);
        REP(i, query_size, std::ranges::size(z_arr)) {
            if(z_arr[i] >= query_size) res.push_back(itr);
            ++itr;
        }
    }

    return res;
}


template<
    replacement_policy POLICY,
    std::ranges::sized_range R,
    std::ranges::sized_range From,
    std::ranges::sized_range To
>
auto replaced(R&& source, From&& from, To&& to) noexcept(NO_EXCEPT) {
    std::remove_cvref_t<R> res;

    if constexpr(POLICY == replacement_policy::insert_sync) {
        const auto found = find(source, from);
        auto itr = std::ranges::begin(source);
        ITRR(fn, found) {
            std::ranges::copy(itr, fn, std::back_inserter(res));
            std::ranges::copy(ALL(to), std::back_inserter(res));
            itr = std::ranges::next(fn, std::ranges::size(from));
        }
        std::ranges::copy(itr, std::ranges::end(source), std::back_inserter(res));
    }
    else {
        res = source;
        res.resize(std::ranges::size(source) + std::ranges::size(to));

        const auto found = find(res, from);
        auto prev = std::ranges::begin(res);
        ITRR(fn, found) {
            if constexpr(POLICY == replacement_policy::overwrite_sync) {
                if(prev <= fn) prev = std::ranges::copy(to, fn);
            }
            else {
                std::ranges::copy(to, fn);
            }
        }

        res.resize(std::ranges::size(source));
    }

    return res;
}

template<
    std::ranges::sized_range R,
    std::ranges::sized_range From,
    std::ranges::sized_range To
>
inline auto replaced(R&& source, From&& from, To&& to) noexcept(NO_EXCEPT) {
    return replaced<replacement_policy::insert_sync, R, From, To>(std::forward<R>(source), std::forward<From>(from), std::forward<To>(to));
}


template<alignment ALIGNMENT, internal::resizable_range R, class T = std::ranges::range_value_t<R>>
auto align(R&& source, const internal::size_t size, const T& v = T()) noexcept(NO_EXCEPT) {
    if(std::ssize(source) >= size) return source;

    if(ALIGNMENT == alignment::left) {
        R left, right;
        left = source;
        right.resize(size - std::size(left), v);
        return R(ALL(uni::views::concat(left, right)));
    }

    if(ALIGNMENT == alignment::center) {
        R left, center, right;
        center = source;
        left.resize((size - std::size(center)) / 2, v);
        right.resize(size - std::size(center) - std::size(left), v);
        return R(ALL(uni::views::concat(left, center, right)));
    }

    if(ALIGNMENT == alignment::right) {
        R left, right;
        right = source;
        left.resize(size - std::size(right), v);
        return R(ALL(uni::views::concat(left, right)));
    }
    assert(false);
}


template<internal::resizable_range R, class T = std::ranges::range_value_t<R>>
auto ljust(R&& source, const internal::size_t size, const T& v = T()) noexcept(NO_EXCEPT) {
    return align<alignment::left>(source, size, v);
}

template<internal::resizable_range R, class T = std::ranges::range_value_t<R>>
auto cjust(R&& source, const internal::size_t size, const T& v = T()) noexcept(NO_EXCEPT) {
    return align<alignment::center>(source, size, v);
}

template<internal::resizable_range R, class T = std::ranges::range_value_t<R>>
auto rjust(R&& source, const internal::size_t size, const T& v = T()) noexcept(NO_EXCEPT) {
    return align<alignment::right>(source, size, v);
}


template<
    class Res,
    std::ranges::random_access_range Target,
    std::ranges::forward_range Order
>
    requires std::ranges::output_range<Res, std::ranges::range_value_t<Target>>
Res ordered_by(Target&& target, Order&& order) noexcept(NO_EXCEPT) {
    const auto target_size = std::ranges::ssize(target);
    const auto order_size = std::ranges::ssize(order);
    Res res(order_size);

    {
        auto res_itr = std::ranges::begin(res);
        auto order_itr = std::ranges::begin(order);
        const auto order_end = std::ranges::end(std::forward<Order>(order));

        for(; order_itr != order_end; ++res_itr, ++order_itr) {
            if constexpr(std::signed_integral<std::ranges::range_value_t<Order>>) assert(0 <= *order_itr);
            assert(*order_itr < target_size);
            *res_itr = target[*order_itr];
        }
    }

    return res;
}


template<
    std::ranges::random_access_range Target,
    std::ranges::forward_range Order
>
auto ordered_by(Target&& target, Order&& order) noexcept(NO_EXCEPT) {
    return ordered_by<std::remove_cvref_t<Target>, Target, Order>(std::forward<Target>(target), std::forward<Order>(order));
}


template<std::ranges::input_range Target, std::ranges::input_range Source>
    requires std::equality_comparable_with<std::ranges::range_value_t<Target>, std::ranges::range_value_t<Source>>
auto is_subsequence_of(Target&& target, Source&& source) noexcept(NO_EXCEPT) {
    auto target_itr = std::ranges::begin(source);
    auto source_itr = std::ranges::begin(source);

    const auto target_end = std::ranges::end(source);
    const auto source_end = std::ranges::end(source);

    for(; source_itr != source_end; ++source_itr) {
        if(*target_itr == *source_itr) ++target_itr;
    }

    return target_itr == target_end;
}


template<std::ranges::input_range Target, std::ranges::input_range Source>
    requires std::equality_comparable_with<std::ranges::range_value_t<Target>, std::ranges::range_value_t<Source>>
auto is_continuous_subsequence_of(Target&& target, Source&& source) noexcept(NO_EXCEPT) {
    auto found = find(source, target);
    return found.size() > 0;
}


} // namespace uni
#line 31 "numeric/arithmetic.hpp"


namespace uni {


template<class T>
inline constexpr T div_floor(const T& x, const T& d) noexcept(NO_EXCEPT) {
    if constexpr(std::is_integral_v<T>) {
        return x / d - (x % d && ((x < 0) ^ (d < 0)));
    }
    else {
        return std::floor(x / d);
    }
}

template<class T>
inline constexpr T div_ceil(const T& x, const T& d) noexcept(NO_EXCEPT) {
    if constexpr(std::is_integral_v<T>) {
        return div_floor(x + d - 1, d);
    }
    else {
        return std::ceil(x / d);
    }
}

template<class T>
inline constexpr T div_round(const T& x, const T& d) noexcept(NO_EXCEPT) {
    if constexpr(std::is_integral_v<T>) {
        return div_round<ld>(x, d);
    }
    else {
        return std::round(x / d);
    }
}


template<class T>
inline constexpr std::make_signed_t<T> to_signed(const T& x) noexcept(NO_EXCEPT) {
    return std::bit_cast<std::make_signed_t<T>>(x);
}

template<class T>
inline constexpr std::make_unsigned_t<T> to_unsigned(const T& x) noexcept(NO_EXCEPT) {
    return std::bit_cast<std::make_unsigned_t<T>>(x);
}


namespace internal {


template<class T>
inline constexpr auto perm(const T& n, const T& r) noexcept(NO_EXCEPT) {
    T res = 1;
    REP(i, r) res *= n - i;
    return res;
}

template<class T>
inline constexpr auto comb(const T& n, T r) noexcept(NO_EXCEPT) {
    if(n < 2 * r) r = n - r;

    T p = 1, q = 1;
    REP(i, r) p *= n - i, q *= r - i;

    return p / q;
}


} // namespace internal


template<class T0, std::common_with<T0> T1>
inline constexpr auto perm(const T0& n, const T1& r) noexcept(NO_EXCEPT) {
    assert(n >= 0), assert(r >= 0);
    using T = std::common_type_t<T0, T1>;
    if(n < r) return static_cast<T>(0);
    return internal::perm<T>(n, r);
}

template<class T0, std::common_with<T0> T1>
inline constexpr auto comb(const T0& n, const T1& r) noexcept(NO_EXCEPT) {
    assert(n >= 0), assert(r >= 0);
    using T = std::common_type_t<T0, T1>;
    if(n < r) return static_cast<T>(0);
    if(n == r) return static_cast<T>(1);
    return internal::comb<T>(n, r);
}



template<class T, class U, std::invocable<T, T> F = std::multiplies<>>
constexpr T pow(T x, U n, F mul = F(), T one = static_cast<T>(1)) noexcept(NO_EXCEPT) {
    if(n == 0) return one;
    if(n == 1 || x == one) return x;

    T res = one;

    while(true) {
        if(n & 1) res = mul(res, x);
        x = mul(x, x);
        if(n == 0) return res;
        n >>= 1;
    }

    assert(false);
}


using atcoder::pow_mod;
using atcoder::inv_mod;
using atcoder::crt;


template<class T> inline constexpr T sign(const T& x) noexcept(NO_EXCEPT) {
    if(x == 0) return 0;
    return (x > 0) ? 1 : -1;
}

template<class T, T FROM_MIN, T FROM_MAX, T TO_MIN, T TO_MAX> inline constexpr T mapping(const T x) {
    return (x - FROM_MIN) * (TO_MAX - TO_MIN) / (FROM_MAX - FROM_MIN) + TO_MIN;
}
template<class T> inline constexpr T mapping(const T x, const T from_min, const T from_max, const T to_min, const T to_max) {
    return (x - from_min) * (to_max - to_min) / (from_max - from_min) + to_min;
}

template<class... Args>
inline constexpr std::common_type_t<Args...> min(const Args&... args) noexcept(NO_EXCEPT) {
    return std::min({ static_cast<std::common_type_t<Args...>>(args)... });
}

template<class... Args>
inline constexpr std::common_type_t<Args...> max(const Args&... args) noexcept(NO_EXCEPT) {
    return std::max({ static_cast<std::common_type_t<Args...>>(args)... });
}


template<class T>
inline constexpr T gcd(const std::initializer_list<T> args) noexcept(NO_EXCEPT) {
    return gcd(ALL(args));
}

template<class... Args>
inline constexpr std::common_type_t<Args...> gcd(const Args&... args) noexcept(NO_EXCEPT) {
    return gcd({ static_cast<std::common_type_t<Args...>>(args)... });
}


template<class T>
inline constexpr T lcm(const std::initializer_list<T> args) noexcept(NO_EXCEPT) {
    return lcm(ALL(args));
}

template<class... Args>
inline constexpr std::common_type_t<Args...> lcm(const Args&... args) noexcept(NO_EXCEPT) {
    return lcm({ static_cast<std::common_type_t<Args...>>(args)... });
}


template<std::integral T0, std::integral T1>
inline constexpr std::optional<std::common_type_t<T0, T1>> add_overflow(const T0& a, const T1& b) noexcept(NO_EXCEPT) {
    std::common_type_t<T0, T1> res;
    if(__builtin_add_overflow(a, b, &res)) return {};
    return res;
}

template<std::integral T0, std::integral T1>
inline constexpr std::optional<std::common_type_t<T0, T1>> sub_overflow(const T0& a, const T1& b) noexcept(NO_EXCEPT) {
    std::common_type_t<T0, T1> res;
    if(__builtin_sub_overflow(a, b, &res)) return {};
    return res;
}

template<std::integral T0, std::integral T1>
inline constexpr std::optional<std::common_type_t<T0, T1>> mul_overflow(const T0& a, const T1& b) noexcept(NO_EXCEPT) {
    std::common_type_t<T0, T1> res;
    if(__builtin_mul_overflow(a, b, &res)) return {};
    return res;
}

template<std::integral T0, std::integral T1, std::integral Limit>
inline auto add_clamp(const T0 x, const T1 y, const Limit inf, const Limit sup) noexcept(NO_EXCEPT) {
    using Common = std::common_type_t<T0, T1, Limit>;
    const auto res = add_overflow<Common>(x, y);
    if(!res) {
        if(x < 0 && y < 0) return inf;
        if(x > 0 && y > 0) return sup;
        assert(false);
    }
    return std::clamp<Common>(*res, inf, sup);
}

template<std::integral T0, std::integral T1, std::integral Limit>
inline auto sub_clamp(const T0 x, const T1 y, const Limit inf, const Limit sup) noexcept(NO_EXCEPT) {
    using Common = std::common_type_t<T0, T1, Limit>;
    const auto res = sub_overflow<Common>(x, y);
    if(!res) {
        if(x < 0 && y > 0) return inf;
        if(x > 0 && y < 0) return sup;
        assert(false);
    }
    return std::clamp<Common>(*res, inf, sup);
}

template<std::integral T0, std::integral T1, std::integral Limit>
inline auto mul_clamp(const T0 x, const T1 y, const Limit inf, const Limit sup) noexcept(NO_EXCEPT) {
    using Common = std::common_type_t<T0, T1, Limit>;
    const auto res = mul_overflow<Common>(x, y);
    if(!res) {
        if((x > 0) xor (y > 0)) return inf;
        else return sup;
        assert(false);
    }
    return std::clamp<Common>(*res, inf, sup);
}


template<class T>
inline constexpr T sqrt_floor(const T x) noexcept(NO_EXCEPT) {
    return static_cast<T>(std::sqrt(static_cast<long double>(x)));
}

template<class T>
inline constexpr T sqrt_ceil(const T x) noexcept(NO_EXCEPT) {
    T res = sqrt_floor(x);

    if constexpr(std::is_floating_point_v<T>) {
        while(res * res < x) res += 1;
    }
    else {
        while(mul_overflow(res, res).value_or(std::numeric_limits<T>::max()) < x) ++res;
    }

    return res;
}

template<class T, std::integral K>
inline constexpr T kth_root_floor(T x, const K k) noexcept(NO_EXCEPT) {
    assert(x >= 0);
    if(std::signed_integral<K>) assert(k > 0);

    if(x <= 1 or k == 1) return x;

    constexpr auto DIGITS = std::numeric_limits<T>::digits;
    if(k >= DIGITS) return T{1};
    if(k == 2) return sqrt_floor(x);

    constexpr auto MAX = std::numeric_limits<T>::max();
    if(x == MAX) --x;

    auto pow = [&](T t, i64 p) {
        if(p == 0) return T{1};
        T res = 1;
        while(p) {
            if(p & 1) {
                res = mul_overflow(res, t).value_or(MAX);
            }
            t = mul_overflow(t, t).value_or(MAX);
            p >>= 1;
        }
        return res;
    };

    auto res = static_cast<T>(std::pow(x, std::nextafter(1 / static_cast<double>(k), 0)));
    while(pow(res + 1, k) <= x) ++res;

    return res;
}


template<std::integral T>
T inline constexpr extended_gcd(const T& a, const T& b, T& x, T& y) noexcept {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    const T d = extended_gcd(b, a%b, y, x);

    y -= a / b * x;
    return d;
};

template<std::integral T>
std::pair<T, spair<T>> inline constexpr extended_gcd(const T& a, const T& b) noexcept {
    T x, y;
    const T d = extended_gcd(a, b, x, y);
    return { d, spair<T>{ x, y } };
};


template<std::integral T>
std::optional<spair<T>> inline constexpr bezout_equation(const T& a, const T& b, const T& c) noexcept {
    if(a == 0) {
        if(b == 0) {
            if(c == 0) return spair<T>{ 0, 0 };
            else { };
        }
        if(c % b == 0) return spair<T>{ 0, c / b };
        return {};
    }

    if(b == 0) {
        const auto ans = bezout_equation(b, a, c);
        if(ans.has_value()) return swapped(ans.value());
        return {};
    }

    T x, y;
    const T gcd = extended_gcd(a, b, x, y);

    if(c % gcd != 0) return {};

    const T p = c / gcd;
    return spair<T>{ x * p, y * p };
};


} // namespace uni
#line 18 "numeric/bit.hpp"


namespace uni {


template<std::unsigned_integral T>
constexpr T multiply_high(const T x, const T y) noexcept(NO_EXCEPT) {
    constexpr int digits = std::numeric_limits<T>::digits;

    if constexpr(digits <= 16) {
        return static_cast<T>((static_cast<u32>(x) * static_cast<u32>(y)) >> digits);
    }
    else if constexpr(digits <= 32) {
        return static_cast<T>((static_cast<u64>(x) * static_cast<u64>(y)) >> digits);
    }
    else if constexpr(digits <= 64) {
        return static_cast<T>((static_cast<u128>(x) * static_cast<u128>(y)) >> digits);
    }
    else {
        constexpr int h_digits = digits / 2;
        constexpr T mask = (T{ 1 } << h_digits) - 1;

        const T xh = x >> h_digits, yh = y >> h_digits;
        const T xl = x & mask, yl = y & mask;
        const T ph = xh * yh, pl = xl * yl;

        return (((pl >> h_digits) + (xh + xl) * (yh + yl) - (ph + pl)) >> h_digits) + ph;
    }
}


template<std::unsigned_integral T>
inline constexpr int highest_bit_pos(const T v) noexcept(NO_EXCEPT) {
    return (int)std::bit_width(v) - 1; // cast to int for GCC12
}

template<std::unsigned_integral T>
inline constexpr int lowest_bit_pos(const T v) noexcept(NO_EXCEPT) {
    if(v == 0) return -1;
    return std::countr_zero(v);
}


template<std::unsigned_integral T, std::integral I = int>
__attribute__((target("bmi2")))
inline constexpr T clear_higher_bits(const T v, const I p) {
    if constexpr(std::signed_integral<I>) assert(0 <= p);

    constexpr int DIGITS = std::numeric_limits<T>::digits;
    assert(p <= DIGITS);

    if constexpr(DIGITS <= 32) return _bzhi_u32(v, static_cast<u32>(p));
    if constexpr(DIGITS <= 64) return _bzhi_u64(v, static_cast<u64>(p));
    else {
        static_assert(DIGITS <= 128);

        constexpr std::uint64_t MAX64 = std::numeric_limits<std::uint64_t>::max();

        const std::uint64_t high = v >> 64;
        const std::uint64_t low = v & MAX64;

        if(p < 64) return _bzhi_u64(low, p);
        return low | (T{_bzhi_u64(high, p - 64)} << 64);
    }
}


template<std::unsigned_integral T, std::integral I = int> constexpr T shiftl(const T, const I = 1);
template<std::unsigned_integral T, std::integral I = int> constexpr T shiftr(const T, const I = 1);

template<std::unsigned_integral T, std::integral I>
constexpr T shiftl(const T x, const I n) {
    constexpr int DIGITS = std::numeric_limits<T>::digits;
    if constexpr(std::signed_integral<I>) {
        if(n < 0) return shiftr(x, -n);
    }
    if(n >= DIGITS) return 0;
    return x << n;
}

template<std::unsigned_integral T, std::integral I>
constexpr T shiftr(const T x, const I n) {
    constexpr int DIGITS = std::numeric_limits<T>::digits;
    if constexpr(std::signed_integral<I>) {
        if(n < 0) return shiftl(x, -n);
    }
    if(n >= DIGITS) return 0;
    return x >> n;
}


template<std::unsigned_integral T, std::integral I = int>
inline constexpr bool bit(const T x, const I p) {
    if constexpr(std::signed_integral<I>) assert(0 <= p);
    assert(p < std::numeric_limits<T>::digits);

    return shiftr(x, p) & T{1};
}


template<std::unsigned_integral T, std::integral I = int>
inline constexpr auto reset_bit(const T x, const I p) {
    if constexpr(std::signed_integral<I>) assert(0 <= p);
    assert(p < std::numeric_limits<T>::digits);

    return x & ~(T{1} << p);
}


template<std::unsigned_integral T, std::integral I = int>
inline constexpr auto set_bit(const T x, const I p, const bool bit = true) {
    if constexpr(std::signed_integral<I>) assert(0 <= p);
    assert(p < std::numeric_limits<T>::digits);

    if(!bit) return reset_bit(x, p);
    return x | (T{1} << p);
}


template<std::unsigned_integral T, std::integral I = int>
inline constexpr T lower_bits(const T x, const I digits) {
    if constexpr(std::signed_integral<I>) assert(0 <= digits);
    assert(digits <= std::numeric_limits<T>::digits);

    return x & (uni::shiftl(x, digits) - 1);
}


// Thanks to: https://noshi91.github.io/Library/other/select64.cpp
constexpr int select64(const u64 x0, u32 k) {
    const u64 x1 = (x0 & UINT64_C(0x5555555555555555)) + (x0 >> 1 & UINT64_C(0x5555555555555555));
    const u64 x2 = (x1 & UINT64_C(0x3333333333333333)) + (x1 >> 2 & UINT64_C(0x3333333333333333));
    const u64 x3 = (x2 & UINT64_C(0x0F0F0F0F0F0F0F0F)) + (x2 >> 4 & UINT64_C(0x0F0F0F0F0F0F0F0F));
    const u64 x4 = (x3 & UINT64_C(0x00FF00FF00FF00FF)) + (x3 >> 8 & UINT64_C(0x00FF00FF00FF00FF));
    const u64 x5 = (x4 & UINT64_C(0x0000FFFF0000FFFF)) + (x4 >> 16 & UINT64_C(0x0000FFFF0000FFFF));

    int res = 0;

    u32 t;

    t = x5 & 0xFFFFFFFF;
    if(t <= k) k -= t, res += 32;

    t = x4 >> res & 0xFFFF;
    if(t <= k) k -= t, res += 16;

    t = x3 >> res & 0xFF;
    if(t <= k) k -= t, res += 8;

    t = x2 >> res & 0xF;
    if(t <= k) k -= t, res += 4;

    t = x1 >> res & 0x3;
    if(t <= k) k -= t, res += 2;

    t = x0 >> res & 0x1;
    if(t <= k) k -= t, res += 1;

    return res;
}


namespace internal {


template<std::unsigned_integral T>
constexpr T binary_gcd(T a, T b) noexcept(NO_EXCEPT) {
    if(!a || !b) return a | b;
    T t, s = std::countr_zero(a | b);
    a >>= std::countr_zero(a);
    do {
        b >>= std::countr_zero(b);
        if(a > b) t = a, a = b, b = t;
        b -= a;
    } while(b);
    return a << s;
}


template<std::signed_integral T>
inline constexpr T binary_gcd(const T a, const T b) noexcept(NO_EXCEPT) {
    return binary_gcd(a < 0 ? -a : a, b < 0 ? -b : b);
}


} // namespace internal


template<std::integral T0, std::integral T1>
inline constexpr auto binary_gcd(T0 v0, T1 v1) noexcept(NO_EXCEPT) {
    using common_type = std::common_type_t<T0, T1>;
    return internal::binary_gcd(static_cast<common_type>(v0), static_cast<common_type>(v1));
}


template<std::unsigned_integral T, std::unsigned_integral S>
inline constexpr bool is_subset_of(T target, S superset) noexcept(NO_EXCEPT) {
    return (target & ~superset) == 0;
}

template<std::unsigned_integral T, std::unsigned_integral S>
inline constexpr bool is_superset_of(T target, S subset) noexcept(NO_EXCEPT) {
    return (~target & subset) == 0;
}


template<std::unsigned_integral S0, std::unsigned_integral S1>
inline constexpr auto comapre_as_bitset(S0 s0, S1 s1) noexcept(NO_EXCEPT) {
    if(s0 == s1) return std::partial_ordering::equivalent;
    if(is_subset_of(s0, s1)) return std::partial_ordering::less;
    if(is_superset_of(s0, s1)) return std::partial_ordering::greater;
    return std::partial_ordering::unordered;
}


} // namespace uni
#line 24 "data_structure/fenwick_tree.hpp"

#line 2 "action/base.hpp"


#line 6 "action/base.hpp"


#line 2 "internal/dummy.hpp"


namespace uni {

namespace internal {


struct dummy {};


} // namespace internal

} // namespace uni
#line 11 "action/base.hpp"

#line 2 "algebraic/internal/concepts.hpp"


#line 6 "algebraic/internal/concepts.hpp"


#line 9 "algebraic/internal/concepts.hpp"

#line 2 "algebraic/base.hpp"


#line 6 "algebraic/base.hpp"


#line 10 "algebraic/base.hpp"


namespace uni {

namespace algebraic {


template<class Derived>
struct scalar_multipliable {
    struct identity {
        template<std::integral Scalar>
        friend inline Derived operator*(const Scalar, const Derived& val) noexcept(NO_EXCEPT) {
            return val;
        }
    };


    struct automatic {
        template<std::integral Scalar>
        friend inline Derived operator*(const Scalar k, const Derived& val) noexcept(NO_EXCEPT) {
            return uni::pow<Derived, Scalar, std::plus<Derived>>(val, k, {}, {});
        }
    };
};



template<class T>
struct base {
    using value_type = T;

  protected:
    value_type _value;

  public:
    template<class... Args>
        requires std::constructible_from<value_type, Args...>
    base(Args&&... args) noexcept(NO_EXCEPT) : _value(std::forward<Args>(args)...) {}

    inline explicit operator value_type() const noexcept(NO_EXCEPT) { return this->_value; }
    inline auto val() const noexcept(NO_EXCEPT) { return this->_value; };

    inline const value_type* operator->() const noexcept(NO_EXCEPT) { return &this->_value; };
    inline value_type* operator->() noexcept(NO_EXCEPT) { return &this->_value; };


    friend inline auto operator<=>(const base& lhs, const base& rhs) noexcept(NO_EXCEPT) {
        return lhs._value <=> rhs._value;
    };

    friend inline bool operator==(const base& lhs, const base& rhs) noexcept(NO_EXCEPT) {
        return lhs._value == rhs._value;
    }
};

struct associative {};

struct commutative {};


} // namespace algebraic

} // namespace uni
#line 11 "algebraic/internal/concepts.hpp"


namespace uni {

namespace algebraic {

namespace internal {


template<class T>
concept magma =
    uni::internal::addable<T> &&
    requires {
        typename T::value_type;
    };


template<class T>
concept associative = std::is_base_of_v<algebraic::associative, T>;

template<class T>
concept commutative = std::is_base_of_v<algebraic::commutative, T>;

template<class T>
concept invertible = uni::internal::unary_subtractable<T>;


template<class T>
concept semigroup = magma<T> && associative<T>;

template<class T>
concept monoid = semigroup<T> && std::default_initializable<T>;

template<class T>
concept group = monoid<T> && invertible<T>;


} // namespace internal

} // namespace algebraic

} // namespace uni
#line 13 "action/base.hpp"


namespace uni {

namespace actions {


template<class operation = uni::internal::dummy>
    requires algebraic::internal::monoid<operation> || std::same_as<operation, uni::internal::dummy>
struct base {
    static operation power(const operation& x, const uni::internal::size_t) noexcept(NO_EXCEPT) { return x; }
};


namespace internal {


template<class T>
concept operatable_action = algebraic::internal::magma<typename T::operand>;

template<class T>
concept effective_action =
    algebraic::internal::magma<typename T::operation> &&
    requires (const typename T::operation& f, const uni::internal::size_t length) {
        { T::power(f, length) } -> std::same_as<typename T::operation>;
    };

template<class T>
concept operand_only_action = operatable_action<T> && (!effective_action<T>);

template<class T>
concept effect_only_action = effective_action<T> && (!operatable_action<T>);

template<class T>
concept full_action =
    operatable_action<T> && effective_action<T> &&
    requires (typename T::operation f, typename T::operand v) {
        { T::mapping(f, v) } -> std::same_as<typename T::operand>;
    };

template<class T>
concept action = operatable_action<T> || effective_action<T>;


} // namespace internal

} // namespace actions

} // namespace uni
#line 27 "data_structure/fenwick_tree.hpp"


namespace uni {

namespace internal {

namespace fenwick_tree_impl {


// Thanks to: atcoder::fenwick_tree
template<algebraic::internal::monoid Operand>
struct core {
    using operand = Operand;
    using size_type = internal::size_t;

  private:
    size_type _n = 0, _bit_ceil = 0;
    std::vector<operand> _data;

    inline void _init() noexcept(NO_EXCEPT) {
        FOR(i, 1, this->_n) {
            size_type j = i + (i & -i);
            if(j <= this->_n) this->_data[j-1] = this->_data[j-1] + this->_data[i-1];
        }
    }

  public:
    core() noexcept(NO_EXCEPT) {}

    explicit core(const size_type n) noexcept(NO_EXCEPT)
      : _n(n), _bit_ceil(std::bit_ceil<std::make_unsigned_t<size_type>>(n)), _data(n, operand{})
    {}

    inline size_type size() const noexcept(NO_EXCEPT) { return this->_n; }


    template<std::input_iterator I, std::sentinel_for<I> S>
    inline void assign(I first, S last) noexcept(NO_EXCEPT) {
        if constexpr(std::sized_sentinel_for<S, I>) {
            assert(std::ranges::distance(first, last) == this->size());
        }
        for(size_type i = 0; first < last; ++i, ++first) this->_data[i] = *first;
        this->_init();
    }


    inline void add(size_type p, const operand& x) noexcept(NO_EXCEPT) {
        for(p++; p<=this->_n; p += p & -p) this->_data[p-1] = this->_data[p-1] + x;
    }

    inline void set(const size_type p, const operand& x) noexcept(NO_EXCEPT) {
        assert(this->get(p) == this->fold(p, p+1));
        this->add(p, x + -this->get(p));
    }

    inline operand fold(size_type r) const noexcept(NO_EXCEPT) {
        operand s = operand{};
        for(; r>0; r -= r & -r) s = s + this->_data[r-1];
        return s;
    }
    inline operand fold(size_type l, size_type r) const noexcept(NO_EXCEPT) {
        operand s = operand{};
        for(; l < r; r -= r & -r) s = s + this->_data[r-1];
        for(; r < l; l -= l & -l) s = s + -this->_data[l-1];
        return s;
    }

    inline operand get(size_type p) const noexcept(NO_EXCEPT) {
        return this->fold(p, p+1);
    }

    template<class F>
    inline size_type max_right(size_type l, F&& f) const noexcept(NO_EXCEPT)
        requires algebraic::internal::invertible<operand>
    {
        assert(0 <= l && l <= this->_n);
        assert(f(operand{}));
        if(l == this->_n) return this->_n;
        operand inv = -this->fold(l);
        size_type p = 0, q = this->_bit_ceil;
        for(size_type k=q; k>0; k >>= 1) {
            if(p+k <= this->_n and f(this->_data[p+k-1] + inv)) {
                inv = inv + this->_data[(p+=k)-1];
            }
        }
        return p;
    }

    template<class F> inline size_type min_left(size_type r, F&& f) const noexcept(NO_EXCEPT)
        requires algebraic::internal::invertible<operand>
    {
        assert(0 <= r && r <= this->_n);
        assert(f(operand{}));
        if(r == 0) return 0;
        operand acc = this->fold(r);
        size_type p = 0, q = std::bit_ceil<std::make_unsigned_t<size_type>>(r);
        for(size_type k=q; k>0; k >>= 1) {
            if(p+k < r and !f(acc + -this->_data[p+k-1])) {
                acc = acc + -this->_data[(p+=k)-1];
            }
        }
        if(p == 0 and f(acc)) return 0;
        return p + 1;
    }
};


} // namespace fenwick_tree_impl

} // namespace internal


template<class Value>
struct fenwick_tree : internal::unconstructible {};


template<algebraic::internal::monoid Monoid>
struct fenwick_tree<Monoid> : internal::fenwick_tree_impl::core<Monoid> {
    static_assert(algebraic::internal::commutative<Monoid>);

  private:
    using core = typename internal::fenwick_tree_impl::core<Monoid>;

    core _impl;

  public:
    using value_type = typename core::operand;
    using size_type = typename core::size_type;

  protected:
    inline size_type _positivize_index(const size_type p) const noexcept(NO_EXCEPT) {
        return p < 0 ? this->_impl.size() + p : p;
    }

  public:
    fenwick_tree() noexcept(NO_EXCEPT) : _impl() {}

    explicit fenwick_tree(const size_type n) noexcept(NO_EXCEPT) : _impl(n) {}
    explicit fenwick_tree(const size_type n, const value_type& v) noexcept(NO_EXCEPT) : _impl(n) { this->_impl.fill(v); }

    template<std::convertible_to<value_type> T>
    fenwick_tree(const std::initializer_list<T>& init_list) noexcept(NO_EXCEPT) : fenwick_tree(ALL(init_list)) {}

    template<std::input_iterator I, std::sized_sentinel_for<I> S>
    explicit fenwick_tree(I first, S last) noexcept(NO_EXCEPT)
      : fenwick_tree(static_cast<size_type>(std::ranges::distance(first, last)))
    { this->assign(first, last); }

    template<std::ranges::input_range R>
    explicit fenwick_tree(R&& range) noexcept(NO_EXCEPT) : fenwick_tree(ALL(range)) {}


    template<std::convertible_to<value_type> T>
    inline auto& assign(const std::initializer_list<T>& init_list) noexcept(NO_EXCEPT){ return this->assign(ALL(init_list)); }

    template<std::input_iterator I, std::sentinel_for<I> S>
    inline auto& assign(I first, S last) noexcept(NO_EXCEPT) {
        this->_impl.assign(first, last);
        return *this;
    }

    template<std::ranges::input_range R>
    inline auto& assign(R&& range) noexcept(NO_EXCEPT) { return this->assign(ALL(range)); }

    inline auto& fill(const value_type& v = value_type()) noexcept(NO_EXCEPT) {
        std::fill(this->data(), this->data() + this->_impl.size(), v);
        this->_init();
        return *this;
    }

    inline auto size() const noexcept(NO_EXCEPT) { return this->_impl.size(); }
    inline bool empty() const noexcept(NO_EXCEPT) { return this->_impl.size() == 0; }

    struct point_reference : internal::point_reference<fenwick_tree> {
        point_reference(fenwick_tree *const super, const size_type p) noexcept(NO_EXCEPT)
          : internal::point_reference<fenwick_tree>(super, super->_positivize_index(p))
        {
            assert(0 <= this->_pos && this->_pos < this->_super->size());
        }

        operator value_type() const noexcept(NO_EXCEPT) { return this->_super->get(this->_pos); }
        auto val() const noexcept(NO_EXCEPT) { return this->_super->get(this->_pos); }

        inline auto& operator=(const value_type& v) noexcept(NO_EXCEPT) {
            this->_super->set(this->_pos, v);
            return *this;
        }

        inline auto& operator+=(const value_type& v) noexcept(NO_EXCEPT) {
            this->_super->add(this->_pos, v);
            return *this;
        }
    };

    struct range_reference : internal::range_reference<fenwick_tree> {
        range_reference(fenwick_tree *const super, const size_type l, const size_type r) noexcept(NO_EXCEPT)
          : internal::range_reference<fenwick_tree>(super, super->_positivize_index(l), super->_positivize_index(r))
        {
            assert(0 <= this->_begin && this->_begin <= this->_end && this->_end <= this->_super->size());
        }

        inline auto fold() noexcept(NO_EXCEPT) {
            if(this->_begin == 0 and this->_end == this->_super->size()) return this->_super->fold();
            if(this->_begin == 0) return this->_super->fold(this->_end);
            return this->_super->fold(this->_begin, this->_end);
        }
    };


    inline auto& add(const size_type p, const value_type& x) noexcept(NO_EXCEPT) {
        assert(0 <= p && p < this->_impl.size());
        this->_impl.add(p, x);
         return *this;
    }

    inline auto& set(const size_type p, const value_type& x) noexcept(NO_EXCEPT)
        requires algebraic::internal::invertible<value_type>
    {
        assert(0 <= p && p < this->_impl.size());
        this->_impl.set(p, x);
         return *this;
    }

    inline value_type get(const size_type p) const noexcept(NO_EXCEPT)
        requires algebraic::internal::invertible<value_type>
    {
        assert(0 <= p && p < this->_impl.size());
        return this->_impl.get(p);
    }

    inline auto operator[](const size_type p) noexcept(NO_EXCEPT) { return point_reference(this, p); }

    inline const auto operator()(const size_type l, const size_type r) const noexcept(NO_EXCEPT) {
        return range_reference(this, l, r);
    }

    inline auto operator()(const size_type l, const size_type r) noexcept(NO_EXCEPT) {
        return range_reference(this, l, r);
    }

    inline auto fold(const size_type l, const size_type r) const noexcept(NO_EXCEPT)
        requires algebraic::internal::invertible<value_type>
    {
        assert(0 <= l && l <= r && r <= this->_impl.size());
        return this->_impl.fold(l, r);
    }

    inline auto fold(const size_type r) const noexcept(NO_EXCEPT) {
        assert(0 <= r && r <= this->_impl.size());
        return this->_impl.fold(r);
    }

    inline auto fold() const noexcept(NO_EXCEPT) {
        return this->_impl.fold(this->_impl.size());
    }

    struct iterator;

  protected:
    using iterator_interface = internal::container_iterator_interface<value_type, const fenwick_tree, iterator>;

  public:
    struct iterator : iterator_interface {
        using iterator_interface::iterator_interface;
    };

    inline auto begin() const noexcept(NO_EXCEPT) { return iterator(this, 0); }
    inline auto end() const noexcept(NO_EXCEPT) { return iterator(this, this->_impl.size()); }

    inline auto rbegin() const noexcept(NO_EXCEPT) { return std::make_reverse_iterator(this->end()); }
    inline auto rend() const noexcept(NO_EXCEPT) { return std::make_reverse_iterator(this->begin()); }
};


template<actions::internal::operatable_action Action>
struct fenwick_tree<Action> : fenwick_tree<typename Action::operand> {
    using fenwick_tree<typename Action::operand>::fenwick_tree;
};


} // namespace uni