#line 2 "include/graph_theory.hpp"
#line 2 "graph/centroid_decomposition.hpp"
#include <cassert>
#include <vector>
#include <utility>
#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 "structure/graph.hpp"
#line 5 "structure/graph.hpp"
#include <tuple>
#include <iostream>
#include <ranges>
#line 2 "snippet/internal/types.hpp"
#include <cstdint>
namespace uni {
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
#ifdef __GNUC__
using i128 = __int128_t;
using u128 = __uint128_t;
using f128 = __float128;
#endif
using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
} // namespace uni
#line 2 "snippet/iterations.hpp"
#include <type_traits>
#line 2 "macro/overload.hpp"
#define $OVERLOAD2(arg0, arg1, cmd, ...) cmd
#define $OVERLOAD3(arg0, arg1, arg2, cmd, ...) cmd
#define $OVERLOAD4(arg0, arg1, arg2, arg3, cmd, ...) cmd
#define $OVERLOAD5(arg0, arg1, arg2, arg3, arg4, cmd, ...) cmd
#define $OVERLOAD6(arg0, arg1, arg2, arg3, arg4, arg5, cmd, ...) cmd
#line 2 "macro/basic.hpp"
#define TO_STRING_AUX(x) #x
#define TO_STRING(x) TO_STRING_AUX(x)
#define CONCAT_AUX(x, y) x##y
#define CONCAT(x, y) CONCAT_AUX(x, y)
#define UNPAREN_AUX(...) __VA_ARGS__
#define UNPAREN(...) __VA_ARGS__
#line 6 "snippet/iterations.hpp"
#define LOOP(n) REPI(CONCAT(_$, __COUNTER__), n)
#define REPI(i,n) for(std::remove_cvref_t<decltype(n)> i=0, CONCAT(i, $)=(n); i<CONCAT(i, $); ++i)
#define REPF(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); ++i)
#define REPIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); i+=(s))
#define REPR(i,n) for(auto i=(n); --i>=0;)
#define REPB(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); --i>=CONCAT(i, $);)
#define REPRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l)-1)/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); (i-=(s)))
#define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__)
#define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__)
#define FORO(i,n) for(int i=0, CONCAT(i, $)=static_cast<int>(n); i<=CONCAT(i, $); ++i)
#define FORI(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); ++i)
#define FORIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); i+=(s))
#define FORRO(i,n) for(auto i=(n); i>=0; --i)
#define FORR(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); i>=CONCAT(i, $); --i)
#define FORRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l))/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); i-=(s))
#define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI, FORO)(__VA_ARGS__)
#define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR, FORRO)(__VA_ARGS__)
#define ITR1(e0,v) for(const auto &e0 : (v))
#define ITRP1(e0,v) for(auto e0 : (v))
#define ITRR1(e0,v) for(auto &e0 : (v))
#define ITR2(e0,e1,v) for(const auto [e0, e1] : (v))
#define ITRP2(e0,e1,v) for(auto [e0, e1] : (v))
#define ITRR2(e0,e1,v) for(auto &[e0, e1] : (v))
#define ITR3(e0,e1,e2,v) for(const auto [e0, e1, e2] : (v))
#define ITRP3(e0,e1,e2,v) for(auto [e0, e1, e2] : (v))
#define ITRR3(e0,e1,e2,v) for(auto &[e0, e1, e2] : (v))
#define ITR4(e0,e1,e2,e3,v) for(const auto [e0, e1, e2, e3] : (v))
#define ITRP4(e0,e1,e2,e3,v) for(auto [e0, e1, e2, e3] : (v))
#define ITRR4(e0,e1,e2,e3,v) for(auto &[e0, e1, e2, e3] : (v))
#define ITR5(e0,e1,e2,e3,e4,v) for(const auto [e0, e1, e2, e3, e4] : (v))
#define ITRP5(e0,e1,e2,e3,e4,v) for(auto [e0, e1, e2, e3, e4] : (v))
#define ITRR5(e0,e1,e2,e3,e4,v) for(auto &[e0, e1, e2, e3, e4] : (v))
#define ITR(...) $OVERLOAD6(__VA_ARGS__, ITR5, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__)
#define ITRP(...) $OVERLOAD6(__VA_ARGS__, ITRP5, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__)
#define ITRR(...) $OVERLOAD6(__VA_ARGS__, ITRR5, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__)
#line 12 "structure/graph.hpp"
#line 2 "internal/types.hpp"
#line 4 "internal/types.hpp"
namespace uni {
namespace internal {
using size_t = std::int64_t;
using int128_t = __int128_t;
using uint128_t = __uint128_t;
} // namesapce internal
} // namespace uni
#line 2 "internal/concepts.hpp"
#line 5 "internal/concepts.hpp"
#include <concepts>
#line 7 "internal/concepts.hpp"
#include <limits>
#include <functional>
namespace uni {
namespace internal {
template<class R, class T>
concept convertibel_range = std::convertible_to<std::ranges::range_value_t<R>, T>;
template<class T, class V>
concept item_or_convertible_range = std::convertible_to<T, V> || convertibel_range<T, V>;
template<class Structure>
concept available =
requires () {
typename Structure;
};
template<
template<class...> class Structure,
class... TemplateParameters
>
concept available_with = available<Structure<TemplateParameters...>>;
template<class T> concept arithmetic = std::is_arithmetic_v<T>;
template<class T> concept pointer = std::is_pointer_v<T>;
template<class T> concept structural = std::is_class_v<T>;
template<class Large, class Small>
concept has_double_digits_of = (std::numeric_limits<Large>::digits == 2 * std::numeric_limits<Small>::digits);
template<class Large, class Small>
concept has_more_digits_than = (std::numeric_limits<Large>::digits > std::numeric_limits<Small>::digits);
template<class Large, class Small>
concept has_or_more_digits_than = (std::numeric_limits<Large>::digits >= std::numeric_limits<Small>::digits);
template<class T>
concept has_static_zero = requires { T::zero; };
template<class T>
concept has_static_one = requires { T::one; };
template<class L, class R = L>
concept weakly_bitand_calcurable = requires (L lhs, R rhs) { lhs & rhs; };
template<class L, class R = L>
concept weakly_bitor_calcurable = requires (L lhs, R rhs) { lhs | rhs; };
template<class L, class R = L>
concept weakly_bitxor_calcurable = requires (L lhs, R rhs) { lhs ^ rhs; };
template<class L, class R = L>
concept weakly_addable = requires (L lhs, R rhs) { lhs + rhs; };
template<class L, class R = L>
concept weakly_subtractable = requires (L lhs, R rhs) { lhs - rhs; };
template<class L, class R = L>
concept weakly_multipliable = requires (L lhs, R rhs) { lhs * rhs; };
template<class L, class R = L>
concept weakly_divisable = requires (L lhs, R rhs) { lhs / rhs; };
template<class L, class R = L>
concept weakly_remainder_calculable = requires (L lhs, R rhs) { lhs % rhs; };
template<class L, class R = L>
concept weakly_bitand_assignable = requires (L lhs, R rhs) { lhs += rhs; };
template<class L, class R = L>
concept weakly_bitor_assignable = requires (L lhs, R rhs) { lhs |= rhs; };
template<class L, class R = L>
concept weakly_bitxor_assignable = requires (L lhs, R rhs) { lhs ^= rhs; };
template<class L, class R = L>
concept weakly_addition_assignable = requires (L lhs, R rhs) { lhs += rhs; };
template<class L, class R = L>
concept weakly_subtraction_assignable = requires (L lhs, R rhs) { lhs -= rhs; };
template<class L, class R = L>
concept weakly_multipliation_assignalbe = requires (L lhs, R rhs) { lhs *= rhs; };
template<class L, class R = L>
concept weakly_division_assignable = requires (L lhs, R rhs) { lhs /= rhs; };
template<class L, class R = L>
concept weakly_remainder_assignable = requires (L lhs, R rhs) { lhs /= rhs; };
template<class L, class R = L>
concept bitand_calculable =
weakly_bitand_calcurable<L, R> &&
weakly_bitand_calcurable<std::invoke_result_t<std::bit_and<>&, L, R>, R> &&
weakly_bitand_calcurable<L, std::invoke_result_t<std::bit_and<>&, L, R>> &&
weakly_bitand_calcurable<std::invoke_result_t<std::bit_and<>&, L, R>, std::invoke_result_t<std::bit_and<>&, L, R>>;
template<class L, class R = L>
concept bitor_calculable =
weakly_bitor_calcurable<L, R> &&
weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, R> &&
weakly_bitor_calcurable<L, std::invoke_result_t<std::bit_or<>&, L, R>> &&
weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, std::invoke_result_t<std::bit_or<>&, L, R>>;
template<class L, class R = L>
concept bitxor_calculable =
weakly_bitxor_calcurable<L, R> &&
weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, R> &&
weakly_bitxor_calcurable<L, std::invoke_result_t<std::bit_xor<>&, L, R>> &&
weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, std::invoke_result_t<std::bit_xor<>&, L, R>>;
template<class L, class R = L>
concept addable =
weakly_addable<L, R> &&
weakly_addable<std::invoke_result_t<std::plus<>&, L, R>, R> &&
weakly_addable<L, std::invoke_result_t<std::plus<>&, L, R>> &&
weakly_addable<std::invoke_result_t<std::plus<>&, L, R>, std::invoke_result_t<std::plus<>&, L, R>>;
template<class L, class R = L>
concept subtractable =
weakly_subtractable<L, R> &&
weakly_subtractable<std::invoke_result_t<std::minus<>&, L, R>, R> &&
weakly_subtractable<L, std::invoke_result_t<std::minus<>&, L, R>> &&
weakly_subtractable<std::invoke_result_t<std::minus<>&, L, R>, std::invoke_result_t<std::minus<>&, L, R>>;
template<class L, class R = L>
concept multipliable =
weakly_multipliable<L, R> &&
weakly_multipliable<std::invoke_result_t<std::multiplies<>&, L, R>, R> &&
weakly_multipliable<L, std::invoke_result_t<std::multiplies<>&, L, R>> &&
weakly_multipliable<std::invoke_result_t<std::multiplies<>&, L, R>, std::invoke_result_t<std::multiplies<>&, L, R>>;
template<class L, class R = L>
concept divisable =
weakly_divisable<L, R> &&
weakly_divisable<std::invoke_result_t<std::divides<>&, L, R>, R> &&
weakly_divisable<L, std::invoke_result_t<std::divides<>&, L, R>> &&
weakly_divisable<std::invoke_result_t<std::divides<>&, L, R>, std::invoke_result_t<std::divides<>&, L, R>>;
template<class L, class R = L>
concept remainder_calculable =
weakly_remainder_calculable<L, R> &&
weakly_remainder_calculable<std::invoke_result_t<std::modulus<>&, L, R>, R> &&
weakly_remainder_calculable<L, std::invoke_result_t<std::modulus<>&, L, R>> &&
weakly_remainder_calculable<std::invoke_result_t<std::modulus<>&, L, R>, std::invoke_result_t<std::modulus<>&, L, R>>;
template<class L, class R = L>
concept bitand_assignable =
weakly_bitand_assignable<L, R> &&
weakly_bitand_assignable<std::invoke_result_t<std::bit_and<>&, L, R>, R> &&
weakly_bitand_assignable<L, std::invoke_result_t<std::bit_and<>&, L, R>> &&
weakly_bitand_assignable<std::invoke_result_t<std::bit_and<>&, L, R>, std::invoke_result_t<std::bit_and<>&, L, R>>;
template<class L, class R = L>
concept bitor_assignable =
weakly_bitor_calcurable<L, R> &&
weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, R> &&
weakly_bitor_calcurable<L, std::invoke_result_t<std::bit_or<>&, L, R>> &&
weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, std::invoke_result_t<std::bit_or<>&, L, R>>;
template<class L, class R = L>
concept bitxor_assignable =
weakly_bitxor_calcurable<L, R> &&
weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, R> &&
weakly_bitxor_calcurable<L, std::invoke_result_t<std::bit_xor<>&, L, R>> &&
weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, std::invoke_result_t<std::bit_xor<>&, L, R>>;
template<class L, class R = L>
concept addition_assignable =
weakly_addition_assignable<L, R> &&
weakly_addition_assignable<std::remove_cvref_t<std::invoke_result_t<std::plus<>&, L, R>>, R> &&
weakly_addition_assignable<L, std::invoke_result_t<std::plus<>&, L, R>> &&
weakly_addition_assignable<std::remove_cvref_t<std::invoke_result_t<std::plus<>&, L, R>>, std::invoke_result_t<std::plus<>&, L, R>>;
template<class L, class R = L>
concept subtraction_assignable =
weakly_subtraction_assignable<L, R> &&
weakly_subtraction_assignable<std::remove_cvref_t<std::invoke_result_t<std::minus<>&, L, R>>, R> &&
weakly_subtraction_assignable<L, std::invoke_result_t<std::minus<>&, L, R>> &&
weakly_subtraction_assignable<std::remove_cvref_t<std::invoke_result_t<std::minus<>&, L, R>>, std::invoke_result_t<std::minus<>&, L, R>>;
template<class L, class R = L>
concept multipliation_assignalbe =
weakly_multipliation_assignalbe<L, R> &&
weakly_multipliation_assignalbe<std::remove_cvref_t<std::invoke_result_t<std::multiplies<>&, L, R>>, R> &&
weakly_multipliation_assignalbe<L, std::invoke_result_t<std::multiplies<>&, L, R>> &&
weakly_multipliation_assignalbe<std::remove_cvref_t<std::invoke_result_t<std::multiplies<>&, L, R>>, std::invoke_result_t<std::multiplies<>&, L, R>>;
template<class L, class R = L>
concept division_assignable =
weakly_division_assignable<L, R> &&
weakly_division_assignable<std::remove_cvref_t<std::invoke_result_t<std::divides<>&, L, R>>, R> &&
weakly_division_assignable<L, std::invoke_result_t<std::divides<>&, L, R>> &&
weakly_division_assignable<std::remove_cvref_t<std::invoke_result_t<std::divides<>&, L, R>>, std::invoke_result_t<std::divides<>&, L, R>>;
template<class L, class R = L>
concept remainder_assignable =
weakly_remainder_assignable<L, R> &&
weakly_remainder_assignable<std::remove_cvref_t<std::invoke_result_t<std::modulus<>&, L, R>>, R> &&
weakly_remainder_assignable<L, std::invoke_result_t<std::modulus<>&, L, R>> &&
weakly_remainder_assignable<std::remove_cvref_t<std::invoke_result_t<std::modulus<>&, L, R>>, std::invoke_result_t<std::modulus<>&, L, R>>;
template<class T>
concept weakly_incrementable =
std::movable<T> &&
requires (T v) {
{ ++v } -> std::same_as<T&>;
v++;
};
template<class T>
concept weakly_decrementable =
std::movable<T> &&
requires (T v) {
{ --v } -> std::same_as<T&>;
v--;
};
template<class T>
concept incrementable =
std::regular<T> &&
weakly_incrementable<T> &&
requires (T v) {
{ v++ } -> std::same_as<T>;
};
template<class T>
concept decrementable =
std::regular<T> &&
weakly_decrementable<T> &&
requires (T v) {
{ v-- } -> std::same_as<T>;
};
template<class L, class R = L>
concept weakly_arithmetic_operable =
weakly_addable<L, R> &&
weakly_subtractable<L, R> &&
weakly_multipliable<L, R> &&
weakly_divisable<L, R>;
template<class L, class R = L>
concept weakly_arithmetic_operation_assignable =
weakly_addition_assignable<L, R> &&
weakly_subtraction_assignable<L, R> &&
weakly_multipliation_assignalbe<L, R> &&
weakly_division_assignable<L, R>;
template<class L, class R = L>
concept arithmetic_operable =
weakly_arithmetic_operable<L, R> &&
addable<L, R> &&
subtractable<L, R> &&
multipliable<L, R> &&
divisable<L, R>;
template<class L, class R = L>
concept arithmetic_operation_assignable =
weakly_arithmetic_operation_assignable<L, R> &&
addition_assignable<L, R> &&
subtraction_assignable<L, R> &&
multipliation_assignalbe<L, R> &&
division_assignable<L, R>;
template<class T>
concept unary_addable =
requires (T v) {
{ +v } -> std::same_as<T>;
};
template<class T>
concept unary_subtractable =
requires (T v) {
{ -v } -> std::same_as<T>;
};
template<class T>
concept numeric =
std::regular<T> &&
arithmetic_operable<T> &&
arithmetic_operation_assignable<T> &&
weakly_incrementable<T> &&
unary_addable<T> &&
unary_subtractable<T>;
} // namespace internal
} // namespace uni
#line 16 "structure/graph.hpp"
#line 2 "utility/functional.hpp"
#line 7 "utility/functional.hpp"
#include <optional>
#line 2 "internal/type_traits.hpp"
#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 11 "utility/functional.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 13 "utility/functional.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 "numeric/arithmetic.hpp"
#line 5 "numeric/arithmetic.hpp"
#include <cstring>
#line 7 "numeric/arithmetic.hpp"
#include <string>
#line 13 "numeric/arithmetic.hpp"
#include <bit>
#include <atcoder/math>
#line 2 "snippet/aliases.hpp"
#line 8 "snippet/aliases.hpp"
#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 21 "numeric/arithmetic.hpp"
#line 25 "numeric/arithmetic.hpp"
#line 27 "numeric/arithmetic.hpp"
#line 2 "numeric/internal/number_base.hpp"
#line 5 "numeric/internal/number_base.hpp"
#include <cstddef>
#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 "iterable/internal/operation_base.hpp"
#line 5 "iterable/internal/operation_base.hpp"
#include <iterator>
#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/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 2 "internal/iterator.hpp"
#line 7 "internal/iterator.hpp"
#include <variant>
#include <compare>
#line 10 "internal/iterator.hpp"
#line 13 "internal/iterator.hpp"
#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/ranges.hpp"
#line 7 "internal/ranges.hpp"
#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 2 "global/constants.hpp"
#line 7 "global/constants.hpp"
#include <cmath>
#line 11 "global/constants.hpp"
#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 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 16 "utility/functional.hpp"
#line 18 "utility/functional.hpp"
namespace uni {
namespace internal {
template<class T> constexpr T plus(const T a, const T b) noexcept(NO_EXCEPT) { return std::plus<T>{}(a, b); }
template<class T> constexpr T minus(const T a, const T b) noexcept(NO_EXCEPT) { return std::minus<T>{}(a, b); }
template<class T> constexpr T bit_xor(const T a, const T b) noexcept(NO_EXCEPT) { return a xor b; }
} // namespace internal
template<class T, class U> inline auto to_optional_if_equal(const T& v, const U& ill) noexcept(NO_EXCEPT) -> std::optional<T> {
return v == ill ? std::optional<T>{} : std::optional<T>(v);
}
template<class T, class U> inline auto to_optional_if_over(const T& v, const U& ill) noexcept(NO_EXCEPT) -> std::optional<T> {
return v > ill ? std::optional<T>{} : std::optional<T>(v);
}
template<class T, class U> inline auto to_optional_if_or_over(const T& v, const U& ill) noexcept(NO_EXCEPT) -> std::optional<T> {
return v >= ill ? std::optional<T>{} : std::optional<T>(v);
}
template<class T, class U> inline auto to_optional_if_under(const T& v, const U& ill) noexcept(NO_EXCEPT) -> std::optional<T> {
return v < ill ? std::optional<T>{} : std::optional<T>(v);
}
template<class T, class U> inline auto to_optional_if_or_under(const T& v, const U& ill) noexcept(NO_EXCEPT) -> std::optional<T> {
return v <= ill ? std::optional<T>{} : std::optional<T>(v);
}
template<class T, class F> inline auto to_optional_if(const T& v, F&& f) noexcept(NO_EXCEPT) -> decltype(f(v), std::optional<T>{}){
return f(v) ? std::optional<T>{} : std::optional<T>(v);
}
template<class T, class U> inline bool chmin(T &a, const U& b) noexcept(NO_EXCEPT) { return (a>b ? a=b, true : false); }
template<class T, class U> inline bool chmax(T &a, const U& b) noexcept(NO_EXCEPT) { return (a<b ? a=b, true : false); }
template<class T, class... Ts> inline bool chmin(T &a, Ts... b) noexcept(NO_EXCEPT) { return chmin(a, min(b...)); }
template<class T, class... Ts> inline bool chmax(T &a, Ts... b) noexcept(NO_EXCEPT) { return chmax(a, max(b...)); }
template<class... Ts>
inline constexpr std::common_type_t<Ts...> tuple_sum(const std::tuple<Ts...>& tuple, const std::common_type_t<Ts...>& base = std::common_type_t<Ts...>()) noexcept(NO_EXCEPT) {
std::common_type_t<Ts...> res = base;
tuple_for_each(tuple, [&](const auto& v) constexpr { res += v; });
return res;
}
template<class... Ts>
inline constexpr std::common_type_t<Ts...> min_element(const std::tuple<Ts...>& tuple) noexcept(NO_EXCEPT) {
return std::apply([&](auto&&... v) constexpr { return min(v...); }, tuple);
}
template<class... Ts>
inline constexpr std::common_type_t<Ts...> max_element(const std::tuple<Ts...>& tuple) noexcept(NO_EXCEPT) {;
return std::apply([&](auto&&... v) constexpr { return max(v...); }, tuple);
}
template<interval_notation INTERVAL, class T0, class T1, class T2>
inline constexpr bool in_range(const T0& x, const T1& l, const T2& r) noexcept(NO_EXCEPT) {
if constexpr(INTERVAL == interval_notation::right_open) return l <= x and x < r;
else if constexpr(INTERVAL == interval_notation::left_open) return l < x and x <= r;
else if constexpr(INTERVAL == interval_notation::open) return l < x and x < r;
return l <= x and x <= r;
}
template<class F, class Tuple>
constexpr void tuple_for_each(F&& f, Tuple&& tuple) {
std::apply(
[&]<class... Ts>(Ts&&... elems) {
(std::invoke(f, std::forward<Ts>(elems)), ...);
},
std::forward<Tuple>(tuple)
);
}
template<class F, class Tuple>
constexpr auto tuple_transform(F&& f, Tuple&& tuple) {
return std::apply(
[&]<class...Ts>(Ts&&... elems) {
return internal::tuple_or_pair_t<std::invoke_result_t<F&,Ts>...>(
std::invoke(f, std::forward<Ts>(elems))...
);
},
std::forward<Tuple>(tuple)
);
}
} // namespace uni
#line 2 "adaptor/io.hpp"
#include <regex>
#line 2 "adaptor/internal/input.hpp"
#line 12 "adaptor/internal/input.hpp"
#line 15 "adaptor/internal/input.hpp"
#line 2 "internal/resolving_rank.hpp"
namespace uni {
namespace internal {
template<int P> struct resolving_rank : resolving_rank<P-1> {};
template<> struct resolving_rank<0> {};
} // namespace internal
} // namespace uni
#line 18 "adaptor/internal/input.hpp"
#line 20 "adaptor/internal/input.hpp"
#line 2 "numeric/modular/modint_interface.hpp"
#line 6 "numeric/modular/modint_interface.hpp"
#line 9 "numeric/modular/modint_interface.hpp"
#line 11 "numeric/modular/modint_interface.hpp"
#line 2 "numeric/modular/builtin_reduction.hpp"
#line 5 "numeric/modular/builtin_reduction.hpp"
#line 8 "numeric/modular/builtin_reduction.hpp"
#line 10 "numeric/modular/builtin_reduction.hpp"
#line 12 "numeric/modular/builtin_reduction.hpp"
namespace uni {
namespace internal {
template<std::unsigned_integral Value, std::unsigned_integral Large>
requires has_double_digits_of<Large, Value>
struct builtin_reduction {
using value_type = Value;
using large_type = Large;
private:
value_type _mod;
public:
static constexpr int digits = std::numeric_limits<value_type>::digits;
static constexpr value_type max() noexcept { return std::numeric_limits<value_type>::max(); }
inline constexpr value_type mod() const noexcept(NO_EXCEPT) { return this->_mod; }
constexpr builtin_reduction() noexcept = default;
constexpr builtin_reduction(const value_type mod) noexcept(NO_EXCEPT) : _mod(mod) {
assert(0 < mod && mod < builtin_reduction::max());
}
inline constexpr value_type reduce(const large_type v) const noexcept(NO_EXCEPT) { return v % this->_mod; }
inline constexpr value_type add(value_type x, const value_type y) const noexcept(NO_EXCEPT) {
if(x >= this->_mod - y) x -= this->_mod;
x += y;
return x;
}
inline constexpr value_type subtract(value_type x, const value_type y) const noexcept(NO_EXCEPT) {
if(x < y) x += this->_mod;
x -= y;
return x;
}
inline constexpr value_type multiply(const value_type x, const value_type y) const noexcept(NO_EXCEPT) {
return this->reduce(static_cast<large_type>(x) * static_cast<large_type>(y));
}
template<std::integral K>
inline constexpr value_type pow(const value_type v, const K p) const noexcept(NO_EXCEPT) {
if constexpr(std::signed_integral<K>) assert(p >= 0);
if(this->_mod == 0) return 0;
return uni::pow(v, p, [this](const value_type x, const value_type y) { return this->multiply(x, y); });
}
inline constexpr auto compare(const value_type x, const value_type y) const noexcept(NO_EXCEPT) {
return x <=> y;
}
constexpr value_type convert_raw(const value_type v) const noexcept(NO_EXCEPT) { return v; }
template<std::integral T>
constexpr value_type convert(T v) const noexcept(NO_EXCEPT) {
using common_type = std::common_type_t<T, value_type>;
const common_type mod = static_cast<common_type>(this->_mod);
if(std::is_constant_evaluated()) {
v %= mod;
if constexpr(std::signed_integral<T>) {
if(v < 0) v += mod;
}
}
else {
if(v > 0 && static_cast<common_type>(v) >= mod) {
v %= mod;
}
if constexpr(std::signed_integral<T>) {
if(v < 0) {
if(static_cast<common_type>(-v) <= mod) v += mod;
else {
v %= mod;
if(v != 0) v += mod;
}
}
}
}
return static_cast<value_type>(v);
}
constexpr value_type revert(const value_type v) const noexcept(NO_EXCEPT) { return this->_mod == 1 ? 0 : v; }
};
} // namespace internal
using builtin_reduction_32bit = internal::builtin_reduction<u32, u64>;
using builtin_reduction_64bit = internal::builtin_reduction<u64, u128>;
} // namespace uni
#line 2 "numeric/modular/binary_reduction.hpp"
#line 7 "numeric/modular/binary_reduction.hpp"
#line 10 "numeric/modular/binary_reduction.hpp"
#line 13 "numeric/modular/binary_reduction.hpp"
#line 2 "numeric/bit.hpp"
#include <immintrin.h>
#line 13 "numeric/bit.hpp"
#line 16 "numeric/bit.hpp"
#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 16 "numeric/modular/binary_reduction.hpp"
namespace uni {
namespace internal {
template<std::unsigned_integral Value>
struct binary_reduction {
using value_type = Value;
private:
value_type _mask;
public:
static constexpr int digits = std::numeric_limits<value_type>::digits;
static constexpr value_type max() noexcept { return std::numeric_limits<value_type>::max(); }
inline constexpr value_type mod() const noexcept(NO_EXCEPT) { return this->_mask + 1; }
constexpr binary_reduction() noexcept = default;
constexpr explicit inline binary_reduction(const value_type mod) noexcept(NO_EXCEPT) : _mask(mod - 1) {
assert(std::has_single_bit(mod));
}
inline constexpr value_type reduce(const value_type v) const noexcept(NO_EXCEPT) { return v; }
inline constexpr value_type add(const value_type x, const value_type y) const noexcept(NO_EXCEPT) {
return x + y;
}
inline constexpr value_type subtract(const value_type x, const value_type y) const noexcept(NO_EXCEPT) {
return x - y;
}
inline constexpr value_type multiply(const value_type x, const value_type y) const noexcept(NO_EXCEPT) {
return x * y;
}
template<std::integral K>
inline constexpr value_type pow(const value_type v, const K p) const noexcept(NO_EXCEPT) {
if constexpr(std::signed_integral<K>) assert(p >= 0);
if(this->_mask == 0) return 0;
return uni::pow(v, p);
}
inline constexpr auto compare(const value_type x, const value_type y) const noexcept(NO_EXCEPT) {
return this->revert(x) <=> this->revert(y);
}
constexpr value_type convert_raw(const value_type v) const noexcept(NO_EXCEPT) {
return v;
}
template<std::integral T>
constexpr value_type convert(T v) const noexcept(NO_EXCEPT) {
return static_cast<value_type>(v);
}
constexpr value_type revert(const value_type v) const noexcept(NO_EXCEPT) {
return v & this->_mask;
}
};
} // namespace internal
using binary_reduction_32bit = internal::binary_reduction<u32>;
using binary_reduction_64bit = internal::binary_reduction<u64>;
using binary_reduction_128bit = internal::binary_reduction<u128>;
} // namespace uni
#line 2 "numeric/modular/barrett_reduction.hpp"
#line 8 "numeric/modular/barrett_reduction.hpp"
#line 11 "numeric/modular/barrett_reduction.hpp"
#line 14 "numeric/modular/barrett_reduction.hpp"
#line 2 "template/debug.hpp"
#ifdef LOCAL_JUDGE
#define DEBUGGER_ENABLED
#define DEBUGGER_COLORED_OUTPUT 1
#endif
#line 2 "debugger/debug.hpp"
#line 9 "debugger/debug.hpp"
#include <array>
#line 13 "debugger/debug.hpp"
#include <bitset>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#line 22 "debugger/debug.hpp"
#include <iomanip>
#line 26 "debugger/debug.hpp"
#line 2 "numeric/int128.hpp"
#include <cctype>
#line 9 "numeric/int128.hpp"
#line 12 "numeric/int128.hpp"
#line 14 "numeric/int128.hpp"
namespace std {
template<class C, class S>
auto& operator>>(std::basic_istream<C, S>& in, uni::i128& v) noexcept(NO_EXCEPT) {
std::string str; in >> str;
v = 0;
bool negative = (str[0] == '-');
REP(d, std::ranges::next(str.begin(), negative), str.end()) {
assert(std::isdigit(*d));
v = v * 10 + *d - '0';
}
if(negative) v *= -1;
return in;
}
template<class C, class S>
auto& operator>>(std::basic_istream<C, S>& in, uni::u128& v) noexcept(NO_EXCEPT) {
std::string str; in >> str;
v = 0U;
assert(str[0] != '-');
REP(d, str.begin(), str.end()) {
assert(std::isdigit(*d));
v = v * 10U + *d - '0';
}
return in;
}
template<class C, class S>
auto& operator<<(std::basic_ostream<C, S>& out, uni::i128 v) noexcept(NO_EXCEPT) {
if(v == 0) return out << 0;
if(v < 0) out << '-', v *= -1;
std::string str;
while(v > 0) str += static_cast<char>(v%10) + '0', v /= 10;
std::reverse(str.begin(), str.end());
return out << str;
}
template<class C, class S>
auto& operator<<(std::basic_ostream<C, S>& out, uni::u128 v) noexcept(NO_EXCEPT) {
if(v == 0) return out << 0U;
std::string str;
while(v > 0) str += static_cast<char>(v%10U) + '0', v /= 10U;
std::reverse(str.begin(), str.end());
return out << str;
}
}
#line 29 "debugger/debug.hpp"
#line 34 "debugger/debug.hpp"
#include <typeinfo>
#include <cxxabi.h>
namespace debugger {
template<class T>
auto _debug (T&& val) -> decltype(val._debug()) {
return val._debug();
}
std::ostream *cdebug = &std::clog;
#ifdef DEBUGGER_COLORED_OUTPUT
constexpr std::string COLOR_LINE = "\033[3;35m";
constexpr std::string COLOR_IDENTIFIER = "\033[32m";
constexpr std::string COLOR_INIT = "\033[m";
constexpr std::string COLOR_STRING = "\033[33m";
constexpr std::string COLOR_TYPE = "\033[34m";
constexpr std::string COLOR_NUMERIC = "\033[36m";
constexpr std::string COLOR_LITERAL_OPERATOR = "\033[31m";
#else
constexpr std::string COLOR_LINE = "";
constexpr std::string COLOR_IDENTIFIER = "";
constexpr std::string COLOR_INIT = "";
constexpr std::string COLOR_STRING = "";
constexpr std::string COLOR_TYPE = "";
constexpr std::string COLOR_NUMERIC = "";
constexpr std::string COLOR_LITERAL_OPERATOR = "";
#endif
using Brackets = std::pair<std::string, std::string>;
template<class T>
std::string dump(T&&);
template<class T>
const std::string get_type_name(T&& val) {
const char* const name = typeid(std::forward<T>(val)).name();
int status = -4;
char* const demangled_name = abi::__cxa_demangle(name, NULL, NULL, &status);
std::string res{name};
if (status == 0) {
res = std::string(demangled_name);
free(demangled_name);
}
return COLOR_TYPE + res + COLOR_INIT;
}
struct debug_t : std::string {
using std::string::string;
debug_t(const std::string& str) {
this->assign(str);
}
};
template<size_t N, class T>
void dump_tuple_impl([[maybe_unused]] T&& val, std::stringstream &res) {
if constexpr(N < std::tuple_size_v<std::remove_cvref_t<T>>) {
res << dump(std::get<N>(val));
if constexpr(N < std::tuple_size_v<std::remove_cvref_t<T>> - 1) res << ", ";
dump_tuple_impl<N + 1>(std::forward<T>(val), res);
}
}
template<std::ranges::input_range R>
std::string dump_range_impl(R&& range, const Brackets& brcs = { "[", "]" }, const std::string& spl = ", ") {
std::stringstream res;
res << brcs.first << " ";
auto itr = std::ranges::begin(range);
auto end = std::ranges::end(std::forward<R>(range));
while(itr != end) {
if(std::ranges::next(itr) == end) res << dump(*itr) << " ";
else res << dump(*itr) << spl;
++itr;
}
res << brcs.second ;
return res.str();
}
std::string dump_debug_t(debug_t info) {
return info;
}
struct dump_primitive_like {
std::string operator()(std::nullptr_t) const {
return COLOR_INIT;
}
template<uni::internal::pointer T>
std::string operator()(const T ptr) const {
return dump(*ptr);
}
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::basic_string>
std::string operator()(T&& val) const {
std::stringstream res;
res << COLOR_STRING << "`" << val << "`" << COLOR_INIT;
return res.str();
}
std::string operator()(const char val) const {
std::stringstream res;
res << COLOR_STRING << "\'" << val << "\'" << COLOR_INIT;
return res.str();
}
std::string operator()(const char val[]) const {
std::stringstream res;
res << COLOR_STRING << "\"" << val << "\"" << COLOR_INIT;
return res.str();
}
std::string operator()(const unsigned char val) const {
std::stringstream res;
res << COLOR_NUMERIC << static_cast<int>(val) << COLOR_INIT;
return res.str();
}
std::string operator()(const bool val) const {
std::stringstream res;
res << COLOR_NUMERIC << (val ? "true" : "false" ) << COLOR_INIT;
return res.str();
}
template<uni::internal::arithmetic T>
std::string operator()(const T val) const {
std::stringstream res;
res << std::setprecision(std::numeric_limits<T>::digits10) << val;
auto str = res.str();
std::string dst = "";
while(str.length() > 3) {
dst = ',' + str.substr(str.length() - 3, 3) + dst;
str = str.substr(0, str.length() - 3);
}
return COLOR_NUMERIC + str + dst + COLOR_LITERAL_OPERATOR + uni::internal::literal_operator_v<T> + COLOR_INIT;
};
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::optional>
std::string operator()(T&& val) const {
if(val.has_value()) return dump(*val);
return COLOR_TYPE + "invalid" + COLOR_INIT;
}
};
struct dump_bitset {
template<std::size_t N>
std::string operator()(const std::bitset<N>& val) const {
std::stringstream res;
res << COLOR_NUMERIC << val.to_string() << COLOR_INIT;
return res.str();
}
};
struct dump_has_val {
template<class T>
requires requires (T val) { val.val(); }
std::string operator()(T&& val) const {
return dump(val.val());
}
};
struct dump_iterator {
template<std::input_or_output_iterator I>
std::string operator()(I&& itr) const {
return COLOR_TYPE + "<iterator> " + COLOR_INIT+ dump(*itr);
}
};
struct dump_wrapper {
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::map>
std::string operator()(T&& val) const {
return dump_range_impl(val, Brackets("{", "}"));
}
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::multimap>
std::string operator()(T&& val) const {
return dump_range_impl(val, Brackets("{", "}"));
}
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::unordered_map>
std::string operator()(T&& val) const {
return dump_range_impl(val, Brackets("{", "}"));
}
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::unordered_multimap>
std::string operator()(T&& val) const {
return dump_range_impl(val, Brackets("{", "}"));
}
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::set>
std::string operator()(T&& val) const {
return dump_range_impl(val, Brackets("{", "}"));
}
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::multiset>
std::string operator()(T&& val) const {
return dump_range_impl(val, Brackets("{", "}"));
}
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::unordered_set>
std::string operator()(T&& val) const {
return dump_range_impl(val, Brackets("{", "}"));
}
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::unordered_multiset>
std::string operator()(T&& val) const {
return dump_range_impl(val, Brackets("{", "}"));
}
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::valarray>
std::string operator()(T&& val) const {
return dump_range_impl(val, Brackets("[", "]"));
}
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::vector>
std::string operator()(T&& val) const {
return dump_range_impl(val, Brackets("[", "]"));
}
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::deque>
std::string operator()(T&& val) const {
return dump_range_impl(val, Brackets("[", "]"));
}
template<uni::internal::derived_from_template<std::queue> T>
std::string operator()(T val) const {
std::vector<typename T::value_type> vec;
while(!val.empty()) vec.emplace_back(val.front()), val.pop();
return dump_range_impl(vec, Brackets("<", ">"));
}
template<uni::internal::derived_from_template<std::stack> T>
std::string operator()(T val) const {
std::vector<typename T::value_type> vec;
while(!val.empty()) vec.emplace_back(val.top()), val.pop();
std::ranges::reverse(vec);
return dump_range_impl(vec, Brackets("<", ">"));
}
template<uni::internal::derived_from_template<std::priority_queue> T>
std::string operator()(T val) const {
std::vector<typename T::value_type> vec;
while(!val.empty()) vec.emplace_back(val.top()), val.pop();
return dump_range_impl(vec, Brackets("<", ">"));
}
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::pair>
std::string operator()(T&& val) const {
std::stringstream res;
res << "( " << dump(val.first) << ", " << dump(val.second) << " )";
return res.str();
}
template<class T>
requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::tuple>
std::string operator()(T&& val) const {
std::stringstream res;
res << "( ";
dump_tuple_impl<0>(val, res);
res << " )";
return res.str();
}
};
struct dump_range {
template<std::ranges::input_range T>
std::string operator()(T&& val) const {
return dump_range_impl(val);
}
};
struct dump_loggable {
template<uni::internal::loggable T>
std::string operator()(T&& val) const {
auto res = _debug(val);
if constexpr(std::same_as<decltype(res), debug_t>) {
return res;
}
else {
return dump(res);
}
}
};
template<class T>
std::string dump(T&& val) {
if constexpr(std::same_as<std::remove_cvref_t<T>, debug_t>) {
// return "debug_t";
return dump_debug_t(std::forward<T>(val));
}
if constexpr(std::invocable<dump_primitive_like, T>) {
// return "primitive";
return dump_primitive_like{}(std::forward<T>(val));
}
if constexpr(std::invocable<dump_loggable, T>) {
// return "loggable";
return dump_loggable{}(std::forward<T>(val));
}
if constexpr(std::invocable<dump_has_val, T>) {
// return "has val";
return dump_has_val{}(std::forward<T>(val));
}
if constexpr(std::invocable<dump_bitset, T>) {
// return "bitset";
return dump_bitset{}(std::forward<T>(val));
}
if constexpr(std::invocable<dump_iterator, T>) {
// return "iterator";
return dump_iterator{}(std::forward<T>(val));
}
if constexpr(std::invocable<dump_wrapper, T>) {
// return "wrapper";
return dump_wrapper{}(std::forward<T>(val));
}
if constexpr(std::invocable<dump_range, T>) {;
// return "range";
return dump_range{}(std::forward<T>(val));
}
return "== dump error ==";
}
template<class T> void debug(T&& val, const std::string& endl) {
*cdebug << dump(val) << endl << std::flush;
}
constexpr std::string_view WHITESPACES = " \n\r\t\f\v";
std::string ltrim(const std::string &s)
{
size_t start = s.find_first_not_of(WHITESPACES);
return (start == std::string::npos) ? "" : s.substr(start);
}
std::string rtrim(const std::string &s)
{
size_t end = s.find_last_not_of(WHITESPACES);
return (end == std::string::npos) ? "" : s.substr(0, end + 1);
}
std::string trim(const std::string &s) {
return rtrim(ltrim(s));
}
std::vector<std::string> split(const std::string& str) {
static constexpr char SEPARATOR = ',';
static constexpr char ESCAPE = '\\';
static constexpr std::string_view QUOTATIONS = "\"\'";
static constexpr std::string_view PARENTHESES = "()[]{}<>";
static constexpr auto PARENTHESES_KINDS = std::ranges::size(PARENTHESES);
static_assert(PARENTHESES_KINDS % 2 == 0);
std::vector<std::string> res = { "" };
bool quoted = false;
std::array<int,(PARENTHESES_KINDS / 2)> enclosed = { 0 };
for(auto itr = std::ranges::begin(str); itr != std::ranges::end(str); ++itr) {
if(std::ranges::find(QUOTATIONS, *itr) != std::ranges::end(QUOTATIONS)) {
if(itr == std::ranges::begin(str) or *std::ranges::prev(itr) != ESCAPE) {
quoted ^= true;
}
}
if(const auto found = std::ranges::find(PARENTHESES, *itr); found != std::ranges::end(PARENTHESES)) {
if(not quoted) {
auto& target = enclosed[std::ranges::distance(std::begin(PARENTHESES), found) / 2];
target = std::max(0, target - static_cast<int>((std::ranges::distance(std::begin(PARENTHESES), found) % 2) * 2) + 1);
}
}
if(
not quoted
and static_cast<std::size_t>(std::ranges::count(enclosed, 0)) == std::ranges::size(enclosed)
and *itr == SEPARATOR
) {
res.push_back("");
}
else {
res.back() += *itr;
}
}
for(auto&& v : res) v = trim(v);
return res;
}
template<class Arg> void raw(std::nullptr_t, Arg&& arg) { *cdebug << std::forward<Arg>(arg) << std::flush; }
template<class Arg> void raw(Arg&& arg) { *cdebug << dump(std::forward<Arg>(arg)) << std::flush; }
void debug(const std::vector<std::string>, const size_t, const int, const std::string) { debug(nullptr, COLOR_INIT + "\n"); }
std::map<std::pair<std::string, int>, int> count;
template<class Head, class... Tail>
void debug(
const std::vector<std::string> args, const size_t idx,
const int line, const std::string path,
Head&& H, Tail&&... T
) {
if(idx == 0) {
std::string file = path.substr(path.find_last_of("/") + 1);
debug(nullptr, COLOR_LINE + file + " #" + std::to_string(line) + " (" + std::to_string(count[{ file, line }]++) + ")" + COLOR_INIT);
}
debug(nullptr, "\n - ");
const std::string content = dump(H);
const std::string type_name = get_type_name(std::forward<Head>(H));
debug(nullptr, COLOR_IDENTIFIER + args[idx] + COLOR_INIT + " : ");
debug(nullptr, content);
if(type_name.size() + content.size() >= 300) debug(nullptr, "\n ");
debug(nullptr, " " + type_name);
debug(args, idx + 1, 0, path, std::forward<Tail>(T)...);
}
} // namespace debugger
#line 13 "template/debug.hpp"
#ifdef DEBUGGER_ENABLED
#define debug(...) debugger::debug(debugger::split(#__VA_ARGS__), 0, __LINE__, __FILE__, __VA_ARGS__)
#define debug_(...) do { const std::string file = __FILE__; debugger::raw(nullptr, debugger::COLOR_LINE + file.substr(file.find_last_of("/") + 1) + " #" + std::to_string(__LINE__) + debugger::COLOR_INIT + " "); debugger::raw(__VA_ARGS__); debugger::raw(nullptr, debugger::COLOR_INIT + "\n"); } while(0);
#define DEBUG if constexpr(true)
#else
#define debug(...) ({ ; })
#define debug_(...) ({ ; })
#define DEBUG if constexpr(false)
#endif
#line 18 "numeric/modular/barrett_reduction.hpp"
namespace uni {
namespace internal {
template<std::unsigned_integral Value, std::unsigned_integral Large>
requires has_double_digits_of<Large, Value>
struct barrett_reduction {
using value_type = Value;
using large_type = Large;
private:
large_type _mod = 0, _mi;
inline constexpr std::pair<large_type,value_type> _reduce(const large_type v) const noexcept(NO_EXCEPT) {
large_type x = multiply_high(v, this->_mi);
return { x, static_cast<value_type>(v - x * this->_mod) };
}
public:
static constexpr int digits = std::numeric_limits<value_type>::digits - 1;
static constexpr value_type max() noexcept { return (value_type{ 1 } << barrett_reduction::digits) - 1; }
inline constexpr value_type mod() const noexcept(NO_EXCEPT) { return this->_mod; }
constexpr barrett_reduction() noexcept = default;
constexpr explicit inline barrett_reduction(const value_type mod)
: _mod(mod), _mi(std::numeric_limits<large_type>::max() / mod + 1)
{
assert(0 < mod && mod <= barrett_reduction::max());
}
inline constexpr large_type quotient(const large_type v) const noexcept(NO_EXCEPT) {
const auto [ x, r ] = this->_reduce(v);
return static_cast<large_type>(this->_mod <= r ? x - 1 : x);
}
inline constexpr value_type reduce(const large_type v) const noexcept(NO_EXCEPT) {
const auto [ x, r ] = this->_reduce(v);
return static_cast<value_type>(this->_mod <= r ? r + this->_mod : r);
}
inline constexpr std::pair<large_type,value_type> divide(const large_type v) const noexcept(NO_EXCEPT) {
const auto [ x, r ] = this->_reduce(v);
if(this->_mod <= r) return { static_cast<large_type>(x - 1), static_cast<value_type>(r + this->_mod) };
return { static_cast<large_type>(x), static_cast<value_type>(r) };
}
inline constexpr value_type add(value_type x, const value_type y) const noexcept(NO_EXCEPT) {
x += y;
if(x >= this->_mod) x -= this->_mod;
return x;
}
inline constexpr value_type subtract(value_type x, const value_type y) const noexcept(NO_EXCEPT) {
if(x < y) x += this->_mod;
x -= y;
return x;
}
inline constexpr value_type multiply(const value_type x, const value_type y) const noexcept(NO_EXCEPT) {
return this->reduce(static_cast<large_type>(x) * static_cast<large_type>(y));
}
template<std::integral K>
inline constexpr value_type pow(const large_type v, const K p) const noexcept(NO_EXCEPT) {
if constexpr(std::signed_integral<K>) assert(p >= 0);
if(this->_mod == 1) return 0;
return uni::pow(
this->reduce(v), p,
[&](const value_type x, const value_type y) noexcept(NO_EXCEPT) { return this->multiply(x, y); }
);
}
inline constexpr auto compare(const value_type x, const value_type y) const noexcept(NO_EXCEPT) {
return x <=> y;
}
constexpr value_type convert_raw(const value_type v) const noexcept(NO_EXCEPT) { return v; }
template<std::integral T>
constexpr value_type convert(T v) const noexcept(NO_EXCEPT) {
using common_type = std::common_type_t<T, value_type>;
const common_type mod = static_cast<common_type>(this->_mod);
if(v > 0 && static_cast<common_type>(v) >= mod) {
if(static_cast<common_type>(v) <= barrett_reduction::max()) v = this->reduce(v);
else v %= mod;
}
if constexpr(std::signed_integral<T>) {
if(v < 0) {
if(static_cast<common_type>(-v) <= mod) v += mod;
else if(static_cast<common_type>(-v) <= barrett_reduction::max()) {
v = mod - this->reduce(static_cast<value_type>(-v - 1)) - 1;
}
else {
v %= mod;
if(v != 0) v += mod;
}
}
}
return static_cast<value_type>(v);
}
constexpr value_type revert(const value_type v) const noexcept(NO_EXCEPT) { return this->reduce(v); }
};
} // namespace internal
using barrett_reduction_32bit = internal::barrett_reduction<u32, u64>;
using barrett_reduction_64bit = internal::barrett_reduction<u64, u128>;
} // namespace uni
#line 2 "numeric/modular/montgomery_reduction.hpp"
#line 7 "numeric/modular/montgomery_reduction.hpp"
#line 10 "numeric/modular/montgomery_reduction.hpp"
#line 16 "numeric/modular/montgomery_reduction.hpp"
namespace uni {
namespace internal {
template<std::unsigned_integral Value, std::unsigned_integral Large>
requires has_double_digits_of<Large, Value>
struct montgomery_reduction {
using value_type = Value;
using large_type = Large;
private:
value_type _mod = 0, _r2, _mp;
constexpr value_type _inv() const noexcept(NO_EXCEPT) {
value_type res = this->_mod;
while(this->_mod * res != 1) res *= value_type{ 2 } - this->_mod * res;
return res;
}
public:
static constexpr int digits = std::numeric_limits<value_type>::digits - 2;
static constexpr value_type max() noexcept { return (value_type{ 1 } << montgomery_reduction::digits) - 1; }
inline constexpr value_type mod() const noexcept(NO_EXCEPT) { return this->_mod; }
value_type zero = 0;
value_type one;
constexpr montgomery_reduction() noexcept = default;
constexpr montgomery_reduction(const value_type mod) noexcept(NO_EXCEPT)
: _mod(mod), _r2(static_cast<value_type>(-static_cast<large_type>(mod) % mod)),
_mp(-this->_inv()), one(this->reduce(this->_r2))
{
assert((mod & 1) == 1);
assert(mod <= montgomery_reduction::max());
}
constexpr value_type reduce(const large_type v) const noexcept(NO_EXCEPT) {
return
static_cast<value_type>(
(
v + static_cast<large_type>(static_cast<value_type>(v) * this->_mp) * this->_mod
) >> std::numeric_limits<value_type>::digits
);
}
inline constexpr value_type add(value_type x, const value_type y) const noexcept(NO_EXCEPT) {
x += y;
if(x >= (this->_mod << 1)) x -= (this->_mod << 1);
return x;
}
inline constexpr value_type subtract(value_type x, const value_type y) const noexcept(NO_EXCEPT) {
if(x < y) x += (this->_mod << 1);
x -= y;
return x;
}
inline constexpr value_type multiply(const value_type x, const value_type y) const noexcept(NO_EXCEPT) {
return this->reduce(static_cast<large_type>(x) * static_cast<large_type>(y));
}
template<std::integral K>
inline constexpr value_type pow(const large_type v, const K p) const noexcept(NO_EXCEPT) {
if constexpr(std::signed_integral<K>) assert(p >= 0);
if(this->_mod == 1) return 0;
return uni::pow(
v, p,
[&](const value_type x, const value_type y) noexcept(NO_EXCEPT) { return this->multiply(x, y); },
static_cast<large_type>(this->one)
);
}
inline constexpr value_type normalize(const value_type v) const noexcept(NO_EXCEPT) {
assert(0 <= v && v < (this->_mod << 1));
if(v < this->_mod) return v;
return v - this->_mod;
}
inline constexpr auto compare(const value_type x, const value_type y) const noexcept(NO_EXCEPT) {
return this->normalize(x) <=> this->normalize(y);
}
inline constexpr value_type convert_raw(const value_type v) const noexcept(NO_EXCEPT) {
if(v == 1) return this->one;
return this->multiply(v, this->_r2);
}
template<std::integral T>
constexpr value_type convert(T v) const noexcept(NO_EXCEPT) {
if(v == 1) return this->one;
using common_type = std::common_type_t<T, value_type>;
const common_type mod2 = static_cast<common_type>(this->_mod << 1);
if(v > 0 && static_cast<common_type>(v) >= mod2) {
v %= mod2;
}
if constexpr(std::is_signed_v<T>) {
if(v < 0 && static_cast<common_type>(-v) >= mod2) {
v %= mod2;
if(v != 0) v += mod2;
}
}
return this->multiply(v, this->_r2);
}
constexpr value_type revert(const value_type v) const noexcept(NO_EXCEPT) {
return this->normalize(this->reduce(v));
}
};
// Thanks to: https://www.mathenachia.blog/even-mod-montgomery-impl/
template<std::unsigned_integral Value, std::unsigned_integral Large>
requires has_double_digits_of<Large, Value>
struct arbitrary_montgomery_reduction {
using value_type = Value;
using large_type = Large;
private:
using context = arbitrary_montgomery_reduction;
static constexpr int width = std::numeric_limits<value_type>::digits;
value_type _mod = 0;
int _tz;
value_type _m0;
large_type _m0i, _mask;
value_type _r2;
constexpr large_type _inv() const noexcept(NO_EXCEPT) {
large_type res = this->_m0;
while(((this->_m0 * res) & this->_mask) != 1) res *= large_type{ 2 } - this->_m0 * res;
return res & this->_mask;
}
constexpr value_type _m0ip() const noexcept(NO_EXCEPT) {
if(this->_tz == 0) return 0;
value_type res = this->_m0;
const value_type mask = (value_type{ 1 } << this->_tz) - 1;
while(((this->_m0 * res) & mask) != 1) res *= value_type{ 2 } - this->_m0 * res;
return res & mask;
}
public:
static constexpr int digits = std::numeric_limits<value_type>::digits - 2;
static constexpr value_type max() noexcept { return (value_type{ 1 } << context::digits) - 1; }
inline constexpr value_type mod() const noexcept(NO_EXCEPT) { return this->_mod; }
value_type one;
constexpr arbitrary_montgomery_reduction() noexcept = default;
constexpr arbitrary_montgomery_reduction(value_type m) noexcept(NO_EXCEPT) {
assert(0 < m);
if(this->_mod == m) return;
this->_mod = m;
this->_tz = std::countr_zero(m);
this->_m0 = m >> this->_tz;
assert(this->_mod < context::max());
this->_mask = (large_type{ 1 } << (context::width + this->_tz)) - 1;
this->_m0i = this->_inv();
{
const value_type x = (std::numeric_limits<large_type>::max() % this->_m0) + 1;
const value_type mask = (value_type{ 1 } << this->_tz) - 1;
this->_r2 = (x + ((((large_type{ 1 } - x) * this->_m0ip()) & mask) * this->_m0));
}
this->one = this->reduce(this->_r2);
}
constexpr value_type reduce(const large_type v) const noexcept(NO_EXCEPT) {
const value_type res =
static_cast<value_type>(
(
v +
this->_m0 *
((((v << std::numeric_limits<value_type>::digits) - v) * this->_m0i) & this->_mask)
) >> std::numeric_limits<value_type>::digits
);
return res;
}
inline constexpr value_type add(value_type x, const value_type y) const noexcept(NO_EXCEPT) {
x += y;
if(x >= (this->_mod << 1)) x -= (this->_mod << 1);
return x;
}
inline constexpr value_type subtract(value_type x, const value_type y) const noexcept(NO_EXCEPT) {
if(x < y) x += (this->_mod << 1);
x -= y;
return x;
}
inline constexpr value_type multiply(const value_type x, const value_type y) const noexcept(NO_EXCEPT) {
return this->reduce(static_cast<large_type>(x) * static_cast<large_type>(y));
}
template<std::integral K>
inline constexpr value_type pow(const large_type v, K p) const noexcept(NO_EXCEPT) {
if constexpr(std::signed_integral<K>) assert(p >= 0);
if(this->_mod == 1) return 0;
return uni::pow(
v, p,
[&](const value_type x, const value_type y) noexcept(NO_EXCEPT) { return this->multiply(x, y); },
static_cast<large_type>(this->one)
);
}
inline constexpr value_type normalize(const value_type v) const noexcept(NO_EXCEPT) {
assert(0 <= v && v < (this->_mod << 1));
if(v < this->_mod) return v;
return v - this->_mod;
}
inline constexpr auto compare(const large_type x, const large_type y) const noexcept(NO_EXCEPT) {
return this->normalize(x) <=> this->normalize(y);
}
inline constexpr value_type convert_raw(const value_type v) const noexcept(NO_EXCEPT) {
if(v == 1) return this->one;
return this->multiply(v, this->_r2);
}
template<std::integral T>
constexpr value_type convert(T v) const noexcept(NO_EXCEPT) {
if(v == 1) return this->one;
using common_type = std::common_type_t<T, value_type>;
const common_type mod2 = static_cast<common_type>(this->_mod << 1);
if(v > 0 && static_cast<common_type>(v) >= mod2) {
v %= mod2;
}
if constexpr(std::signed_integral<T>) {
if(v < 0) {
if(static_cast<common_type>(-v) >= mod2) v %= mod2;
if(v < 0) v += mod2;
}
}
return this->multiply(v, this->_r2);
}
constexpr value_type revert(const value_type v) const noexcept(NO_EXCEPT) {
return this->normalize(this->reduce(v));
}
};
} // namespace internal
using montgomery_reduction_32bit = internal::montgomery_reduction<u32, u64>;
using montgomery_reduction_64bit = internal::montgomery_reduction<u64, u128>;
using arbitrary_montgomery_reduction_32bit = internal::arbitrary_montgomery_reduction<u32, u64>;
using arbitrary_montgomery_reduction_64bit = internal::arbitrary_montgomery_reduction<u64, u128>;
} // namespace uni
#line 16 "numeric/modular/modint_interface.hpp"
namespace uni {
namespace internal {
template<class T>
concept modint_family =
numeric<T> &&
has_static_one<T> && has_static_zero<T> &&
requires (T v, i64 p, typename T::value_type x) {
{ v.pow(p) } -> std::same_as<T>;
{ v.inv() } -> std::same_as<T>;
{ T::raw(x) } -> std::same_as<T>;
{ v.val() } -> std::same_as<typename T::value_type>;
{ T::mod() } -> std::same_as<typename T::value_type>;
{ T::max() } -> std::same_as<typename T::value_type>;
T::digits;
T::context::dynamic;
};
template<class T>
concept dynamic_modint_family =
modint_family<T> &&
T::context::dynamic &&
requires (typename T::value_type v) {
T::set_mod(v);
};
template<class T>
concept static_modint_family =
modint_family<T> &&
(!T::context::dynamic); //&&
// requires {
// T::is_prime;
// };
template<class T>
concept modular_reduction =
std::default_initializable<T> &&
std::constructible_from<T, typename T::value_type> &&
requires (T v, typename T::value_type x, i64 p) {
typename T::value_type;
T::digits;
{ T::max() } -> std::same_as<typename T::value_type>;
{ v.mod() } -> std::same_as<typename T::value_type>;
{ v.reduce(x) } -> std::same_as<typename T::value_type>;
{ v.add(x, x) } -> std::same_as<typename T::value_type>;
{ v.subtract(x, x) } -> std::same_as<typename T::value_type>;
{ v.multiply(x, x) } -> std::same_as<typename T::value_type>;
{ v.multiply(x, x) } -> std::same_as<typename T::value_type>;
{ v.pow(x, p) } -> std::same_as<typename T::value_type>;
{ v.convert_raw(x) } -> std::same_as<typename T::value_type>;
{ v.convert(x) } -> std::same_as<typename T::value_type>;
{ v.revert(x) } -> std::same_as<typename T::value_type>;
v.compare(x, x);
};
template<class T>
concept modular_context =
requires {
typename T::reductor;
typename T::value_type;
T::reduction;
};
} // namespace internal
template<internal::modular_reduction Reduction, typename Reduction::value_type Mod>
struct static_modular_context {
using reductor = Reduction;
using value_type = typename reductor::value_type;
static constexpr bool dynamic = false;
static constexpr reductor reduction = reductor(Mod);
private:
using context = static_modular_context;
};
template<internal::modular_reduction Reduction, i64 Id>
struct dynamic_modular_context {
using reductor = Reduction;
using value_type = typename reductor::value_type;
static constexpr bool dynamic = true;
static inline reductor reduction;
private:
using context = dynamic_modular_context;
public:
static constexpr void set_mod(const value_type mod) noexcept(NO_EXCEPT) { context::reduction = reductor(mod); }
};
template<internal::modular_context> struct modint;
template<u32 Mod> using static_builtin_modular_context_32bit = static_modular_context<builtin_reduction_32bit, Mod>;
template<u64 Mod> using static_builtin_modular_context_64bit = static_modular_context<builtin_reduction_64bit, Mod>;
template<u32 Mod> using static_barrett_modular_context_32bit = static_modular_context<barrett_reduction_32bit, Mod>;
template<u64 Mod> using static_barrett_modular_context_64bit = static_modular_context<barrett_reduction_64bit, Mod>;
template<u32 Mod> using static_montgomery_modular_context_32bit = static_modular_context<montgomery_reduction_32bit, Mod>;
template<u64 Mod> using static_montgomery_modular_context_64bit = static_modular_context<montgomery_reduction_64bit, Mod>;
template<u32 Mod> using static_arbitrary_montgomery_modular_context_32bit = static_modular_context<arbitrary_montgomery_reduction_32bit, Mod>;
template<u64 Mod> using static_arbitrary_montgomery_modular_context_64bit = static_modular_context<arbitrary_montgomery_reduction_64bit, Mod>;
template<u32 Mod> using static_binary_modular_context_32bit = static_modular_context<binary_reduction_32bit, Mod>;
template<u64 Mod> using static_binary_modular_context_64bit = static_modular_context<binary_reduction_64bit, Mod>;
template<u128 Mod> using static_binary_modular_context_128bit = static_modular_context<binary_reduction_128bit, Mod>;
template<u32 Mod> using static_builtin_modint_32bit = modint<static_builtin_modular_context_32bit<Mod>>;
template<u64 Mod> using static_builtin_modint_64bit = modint<static_builtin_modular_context_64bit<Mod>>;
template<u32 Mod> using static_barrett_modint_32bit = modint<static_barrett_modular_context_32bit<Mod>>;
template<u64 Mod> using static_barrett_modint_64bit = modint<static_barrett_modular_context_64bit<Mod>>;
template<u32 Mod> using static_montgomery_modint_32bit = modint<static_montgomery_modular_context_32bit<Mod>>;
template<u64 Mod> using static_montgomery_modint_64bit = modint<static_montgomery_modular_context_64bit<Mod>>;
template<u32 Mod> using static_arbitrary_montgomery_modint_32bit = modint<static_arbitrary_montgomery_modular_context_32bit<Mod>>;
template<u64 Mod> using static_arbitrary_montgomery_modint_64bit = modint<static_arbitrary_montgomery_modular_context_64bit<Mod>>;
template<u32 Mod> using static_binary_modint_32bit = modint<static_binary_modular_context_32bit<Mod>>;
template<u64 Mod> using static_binary_modint_64bit = modint<static_binary_modular_context_64bit<Mod>>;
template<u128 Mod> using static_binary_modint_128bit = modint<static_binary_modular_context_128bit<Mod>>;
template<i64 Id> using dynamic_builtin_modular_context_32bit = dynamic_modular_context<builtin_reduction_32bit, Id>;
template<i64 Id> using dynamic_builtin_modular_context_64bit = dynamic_modular_context<builtin_reduction_64bit, Id>;
template<i64 Id> using dynamic_barrett_modular_context_32bit = dynamic_modular_context<barrett_reduction_32bit, Id>;
template<i64 Id> using dynamic_barrett_modular_context_64bit = dynamic_modular_context<barrett_reduction_64bit, Id>;
template<i64 Id> using dynamic_montgomery_modular_context_32bit = dynamic_modular_context<montgomery_reduction_32bit, Id>;
template<i64 Id> using dynamic_montgomery_modular_context_64bit = dynamic_modular_context<montgomery_reduction_64bit, Id>;
template<i64 Id> using dynamic_arbitrary_montgomery_modular_context_32bit = dynamic_modular_context<arbitrary_montgomery_reduction_32bit, Id>;
template<i64 Id> using dynamic_arbitrary_montgomery_modular_context_64bit = dynamic_modular_context<arbitrary_montgomery_reduction_64bit, Id>;
template<i64 Id> using dynamic_binary_modular_context_32bit = dynamic_modular_context<binary_reduction_32bit, Id>;
template<i64 Id> using dynamic_binary_modular_context_64bit = dynamic_modular_context<binary_reduction_64bit, Id>;
template<i64 Id> using dynamic_binary_modular_context_128bit = dynamic_modular_context<binary_reduction_128bit, Id>;
template<i64 Id> using dynamic_builtin_modint_32bit = modint<dynamic_builtin_modular_context_32bit<Id>>;
template<i64 Id> using dynamic_builtin_modint_64bit = modint<dynamic_builtin_modular_context_64bit<Id>>;
template<i64 Id> using dynamic_barrett_modint_32bit = modint<dynamic_barrett_modular_context_32bit<Id>>;
template<i64 Id> using dynamic_barrett_modint_64bit = modint<dynamic_barrett_modular_context_64bit<Id>>;
template<i64 Id> using dynamic_montgomery_modint_32bit = modint<dynamic_montgomery_modular_context_32bit<Id>>;
template<i64 Id> using dynamic_montgomery_modint_64bit = modint<dynamic_montgomery_modular_context_64bit<Id>>;
template<i64 Id> using dynamic_arbitrary_montgomery_modint_32bit = modint<dynamic_arbitrary_montgomery_modular_context_32bit<Id>>;
template<i64 Id> using dynamic_arbitrary_montgomery_modint_64bit = modint<dynamic_arbitrary_montgomery_modular_context_64bit<Id>>;
template<i64 Id> using dynamic_binary_modint_32bit = modint<dynamic_binary_modular_context_32bit<Id>>;
template<i64 Id> using dynamic_binary_modint_64bit = modint<dynamic_binary_modular_context_64bit<Id>>;
template<i64 Id> using dynamic_binary_modint_128bit = modint<dynamic_binary_modular_context_128bit<Id>>;
template<u32 Mod> using static_modint_32bit = static_builtin_modint_32bit<Mod>;
template<u64 Mod> using static_modint_64bit = static_builtin_modint_64bit<Mod>;
using modint998244353 = static_modint_32bit<998244353>;
using modint1000000007 = static_modint_32bit<1000000007>;
using modint_32 = dynamic_barrett_modint_32bit<-1>;
using modint_64 = dynamic_barrett_modint_64bit<-1>;
template<const unsigned Val, const unsigned Mod = 998244353>
const uni::static_modint_32bit<Mod> MINT = Val;
template<const unsigned Val, const unsigned Mod = 998244353>
const unsigned INV = uni::static_modint_32bit<Mod>{ Val }.inv().val();
template<const unsigned Val, const unsigned Mod = 998244353>
const int SINV = uni::static_modint_32bit<Mod>{ Val }.inv().val();
} // namespace uni
#line 22 "adaptor/internal/input.hpp"
#line 24 "adaptor/internal/input.hpp"
namespace uni {
template<std::derived_from<std::ios_base> Source = std::istream>
struct input_adaptor {
using source_type = Source;
private:
template<class T>
requires std::derived_from<T, std::valarray<typename T::value_type>>
auto _set(uni::internal::resolving_rank<6>, T& val) noexcept(NO_EXCEPT) -> int {
this->operator()(ALL(val));
return 0;
}
template<class T>
requires
requires (source_type& in, T& val) {
in >> val;
}
int _set(uni::internal::resolving_rank<5>, T& val) noexcept(NO_EXCEPT) {
*this->in >> val;
return 0;
}
template<std::ranges::range T>
int _set(uni::internal::resolving_rank<4>, T& val) noexcept(NO_EXCEPT) {
this->operator()(std::ranges::begin(val), std::ranges::end(val));
return 0;
}
template<class T>
requires
requires (T& val) {
val.first;
val.second;
}
int _set(uni::internal::resolving_rank<3>, T& val) noexcept(NO_EXCEPT) {
*this >> val.first >> val.second;
return 0;
}
template<class T>
requires
requires (T& val) {
std::get<0>(val);
}
int _set(uni::internal::resolving_rank<2>, T& val) noexcept(NO_EXCEPT) {
tuple_for_each([this](auto&& v) { *this >> v; }, val);
return 0;
}
template<uni::internal::modint_family T>
int _set(uni::internal::resolving_rank<1>, T& val) noexcept(NO_EXCEPT) {
std::int64_t v; std::cin >> v;
val = { v };
return 0;
}
template<class T>
requires
requires {
typename T::value_type;
}
int _set(uni::internal::resolving_rank<0>, T& val) noexcept(NO_EXCEPT) {
typename T::value_type v; *this >> v;
val = { v };
return 0;
}
protected:
template<class T>
source_type *set(T& val) noexcept(NO_EXCEPT) {
this->_set(uni::internal::resolving_rank<10>{}, val);
return this->in;
}
template<class T>
source_type *set(T&& _val) noexcept(NO_EXCEPT) {
T val = _val;
this->_set(uni::internal::resolving_rank<10>{}, val);
return this->in;
}
public:
using char_type = typename source_type::char_type;
source_type *in;
input_adaptor(source_type *_in = &std::cin) noexcept(NO_EXCEPT) : in(_in) {}
template<class T>
inline input_adaptor& operator>>(T&& s) noexcept(NO_EXCEPT) {
this->set(std::forward<T>(s));
return *this;
}
template<class T>
inline T one() noexcept(NO_EXCEPT) {
T val; *this >> val;
return val;
}
template<class T>
inline auto& operator()(T& val) noexcept(NO_EXCEPT) {
*this >> val;
return *this;
}
template<class T, class... Args>
inline auto& operator()(T& head, Args&... tail) noexcept(NO_EXCEPT) {
*this >> head;
this->operator()(tail...);
return *this;
}
template<std::input_or_output_iterator I, std::sentinel_for<I> S>
inline auto& operator()(I first, S last) noexcept(NO_EXCEPT) {
for(I itr=first; itr!=last; ++itr) *this >> *itr;
return *this;
}
explicit operator bool() const noexcept(NO_EXCEPT) { return (bool)*this->in; }
};
} // namespace uni
#line 2 "adaptor/internal/output.hpp"
#line 11 "adaptor/internal/output.hpp"
#line 15 "adaptor/internal/output.hpp"
namespace uni {
template<class Destination = std::ostream>
struct output_adaptor {
using destination_type = Destination;
private:
template<class T>
requires
requires (destination_type& out, T val) {
out << val;
}
int _put(uni::internal::resolving_rank<5>, T&& val) noexcept(NO_EXCEPT) {
*this->out << std::forward<T>(val);
return 0;
}
template<class T>
requires
requires (T&& val) {
val.val();
}
int _put(uni::internal::resolving_rank<4>, T&& val) noexcept(NO_EXCEPT) {
this->put(val.val());
return 0;
}
template<std::ranges::input_range T>
int _put(uni::internal::resolving_rank<3>, T&& val) noexcept(NO_EXCEPT) {
(*this)(std::ranges::begin(val), std::ranges::end(val), false);
return 0;
}
template<class T>
requires
requires (T&& val) {
val.first;
val.second;
}
int _put(uni::internal::resolving_rank<2>, T&& val) noexcept(NO_EXCEPT) {
*this << val.first, this->put_separator();
*this << val.second;
return 0;
}
template<class T>
requires
requires (T&& val) {
std::get<0>(val);
}
auto _put(uni::internal::resolving_rank<1>, T&& val) noexcept(NO_EXCEPT) {
std::apply([this](const auto&... args) constexpr { ((*this << args, this->put_separator()), ...); }, std::forward<T>(val));
return 0;
}
template<std::input_or_output_iterator T>
int _put(uni::internal::resolving_rank<0>, T&& val) noexcept(NO_EXCEPT) {
(*this)(*std::forward<T>(val));
return 0;
}
protected:
template<class T>
destination_type* put(T&& val) noexcept(NO_EXCEPT){
this->_put(uni::internal::resolving_rank<10>{}, std::forward<T>(val));
return this->out;
}
public:
using char_type = typename destination_type::char_type;
static constexpr auto sendl = std::endl<char_type,std::char_traits<char_type>>;
static constexpr auto sflush = std::flush<char_type,std::char_traits<char_type>>;
protected:
using sfunc_type = std::remove_const_t<decltype(output_adaptor::sendl)>;
public:
using separator_type = std::variant<std::string,sfunc_type>;
destination_type *out;
separator_type endline;
separator_type separator;
protected:
void put_separator() noexcept(NO_EXCEPT) {
if(this->separator.index() == 0) *this->out << std::get<std::string>(this->separator);
if(this->separator.index() == 1) *this->out << std::get<sfunc_type>(this->separator);
}
void put_endline() noexcept(NO_EXCEPT) {
if(this->endline.index() == 0) *this->out << std::get<std::string>(this->endline);
if(this->endline.index() == 1) *this->out << std::get<sfunc_type>(this->endline);
}
public:
template<class Terminator = std::string, class Separator = std::string>
output_adaptor(destination_type *des = &std::cout, Terminator endl = "\n", Separator sep = " ") noexcept(NO_EXCEPT)
: out(des), endline(endl), separator(sep)
{
*this << std::fixed << std::setprecision(20);
}
inline auto& seekp(const typename destination_type::off_type off, const std::ios_base::seekdir dir = std::ios_base::cur) noexcept(NO_EXCEPT) {
this->out->seekp(off, dir); return *this;
};
template<class T> inline output_adaptor& operator<<(T&& s) noexcept(NO_EXCEPT){
this->put(std::forward<T>(s));
return *this;
}
template<class T = std::string>
inline auto& operator()(T&& val = "") noexcept(NO_EXCEPT){
*this << std::forward<T>(val), this->put_endline();
return *this;
}
template<class T, class ...Args>
inline auto& operator()(T&& head, Args&& ...tail) noexcept(NO_EXCEPT){
*this << std::forward<T>(head), this->put_separator();
(*this)(std::forward<Args>(tail)...);
return *this;
}
template<std::forward_iterator I, std::sentinel_for<I> S>
inline auto& operator()(I first, S last, const bool terminate = true) noexcept(NO_EXCEPT) {
for(I itr=first; itr!=last;) {
*this << *itr;
if(++itr == last) {
if(terminate) this->put_endline();
}
else this->put_separator();
}
return *this;
}
template<class T>
inline auto& operator()(const std::initializer_list<T> vals) noexcept(NO_EXCEPT) {
std::vector wrapped(vals.begin(), vals.end());
(*this)(wrapped.begin(), wrapped.end());
return *this;
}
template<class T0, class T1>
inline auto& conditional(const bool cond, const T0& a, const T1& b) noexcept(NO_EXCEPT) {
if(cond) (*this)(a);
else (*this)(b);
return *this;
}
inline auto& yesno(const bool cond) noexcept(NO_EXCEPT) {
if(cond) this->yes();
else this->no();
return *this;
}
inline auto yes() noexcept(NO_EXCEPT) {
*this->out << "Yes";
this->put_endline();
return *this;
}
inline auto no() noexcept(NO_EXCEPT) {
*this->out << "No";
this->put_endline();
return *this;
}
inline auto flush() noexcept(NO_EXCEPT) {
*this->out << std::flush;
return *this;
}
};
} // namespace uni
#line 7 "adaptor/io.hpp"
namespace uni {
uni::input_adaptor _input;
uni::output_adaptor _print;
}
#define input uni::_input
#define print uni::_print
#line 21 "structure/graph.hpp"
#line 2 "structure/grid.hpp"
#line 12 "structure/grid.hpp"
#line 16 "structure/grid.hpp"
#line 19 "structure/grid.hpp"
#line 21 "structure/grid.hpp"
#line 24 "structure/grid.hpp"
namespace uni {
namespace internal {
namespace grid_impl {
template<class T>
struct container_base {
using value_type = T;
using size_type = internal::size_t;
private:
size_type _h, _w;
protected:
inline void _validate_index(__attribute__ ((unused)) const size_type i, __attribute__ ((unused)) const size_type j) const noexcept(NO_EXCEPT) {
assert(0 <= i and i < this->height());
assert(0 <= j and j < this->width());
}
inline size_type _positivize_row_index(const size_type x) const noexcept(NO_EXCEPT) {
return x < 0 ? this->height() + x : x;
}
inline size_type _positivize_col_index(const size_type x) const noexcept(NO_EXCEPT) {
return x < 0 ? this->width() + x : x;
}
public:
container_base() = default;
container_base(const size_type h, const size_type w) noexcept(NO_EXCEPT) : _h(h), _w(w) {}
void resize(const size_type h, const size_type w) noexcept(NO_EXCEPT) {
this->_h = h, this->_w = w;
}
inline size_type height() const noexcept(NO_EXCEPT) { return this->_h; }
inline size_type width() const noexcept(NO_EXCEPT) { return this->_w; }
inline size_type id(const size_type i, const size_type j) const noexcept(NO_EXCEPT) {
const size_type _i = this->_positivize_row_index(i);
const size_type _j = this->_positivize_col_index(j);
this->_validate_index(_i, _j);
return _i * this->width() + _j;
}
inline size_type id(const std::pair<size_type,size_type>& p) const noexcept(NO_EXCEPT) {
return this->id(p.first, p.second);
}
inline std::pair<size_type,size_type> pos(const size_type id) const noexcept(NO_EXCEPT) {
return { id / this->width(), id % this->width() };
}
};
template<class Base>
struct regular_container : Base, container_base<typename Base::value_type::value_type> {
using row_type = typename Base::value_type;
using value_type = typename row_type::value_type;
using size_type = internal::size_t;
explicit regular_container(const size_type n = 0) noexcept(NO_EXCEPT) : regular_container(n, n) {}
regular_container(const size_type h, const size_type w, const value_type &val = value_type()) noexcept(NO_EXCEPT)
: Base(h, row_type(w, val)), container_base<value_type>(h, w)
{}
regular_container(const std::initializer_list<row_type> init_list) noexcept(NO_EXCEPT) : Base(init_list) {
const auto rows = std::ranges::ssize(init_list);
const size_type first_cols = init_list.begin()->size();
if constexpr (DEV_ENV) { ITR(init_row, init_list) assert((size_type)init_row.size() == first_cols); }
this->container_base<value_type>::resize(rows, first_cols);
}
inline void assign(const regular_container &source) noexcept(NO_EXCEPT) {
this->resize(source.height(), source.width());
this->Base::assign(ALL(source));
}
inline void assign(const size_type h, const size_type w, const value_type &val = value_type()) noexcept(NO_EXCEPT) {
this->container_base<value_type>::resize(h, w);
this->Base::resize(h);
ITRR(row, *this) row.assign(w, val);
}
inline void resize(const size_type h, const size_type w) noexcept(NO_EXCEPT) {
this->container_base<value_type>::resize(h, w);
this->Base::resize(h);
ITRR(row, *this) row.resize(w);
}
inline auto& operator()(const size_type i, const size_type j) noexcept(NO_EXCEPT) {
const size_type _i = this->_positivize_row_index(i);
const size_type _j = this->_positivize_col_index(j);
this->_validate_index(_i, _j);
return (*this)[_i][_j];
}
inline const auto& operator()(const size_type i, const size_type j) const noexcept(NO_EXCEPT) {
const size_type _i = this->_positivize_row_index(i);
const size_type _j = this->_positivize_col_index(j);
this->_validate_index(_i, _j);
return (*this)[_i][_j];
}
inline auto& operator()(const std::pair<size_type,size_type>& p) noexcept(NO_EXCEPT) {
return this->operator()(p.first, p.second);
}
inline const auto& operator()(const std::pair<size_type,size_type>& p) const noexcept(NO_EXCEPT) {
return this->operator()(p.first, p.second);
}
};
template<class Base>
struct unfolded_container : Base, container_base<typename Base::value_type> {
using value_type = typename Base::value_type;
using size_type = internal::size_t;
explicit unfolded_container(size_type n = 0) noexcept(NO_EXCEPT) : unfolded_container(n, n) {}
unfolded_container(const size_type h, const size_type w, const value_type &val = value_type()) noexcept(NO_EXCEPT)
: Base(h * w, val), container_base<value_type>(h, w)
{}
unfolded_container(std::initializer_list<std::initializer_list<value_type>> init_list) noexcept(NO_EXCEPT) {
const auto rows = std::ranges::ssize(init_list);
const auto first_cols = std::ranges::ssize(std::ranges::begin(init_list));
this->resize(rows, first_cols);
{
size_type index = 0;
for(
auto itr = std::ranges::begin(init_list), itr_end = std::ranges::end(init_list);
itr!=itr_end;
++itr
)
{
assert((size_type)itr->size() == first_cols);
for(auto v=itr->begin(), v_end=itr->end(); v!=v_end; ++v) (*this)[index++] = *v;
}
}
}
inline void assign(const unfolded_container &source) noexcept(NO_EXCEPT) {
this->resize(source.height(), source.width());
this->Base::assign(ALL(source));
}
inline void assign(const size_type h, const size_type w, const value_type &val = value_type()) noexcept(NO_EXCEPT) {
this->container_base<value_type>::resize(h, w);
this->Base::assign(h * w, val);
}
inline void resize(const size_type h, const size_type w) noexcept(NO_EXCEPT) {
this->container_base<value_type>::resize(h, w);
this->Base::resize(h * w);
}
inline value_type& operator()(const size_type i, const size_type j) noexcept(NO_EXCEPT) {
const size_type _i = this->_positivize_row_index(i);
const size_type _j = this->_positivize_col_index(j);
return this->operator[](this->id(_i, _j));
}
inline value_type& operator()(const std::pair<size_type,size_type>& p) noexcept(NO_EXCEPT) {
return this->operator()(this->id(p.first, p.second));
}
inline const value_type& operator()(const std::pair<size_type,size_type>& p) const noexcept(NO_EXCEPT) {
return this->operator()(this->id(p.first, p.second));
}
};
} // namespace grid_impl
template<class Container>
struct grid_core : Container {
using Container::Container;
using value_type = Container::value_type;
using size_type = internal::size_t;
enum class invert_direction { vertical, horizontal };
enum class rotate_direction { counter_clockwise, clockwise };
inline bool is_valid(const size_type i, const size_type j) const noexcept(NO_EXCEPT) {
return 0 <= i and i < this->height() and 0 <= j and j < this->width();
}
inline bool is_valid(const std::pair<size_type, size_type>& p) const noexcept(NO_EXCEPT) {
return this->is_valid(p.first, p.second);
}
template<std::input_iterator I, std::sentinel_for<I> S>
inline auto vicinities(const size_type i, const size_type j, I dirs_first, S dirs_last) const noexcept(NO_EXCEPT) {
std::vector<std::pair<size_type, size_type>> res;
REP(itr, dirs_first, dirs_last) {
const size_type ii = i + itr->first, jj = j + itr->second;
if(this->is_valid(ii, jj)) res.emplace_back(ii, jj);
}
return res;
}
template<class I, class C>
inline auto vicinities(const std::pair<size_type, size_type>& p, const C dirs) const noexcept(NO_EXCEPT) {
return this->vicinities(p.first, p.second, ALL(dirs));
}
inline auto vicinities4(const size_type i, const size_type j) const noexcept(NO_EXCEPT) { return this->vicinities(i, j, ALL(DIRS4)); }
inline auto vicinities4(const std::pair<size_type, size_type>& p) const noexcept(NO_EXCEPT) { return this->vicinities(p.first, p.second, ALL(DIRS4)); }
inline auto vicinities8(const size_type i, const size_type j) const noexcept(NO_EXCEPT) { return this->vicinities(i, j, ALL(DIRS8)); }
inline auto vicinities8(const std::pair<size_type, size_type>& p) const noexcept(NO_EXCEPT) { return this->vicinities(p.first, p.second, ALL(DIRS8)); }
template<invert_direction DIRECTION = invert_direction::vertical>
inline grid_core& invert() noexcept(NO_EXCEPT) {
grid_core res(this->height(), this->width());
REP(i, this->height()) REP(j, this->width()) {
if constexpr (DIRECTION == invert_direction::vertical) {
res(i,j) = (*this)(this->height()-i-1,j);
}
else {
res(i,j) = (*this)(i, this->width()-j-1);
}
}
this->assign(res);
return *this;
}
template<rotate_direction DIRECTION = rotate_direction::clockwise>
inline grid_core& rotate(const size_type k) noexcept(NO_EXCEPT) {
grid_core res = *this;
REP(i, k) { res = res.rotate<DIRECTION>(); }
this->assign(res);
return *this;
}
template<rotate_direction DIRECTION = rotate_direction::clockwise>
inline grid_core& rotate() noexcept(NO_EXCEPT) {
grid_core res(this->width(), this->height());
REP(i, this->width()) REP(j, this->height()) {
if constexpr (DIRECTION == rotate_direction::clockwise) {
res(i,j) = (*this)(this->height()-j-1,i);
}
else {
res(i,j) = (*this)(j,this->width()-i-1);
}
}
this->assign(res);
return *this;
}
inline grid_core& transpose() noexcept(NO_EXCEPT) {
grid_core res(this->width(), this->height());
REP(i, this->width()) REP(j, this->height()) {
res(i,j) = (*this)(j,i);
}
this->assign(res);
return *this;
}
};
} // namespace internal
template<class T, class row_type = vector<T>, class Base = vector<row_type>>
using grid = internal::grid_core<internal::grid_impl::regular_container<Base>>;
template<class T, class row_type = valarray<T>, class Base = vector<row_type>>
using valgrid = internal::grid_core<internal::grid_impl::regular_container<Base>>;
template<class T, class Base = vector<T>>
using unfolded_grid = internal::grid_core<internal::grid_impl::unfolded_container<Base>>;
template<class T, class Base = valarray<T>>
using unfolded_valgrid = internal::grid_core<internal::grid_impl::unfolded_container<Base>>;
} // namespace uni
#line 2 "data_structure/disjoint_set.hpp"
#line 8 "data_structure/disjoint_set.hpp"
#line 12 "data_structure/disjoint_set.hpp"
#line 15 "data_structure/disjoint_set.hpp"
#line 17 "data_structure/disjoint_set.hpp"
namespace uni {
//Thanks to: atcoder::disjoint_set
struct disjoint_set {
using size_type = internal::size_t;
private:
size_type _n = 0, _group_count = 0;
// root node: -1 * component size
// otherwise: parent
std::vector<size_type> _parent_or_size;
public:
disjoint_set() noexcept = default;
explicit disjoint_set(const size_type n) noexcept(NO_EXCEPT) : _n(n), _group_count(n), _parent_or_size(n, -1) {}
inline auto size() const noexcept(NO_EXCEPT) { return this->_n; }
inline auto group_count() const noexcept(NO_EXCEPT) { return this->_group_count; }
inline auto merge(const size_type a, const size_type b) noexcept(NO_EXCEPT) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
size_type x = this->leader(a), y = this->leader(b);
if (x == y) return x;
--this->_group_count;
if (-this->_parent_or_size[x] < -this->_parent_or_size[y]) std::swap(x, y);
this->_parent_or_size[x] += this->_parent_or_size[y];
this->_parent_or_size[y] = x;
return x;
}
inline bool same(const size_type a, const size_type b) noexcept(NO_EXCEPT) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return this->leader(a) == this->leader(b);
}
inline size_type leader(const size_type a) noexcept(NO_EXCEPT) {
assert(0 <= a && a < _n);
if(this->_parent_or_size[a] < 0) return a;
return this->_parent_or_size[a] = this->leader(this->_parent_or_size[a]);
}
inline auto size(const size_type a) noexcept(NO_EXCEPT) {
assert(0 <= a && a < _n);
return -this->_parent_or_size[this->leader(a)];
}
inline auto groups() noexcept(NO_EXCEPT) {
vector<size_type> leader_buf(_n), group_size(_n);
REP(i, this->_n) {
leader_buf[i] = this->leader(i);
group_size[leader_buf[i]]++;
}
vector<vector<size_type>> result(_n);
REP(i, this->_n) result[i].reserve(group_size[i]);
REP(i, this->_n) result[leader_buf[i]].push_back(i);
{
const auto range = std::ranges::remove_if(result, [&](const auto& v) { return v.empty(); });
result.erase(ALL(range));
}
return result;
}
};
} // namespace uni
#line 24 "structure/graph.hpp"
#line 2 "adaptor/virtual_map.hpp"
#line 5 "adaptor/virtual_map.hpp"
#line 7 "adaptor/virtual_map.hpp"
namespace uni {
template<class> struct virtual_combined_map {};
template<class Mapped, class... Keys>
struct virtual_combined_map<Mapped(Keys...)> {
using key_type = std::tuple<Keys...>;
using mapped_type = Mapped;
using value_type = std::pair<key_type,mapped_type>;
protected:
std::function<Mapped(Keys...)> _f;
public:
virtual_combined_map() = default;
template<class F>
explicit virtual_combined_map(F&& f) noexcept(NO_EXCEPT) : _f(f) {};
inline const auto* get_functor() const noexcept(NO_EXCEPT) { return this->_f; }
inline auto* get_functor() noexcept(NO_EXCEPT) { return this->_f; }
template<class F>
inline auto& set_functor(F&& f) const noexcept(NO_EXCEPT) { return this->_f = f; }
inline mapped_type operator()(const Keys&... key) const noexcept(NO_EXCEPT) {
return this->_f(key...);
}
inline mapped_type operator[](const key_type& key) const noexcept(NO_EXCEPT) {
return std::apply(this->_f, key);
}
};
template<class Key, class Mapped>
struct virtual_map : virtual_combined_map<Mapped(Key)> {
using key_type = Key;
using mapped_type = Mapped;
using value_type = std::pair<key_type,mapped_type>;
using virtual_combined_map<mapped_type(key_type)>::virtual_combined_map;
inline mapped_type operator[](const key_type& key) const noexcept(NO_EXCEPT) {
return this->_f(key);
}
};
}; // namesapce uni
#line 26 "structure/graph.hpp"
#line 2 "internal/auto_holder.hpp"
#line 5 "internal/auto_holder.hpp"
#line 2 "adaptor/map.hpp"
#line 7 "adaptor/map.hpp"
#line 11 "adaptor/map.hpp"
#line 2 "adaptor/gnu/hash_table.hpp"
#line 5 "adaptor/gnu/hash_table.hpp"
#include <stdexcept>
#include <ext/pb_ds/assoc_container.hpp>
#line 11 "adaptor/gnu/hash_table.hpp"
namespace uni {
namespace gnu {
template<class Base>
struct hash_table : Base {
using key_type = typename Base::key_type;
using value_type = typename Base::value_type;
using mapped_type = typename Base::mapped_type;
inline bool contains(const key_type& key) const noexcept(NO_EXCEPT) {
return this->Base::find(key) != this->Base::end();
}
template<class K, class T>
inline decltype(auto) emplace(K&& key, T&& val) noexcept(NO_EXCEPT) {
return this->Base::insert({ std::forward<K>(key), std::forward<T>(val) });
}
mapped_type& at(const key_type& key) {
auto itr = this->Base::find(key);
if(itr == this->Base::end()) throw std::out_of_range("hash_table::at()");
return itr->second;
};
const mapped_type& at(const key_type & key) const {
auto itr = this->Base::find(key);
if(itr == this->Base::end()) throw std::out_of_range("hash_table::at()");
return itr->second;
};
};
template<class Key, class T, class Hash = void>
struct cc_hash_table : hash_table<__gnu_pbds::cc_hash_table<Key, T, Hash>> {
using hash_table<__gnu_pbds::cc_hash_table<Key, T, Hash>>::hash_table;
};
template<class Key, class T>
struct cc_hash_table<Key, T, void> : hash_table<__gnu_pbds::cc_hash_table<Key, T>> {
using hash_table<__gnu_pbds::cc_hash_table<Key, T>>::hash_table;
};
template<class Key, class T, class Hash = void>
struct gp_hash_table : hash_table<__gnu_pbds::gp_hash_table<Key, T, Hash>> {
using hash_table<__gnu_pbds::gp_hash_table<Key, T, Hash>>::hash_table;
};
template<class Key, class T>
struct gp_hash_table<Key, T, void> : hash_table<__gnu_pbds::gp_hash_table<Key, T>> {
using hash_table<__gnu_pbds::gp_hash_table<Key, T>>::hash_table;
};
} // namespace gnu
} // namespace uni
#line 2 "adaptor/set.hpp"
#line 11 "adaptor/set.hpp"
#line 15 "adaptor/set.hpp"
#line 17 "adaptor/set.hpp"
namespace uni {
namespace internal {
template<class Set>
struct set_wrapper : Set {
using Set::Set;
using value_type = typename Set::value_type;
using size_type = internal::size_t;
template<class Key>
auto remove(Key&& key) noexcept(NO_EXCEPT) { return this->extract(std::forward<Key>(key)); }
inline auto ssize() const noexcept(NO_EXCEPT) { return std::ranges::ssize(*this); }
inline auto min_element() const noexcept(NO_EXCEPT) { return this->begin(); }
inline auto max_element() const noexcept(NO_EXCEPT) { return std::ranges::prev(this->end()); }
inline auto min() const noexcept(NO_EXCEPT) { return *this->begin(); }
inline auto max() const noexcept(NO_EXCEPT) { return *std::ranges::prev(this->end()); }
inline auto& pop_min() noexcept(NO_EXCEPT) { this->erase(this->begin()); return *this; }
inline auto& pop_max() noexcept(NO_EXCEPT) { this->erase(std::ranges::prev(this->end())); return *this; }
inline auto kth_smallest_element(const size_type k) const noexcept(NO_EXCEPT) {
return std::ranges::next(this->begin(), k);
}
inline auto kth_largest_element(const size_type k) const noexcept(NO_EXCEPT) {
return std::ranges::prev(this->end(), k + 1);
}
inline auto kth_smallest(const size_type k) const noexcept(NO_EXCEPT) {
return *std::ranges::next(this->begin(), k);
}
inline auto kth_largest(const size_type k) const noexcept(NO_EXCEPT) {
return *std::ranges::prev(this->end(), k + 1);
}
inline auto& pop_kth_smallest(const size_type k) const noexcept(NO_EXCEPT) {
return this->erase(std::ranges::next(this->begin(), k));
return *this;
}
inline auto& pop_kth_largest(const size_type k) const noexcept(NO_EXCEPT) {
return this->erase(std::ranges::prev(this->end(), k + 1));
return *this;
}
auto next_element(const typename Set::key_type& key, const size_type _count = 0) const noexcept(NO_EXCEPT) {
size_type count = std::abs(_count);
auto itr = this->lower_bound(key);
const auto begin = this->begin(), end = this->end();
if(itr == end) return this->end();
if(itr == begin) return this->begin();
while(count--) {
if(_count < 0) if(itr-- == begin) return this->begin();
if(_count > 0) if(++itr == end) return this->end();
}
return itr;
}
auto prev_element(const typename Set::key_type& key, const size_type _count = 0) const noexcept(NO_EXCEPT) {
size_type count = std::abs(_count);
auto itr = this->upper_bound(key);
const auto begin = this->begin(), end = this->end();
if(itr == end) return this->end();
if(itr-- == begin) return this->begin();
while(count--) {
if(_count < 0) if(itr-- == begin) return this->begin();
if(_count > 0) if(++itr == end) return this->end();
}
return itr;
}
std::optional<typename Set::value_type> next(const typename Set::key_type& key, size_type count = 0) const noexcept(NO_EXCEPT) {
if(this->empty()) return {};
auto itr = this->lower_bound(key);
const auto end = this->end();
if(itr == end) return {};
while(count--) if(++itr == end) return {};
return { *itr };
}
std::optional<typename Set::value_type> prev(const typename Set::key_type& key, size_type count = 0) const noexcept(NO_EXCEPT) {
if(this->empty()) return {};
auto itr = this->upper_bound(key);
const auto begin = this->begin();
if(itr-- == begin) return {};
while(count--) if(itr-- == begin) return {};
return { *itr };
}
template<class Rhs>
inline set_wrapper& operator|=(Rhs&& rhs) noexcept(NO_EXCEPT) {
set_wrapper res;
std::ranges::set_union(*this, std::forward<Rhs>(rhs), std::inserter(res, res.end()));
this->swap(res);
return *this;
}
template<class Rhs>
inline set_wrapper& operator&=(Rhs&& rhs) noexcept(NO_EXCEPT) {
set_wrapper res;
std::ranges::set_intersection(*this, std::forward<Rhs>(rhs), std::inserter(res, res.end()));
this->swap(res);
return *this;
}
template<class Rhs>
inline set_wrapper& operator^=(Rhs&& rhs) noexcept(NO_EXCEPT) {
set_wrapper res;
std::ranges::set_symmetric_difference(*this, std::forward<Rhs>(rhs), std::inserter(res, res.end()));
this->swap(res);
return *this;
}
template<class... Args>
inline set_wrapper operator|(set_wrapper<Args...> rhs) noexcept(NO_EXCEPT) {
return rhs |= *this;
}
template<class... Args>
inline set_wrapper operator&(set_wrapper<Args...> rhs) noexcept(NO_EXCEPT) {
return rhs &= *this;
}
template<class... Args>
inline set_wrapper operator^(set_wrapper<Args...> rhs) noexcept(NO_EXCEPT) {
return rhs ^= *this;
}
template<class... Args>
inline auto operator<=>(const set_wrapper<Args...>& rhs) const noexcept(NO_EXCEPT) {
const bool leq = this->size() <= rhs.size() && std::ranges::includes(rhs, *this);
const bool geq = rhs.size() <= this->size() && std::ranges::includes(*this, rhs);
if(leq) {
if(geq) return std::partial_ordering::equivalent;
return std::partial_ordering::less;
}
if(geq) return std::partial_ordering::greater;
return std::partial_ordering::unordered;
}
};
} //namespace internal
template<class... Args> using set = internal::set_wrapper<std::set<Args...>>;
template<class... Args> using unordered_set = internal::set_wrapper<std::unordered_set<Args...>>;
template<class... Args> using multiset = internal::set_wrapper<std::multiset<Args...>>;
template<class... Args> using unordered_multiset = internal::set_wrapper<std::unordered_multiset<Args...>>;
} // namespace uni
#line 14 "adaptor/map.hpp"
namespace uni {
namespace internal {
template<class Map>
using map_wrapper_base = set_wrapper<Map>;
template<class Map> struct map_wrapper : map_wrapper_base<Map> {
private:
using base = map_wrapper_base<Map>;
public:
using base::base;
using mapped_type = typename base::mapped_type;
using key_type = typename base::key_type;
protected:
using default_func_noarg_type = std::function<mapped_type(void)>;
using default_func_type = std::function<mapped_type(key_type)>;
int _default_type = 0;
mapped_type _default_val = mapped_type();
default_func_noarg_type _default_func_noarg;
default_func_type _default_func;
inline mapped_type _get_default(const key_type& key) const noexcept(NO_EXCEPT) {
if(this->_default_type == 0) return this->_default_val;
if(this->_default_type == 1) return this->_default_func_noarg();
if(this->_default_type == 2) return this->_default_func(key);
else assert(false);
}
public:
inline auto& set_default(const mapped_type& val) noexcept(NO_EXCEPT) {
this->_default_val = val;
this->_default_type = 0;
return *this;
}
inline auto& set_default(const default_func_noarg_type func) noexcept(NO_EXCEPT) {
this->_default_func_noarg = func;
this->_default_type = 1;
return *this;
}
inline auto& set_default(const default_func_type func) noexcept(NO_EXCEPT) {
this->_default_func = func;
this->_default_type = 2;
return *this;
}
inline auto& operator[](const key_type& key) noexcept(NO_EXCEPT) {
auto found = this->base::find(key);
if(found == this->base::end()) return this->base::emplace(key, this->_get_default(key)).first->second;
return found->second;
}
inline auto& operator()(const key_type& key) noexcept(NO_EXCEPT) {
return this->base::operator[](key);
}
inline std::optional<mapped_type> get(const key_type& key) const noexcept(NO_EXCEPT) {
const auto found = this->base::find(key);
if(found == this->base::end()) return {};
return found->second;
}
};
} // namespace internal
template<class... Args> using map = internal::map_wrapper<std::map<Args...>>;
template<class... Args> using unordered_map = internal::map_wrapper<std::unordered_map<Args...>>;
template<class... Args> using multimap = internal::map_wrapper<std::multimap<Args...>>;
template<class... Args> using unordered_multimap = internal::map_wrapper<std::unordered_multimap<Args...>>;
template<class... Args> using cc_hash_table = internal::map_wrapper<gnu::cc_hash_table<Args...>>;
template<class... Args> using gp_hash_table = internal::map_wrapper<gnu::gp_hash_table<Args...>>;
} // namespace uni
#line 9 "internal/auto_holder.hpp"
#line 11 "internal/auto_holder.hpp"
namespace uni {
namespace internal {
namespace auto_holder_impl {
template<class T, bool DYNAMIC, class = std::enable_if_t<std::is_integral_v<T> && not DYNAMIC>>
constexpr int _holder_type(resolving_rank<2>) { return 0; }
template<class T, bool>
constexpr auto _holder_type(resolving_rank<1>) -> decltype(std::unordered_set<T>(), 0){ return 1; }
template<class T, bool>
constexpr int _holder_type(resolving_rank<0>) { return 2; }
template<class T, bool DYNAMIC = false>
constexpr int holder_type = _holder_type<T,DYNAMIC>(resolving_rank<10>{});
template<class,class,int> struct holder {};
template<class T, class U>
struct holder<T, U, 0> : vector<U> {
using vector<U>::vector;
};
template<class T, class U>
struct holder<T, U, 1> : gp_hash_table<T, U> {
using gp_hash_table<T, U>::gp_hash_table;
template<class V> inline void assign(const internal::size_t, const V& v) { this->set_default(v); }
};
template<class T, class U>
struct holder<T, U, 2> : map<T, U> {
using map<T, U>::map;
template<class V> inline void assign(const internal::size_t, const V& v) { this->set_default(v); }
};
} // namespace auto_holder_impl
} // namespace internal
template<class T, class U> struct auto_holder : internal::auto_holder_impl::holder<T,U,internal::auto_holder_impl::holder_type<T>> {
using internal::auto_holder_impl::holder<T,U,internal::auto_holder_impl::holder_type<T>>::holder;
};
template<class T, class U> struct dynamic_auto_holder : internal::auto_holder_impl::holder<T,U,internal::auto_holder_impl::holder_type<T,true>> {
using internal::auto_holder_impl::holder<T,U,internal::auto_holder_impl::holder_type<T,true>>::holder;
};
} // namespace uni
#line 28 "structure/graph.hpp"
namespace uni {
namespace internal {
namespace graph_impl {
template<class Node,class Cost> struct edge {
private:
inline static internal::size_t unique() noexcept(NO_EXCEPT) { static internal::size_t id = 0; return id++; }
public:
using cost_type = Cost;
using node_type = Node;
using size_type = internal::size_t;
const size_type id = unique();
const node_type from, to; const Cost cost;
const size_type index = 0;
edge(const node_type u, const node_type v, const Cost w = 1, const size_type i = 0) noexcept(NO_EXCEPT)
: from(u), to(v), cost(w), index(i)
{}
operator node_type() const noexcept(NO_EXCEPT) { return this->to; }
inline node_type opposite(const node_type v) const noexcept(NO_EXCEPT) {
if(this->from == v) return this->to;
if(this->to == v) return this->from;
assert(false);
}
auto _debug() const { return std::make_tuple(index, from, to, cost); };
friend bool operator==(const edge& lhs, const edge& rhs) noexcept(NO_EXCEPT) { return lhs.id == rhs.id; }
friend bool operator!=(const edge& lhs, const edge& rhs) noexcept(NO_EXCEPT) { return lhs.id != rhs.id; }
};
template<class NodeType, class CostType, class EdgeCollector>
struct regular_base : EdgeCollector {
using EdgeCollector::EdgeCollector;
using size_type = internal::size_t;
using node_type = NodeType;
using cost_type = CostType;
inline size_type size() const noexcept(NO_EXCEPT) { return static_cast<size_type>(this->EdgeCollector::size()); }
};
template<class NodeType, class CostType, class Map>
struct virtual_base : Map {
public:
using size_type = internal::size_t;
using node_type = NodeType;
using cost_type = CostType;
protected:
size_type _n = 0;
public:
template<class F>
explicit virtual_base(const size_type n, F&& f) noexcept(NO_EXCEPT)
: Map(std::forward<F>(f)), _n(n)
{}
inline size_type size() const noexcept(NO_EXCEPT) { return this->_n; }
};
template<class NodeType, class CostType, template<class...> class Container>
struct regular_core : regular_base<NodeType,CostType,Container<vector<internal::graph_impl::edge<NodeType,CostType>>>> {
using size_type = internal::size_t;
using node_type = NodeType;
using cost_type = CostType;
using edge_type = typename internal::graph_impl::edge<node_type,cost_type>;
enum class edge_kind { undirected, directed };
private:
using base = regular_base<NodeType,CostType,Container<vector<edge_type>>>;
size_type _directed_edge_count = 0, _undirected_edge_count = 0;
Container<edge_type> _edges;
Container<size_type> _out_degs, _in_degs;
protected:
inline void _add_edge(const size_type u, const size_type v, const cost_type w, const size_type k) noexcept(NO_EXCEPT) {
this->operator[](u).emplace_back(u, v, w, k);
++_out_degs[u], ++_in_degs[v];
++this->_directed_edge_count;
}
public:
explicit regular_core() noexcept(NO_EXCEPT) : base() {}
explicit regular_core(const size_type n = 0) noexcept(NO_EXCEPT)
: base(n), _out_degs(n), _in_degs(n)
{}
auto& clear() noexcept(NO_EXCEPT) {
this->_directed_edge_count = 0, this->_undirected_edge_count = 0;
this->base::clear(), this->_edges.clear();
this->_out_degs.clear(), this->_in_degs.clear();
return *this;
}
auto& resize(const size_type n) noexcept(NO_EXCEPT) {
this->base::resize(n), this->_out_degs.resize(n), this->_in_degs.resize(n);
return *this;
}
inline const auto& edges() const noexcept(NO_EXCEPT) { return this->_edges; }
inline const auto& edge(const size_type k) const noexcept(NO_EXCEPT) { return this->_edges[k]; }
inline const auto& degrees() const noexcept(NO_EXCEPT) { return this->_in_degs; }
inline const auto& degree(const size_type k) const noexcept(NO_EXCEPT) { return this->_in_degs[k]; }
inline const auto& in_degrees() const noexcept(NO_EXCEPT) { return this->_in_degs; }
inline const auto& in_degree(const size_type k) const noexcept(NO_EXCEPT) { return this->_in_degs[k]; }
inline const auto& out_degrees() const noexcept(NO_EXCEPT) { return this->_out_degs; }
inline const auto& out_degree(const size_type k) const noexcept(NO_EXCEPT) { return this->_out_degs[k]; }
inline size_type directed_edges_count() const noexcept(NO_EXCEPT) { return this->_directed_edge_count; }
template<class R = valgrid<bool>>
auto make_has_edges() const noexcept(NO_EXCEPT) {
R res(this->size(), this->size(), false);
REP(i, this->size()) ITR(j, this->operator[](i)) res[i][j] = true;
return res;
}
template<bool SELF_ZERO = true, class T = cost_type, class R = valgrid<T>>
auto make_initial_distance_matrix() const noexcept(NO_EXCEPT) {
R res(this->size(), this->size(), numeric_limits<T>::arithmetic_infinity());
if constexpr(SELF_ZERO) REP(i, this->size()) res[i][i] = 0;
REP(i, this->size()) ITR(j, this->operator[](i)) res[i][j] = j.cost;
return res;
}
template<bool SELF_ZERO = true, class T = cost_type, class R = valgrid<T>>
auto make_distance_matrix() const noexcept(NO_EXCEPT) {
R res = this->make_initial_distance_matrix<SELF_ZERO,T,R>();
REP(k, this->size()) REP(i, this->size()) REP(j, this->size()) {
chmin(res[i][j], res[i][k] + res[k][j]);
}
return res;
}
template<edge_kind EDGE_TYPE = edge_kind::directed>
auto add_edge(const node_type u, const node_type v, const cost_type w = 1) noexcept(NO_EXCEPT) {
assert(0 <= u and u < this->size()), assert(0 <= v and v < this->size());
const size_type k = this->edges().size();
this->_edges.emplace_back(u, v, w, k);
this->_add_edge(u, v, w, k);
if constexpr(EDGE_TYPE == edge_kind::undirected) this->_add_edge(v, u, w, k);
return k;
}
inline auto add_edge_bidirectionally(const node_type u, const node_type v, const cost_type w = 1) noexcept(NO_EXCEPT) {
return this->add_edge<edge_kind::undirected>(u, v, w);
}
template<bool WEIGHTED = false, bool ONE_ORIGIN = true, const edge_kind EDGE_TYPE = edge_kind::directed, class Stream = input_adaptor<>>
void read(const size_type edges, Stream *const ist = &_input) noexcept(NO_EXCEPT) {
REP(edges) {
node_type u, v; cost_type w = 1; *ist >> u >> v; if(ONE_ORIGIN) --u, --v;
if(WEIGHTED) *ist >> w;
this->add_edge<EDGE_TYPE>(u, v, w);
}
}
template<bool WEIGHTED = false, bool ONE_ORIGIN = true, class Stream = input_adaptor<>>
void read_bidirectionally(const size_type edges, Stream *const ist = &_input) noexcept(NO_EXCEPT) {
REP(edges) {
node_type u, v; cost_type w = 1; *ist >> u >> v; if(ONE_ORIGIN) --u, --v;
if(WEIGHTED) *ist >> w;
this->add_edge<edge_kind::undirected>(u, v, w);
}
}
};
template<class Graph>
struct mixin : Graph {
using Graph::Graph;
using size_type = typename Graph::size_type;
using node_type = typename Graph::node_type;
using cost_type = typename Graph::cost_type;
inline size_type vertices() const noexcept(NO_EXCEPT) { return static_cast<size_type>(this->Graph::size()); }
public:
// graph/shortest_path.hpp
template<item_or_convertible_range<node_type> Source, class Dist, class Prev = std::nullptr_t>
void shortest_path_without_cost(Source&&, Dist *const, Prev *const = nullptr, const node_type& = -1, const node_type& = -2) const noexcept(NO_EXCEPT);
template<item_or_convertible_range<node_type> Source>
auto shortest_path_without_cost(Source&&) const noexcept(NO_EXCEPT);
// graph/dijkstra.hpp
template<item_or_convertible_range<node_type> Source, class Dist, class Prev = std::nullptr_t>
void shortest_path_with_01cost(Source&&, Dist *const, Prev *const = nullptr, const node_type& = -1, const node_type& = -2) const noexcept(NO_EXCEPT);
template<item_or_convertible_range<node_type> Source>
auto shortest_path_with_01cost(Source&&) const noexcept(NO_EXCEPT);
// graph/dijkstra.hpp
template<item_or_convertible_range<node_type> Source, class Dist, class Prev = std::nullptr_t>
void shortest_path_with_cost(Source&&, Dist *const, Prev *const = nullptr, const node_type& = -1, const node_type& = -2) const noexcept(NO_EXCEPT);
template<item_or_convertible_range<node_type> Source>
auto shortest_path_with_cost(Source&&) const noexcept(NO_EXCEPT);
// graph/topological_sort.hpp
bool sort_topologically(vector<node_type> *const ) const noexcept(NO_EXCEPT);
bool sort_topologically() const noexcept(NO_EXCEPT);
// graph/topological_sort.hpp
template<class> bool sort_topologically_with_priority(vector<node_type> *const) const noexcept(NO_EXCEPT);
template<class> bool sort_topologically_with_priority() const noexcept(NO_EXCEPT);
// graph/minimum_paph_cover.hpp
size_type minimum_paph_cover_size_as_dag() const noexcept(NO_EXCEPT);
// graph/spanning_tree_cost.hpp
auto minimum_spanning_tree(mixin *const = nullptr) const noexcept(NO_EXCEPT);
// graph/spanning_tree_cost.hpp
auto maximum_spanning_tree(mixin *const = nullptr) const noexcept(NO_EXCEPT);
// graph/reachability.hpp
template<std::ranges::sized_range R>
auto test_reachability(R&&) const noexcept(NO_EXCEPT);
// graph/connected_components.hpp
disjoint_set components() const noexcept(NO_EXCEPT);
// graph/connected_components.hpp
bool is_bipartite() const noexcept(NO_EXCEPT);
// graph/connected_components.hpp
template<class Colors>
bool is_bipartite(Colors *const) const noexcept(NO_EXCEPT);
// graph/parse_grid.hpp
template<bool = false, class G, class U = char>
void parse_grid(const G&, U = '.') noexcept(NO_EXCEPT);
// graph/manhattan_minimum_spanning_tree.hpp
template<
std::input_iterator I0, std::input_iterator I1,
std::sentinel_for<I0> S0, std::sentinel_for<I1> S1
>
cost_type build_manhattan_mst(I0, S0, I1, S1) noexcept(NO_EXCEPT);
};
} // namespace graph_impl
} // namespace internal
template<class Cost = std::int64_t, class Node = internal::size_t, template<class...> class Container = vector>
struct graph : internal::graph_impl::mixin<internal::graph_impl::regular_core<Node, Cost, Container>> {
private:
using base = internal::graph_impl::mixin<internal::graph_impl::regular_core<Node, Cost, Container>>;
public:
using size_type = typename base::size_type;
using node_type = typename base::node_type;
using edge = typename internal::graph_impl::edge<node_type,Cost>;
explicit graph(const size_type n = 0) noexcept(NO_EXCEPT) : base(n) {}
};
template<class Node = internal::size_t, class Cost = std::int64_t, class Edges = virtual_map<Node, vector<typename internal::graph_impl::edge<Node, Cost>>>>
struct virtual_graph : internal::graph_impl::mixin<internal::graph_impl::virtual_base<Node, Cost, Edges>> {
private:
using base = internal::graph_impl::mixin<internal::graph_impl::virtual_base<Node, Cost, Edges>>;
public:
using size_type = typename base::size_type;
using edge = typename internal::graph_impl::edge<Node, Cost>;
private:
size_type _n = 0;
public:
template<class F>
explicit virtual_graph(F&& f, const size_type n = 0) noexcept(NO_EXCEPT)
: base(n, std::forward<F>(f)), _n(n)
{}
};
} // namespace uni
#line 9 "graph/centroid_decomposition.hpp"
namespace uni {
// Thanks to: https://qiita.com/drken/items/4b4c3f1824339b090202
template<class Graph = graph<>>
struct centroid_decomposition {
using size_type = internal::size_t;
std::vector<size_type> centroids;
private:
const Graph& graph;
std::vector<size_type> _size, _parent;
std::vector<bool> _used;
public:
centroid_decomposition(const Graph& _graph) noexcept(NO_EXCEPT)
: graph(_graph),
_size(graph.vertices()), _parent(graph.vertices()), _used(graph.vertices())
{}
inline const auto& sizes() const noexcept(NO_EXCEPT) { return this->_size; }
inline const auto& parents() const noexcept(NO_EXCEPT) { return this->_parent; }
inline const auto& used() const noexcept(NO_EXCEPT) { return this->_used; }
inline size_type size(const size_type v) const noexcept(NO_EXCEPT) {
assert(0 <= v && v < this->graph.vertices());
return this->_size[v];
}
inline size_type parent(const size_type v) const noexcept(NO_EXCEPT) {
assert(0 <= v && v < this->graph.vertices());
return this->_parent[v];
}
inline bool used(const size_type v) const noexcept(NO_EXCEPT) {
assert(0 <= v && v < this->graph.vertices());
return this->_used[v];
}
const std::vector<size_type>& find(const size_type v, const size_type sz, const size_type p = -1) noexcept(NO_EXCEPT) {
assert(not this->_used[v]);
this->_size[v] = 1, this->_parent[v] = p;
bool found = true;
ITR(e, this->graph[v]) {
if(e.to == p) continue;
if(this->_used[e.to]) continue;
this->find(e.to, sz, v);
if(this->_size[e.to] > sz / 2) found = false;
this->_size[v] += this->_size[e.to];
}
if(sz - this->_size[v] > sz / 2) found = false;
if(found) this->centroids.push_back(v);
return this->centroids;
}
auto decompose(const size_type root, const size_type sz) noexcept(NO_EXCEPT) {
assert(not this->_used[root]);
std::vector<std::pair<size_type,size_type>> subtrees;
this->centroids.clear();
this->find(root, sz);
const size_type centroid = this->centroids[0];
this->_used[centroid] = true;
ITR(e, this->graph[centroid]) {
if(this->_used[e.to]) continue;
if(e.to == this->_parent[centroid]) {
subtrees.emplace_back(e.to, sz - this->_size[centroid]);
}
else {
subtrees.emplace_back(e.to, this->_size[e.to]);
}
}
return std::make_pair(centroid, subtrees);
}
auto decompose(const size_type root = 0) noexcept(NO_EXCEPT) {
return this->decompose(root, this->graph.vertices());
}
};
} // namespace uni
#line 2 "graph/centroid_path_decomposition.hpp"
#line 7 "graph/centroid_path_decomposition.hpp"
#line 9 "graph/centroid_path_decomposition.hpp"
#line 12 "graph/centroid_path_decomposition.hpp"
#line 14 "graph/centroid_path_decomposition.hpp"
namespace uni {
// Thanks to: https://kazuma8128.hatenablog.com/entry/2018/07/16/010500#fn-96e76557
class centroid_path_decomposition {
using size_type = internal::size_t;
private:
std::vector<std::vector<size_type>> graph;
public:
std::vector<size_type> in, out, size, head, parent;
private:
size_type _cur = 0;
void _erase_parent(const size_type v, const size_type p) noexcept(NO_EXCEPT) {
this->parent[v] = p;
ITRR(nv, graph[v]) {
if(nv == this->graph[v].back()) break;
if(nv == p) std::swap(nv, this->graph[v].back());
this->_erase_parent(nv, v);
}
this->graph[v].pop_back();
}
void _race_size(const size_type v) noexcept(NO_EXCEPT) {
ITRR(nv, this->graph[v]) {
this->_race_size(nv);
this->size[v] += this->size[nv];
if(this->size[nv] > this->size[this->graph[v].front()]) std::swap(nv, this->graph[v].front());
}
}
void _race_path(const size_type v) noexcept(NO_EXCEPT) {
this->in[v] = this->_cur++;
ITR(nv, this->graph[v]) {
this->head[nv] = (nv == this->graph[v].front() ? this->head[v] : nv);
this->_race_path(nv);
}
this->out[v] = this->_cur;
}
public:
template<class Graph>
centroid_path_decomposition(const Graph& _graph, const size_type root = 0) noexcept(NO_EXCEPT)
: graph(_graph.size()), in(_graph.size(), -1), out(_graph.size(), -1), size(_graph.size(), 1), head(_graph.size()), parent(_graph.size(), -1)
{
REP(v, _graph.size()) ITR(nv, _graph[v]) { this->graph[v].push_back(nv); }
this->build(root);
}
void build(const size_type root = 0) noexcept(NO_EXCEPT) {
ITR(v, this->graph[root]) this->_erase_parent(v, root);
this->_race_size(root);
this->head[root] = root;
this->_race_path(root);
}
size_type id(const size_type v) noexcept(NO_EXCEPT) { return this->in[v]; }
size_type lca(size_type u, size_type v) const noexcept(NO_EXCEPT) {
while(true) {
if(this->in[u] > this->in[v]) std::swap(u, v);
if(this->head[u] == this->head[v]) return u;
v = this->parent[this->head[v]];
}
}
template<class F>
void edges_on_path(size_type u, size_type v, F&& f) noexcept(NO_EXCEPT) {
while(true) {
if(this->in[u] > this->in[v]) std::swap(u, v);
if(this->head[u] != this->head[v]) {
f(this->in[this->head[v]] - 1, this->in[v]);
v = this->parent[this->head[v]];
} else {
if(u != v) f(this->in[u], this->in[v]);
break;
}
}
}
template<class F>
void nodes_on_path(size_type u, size_type v, F&& f) noexcept(NO_EXCEPT) {
while (true) {
if (this->in[u] > this->in[v]) std::swap(u, v);
f(std::max(this->in[this->head[v]], this->in[u]), this->in[v]);
if (this->head[u] != this->head[v])
v = this->parent[this->head[v]];
else {
break;
}
}
}
template<class F>
void subtree(const size_type v, F&& f) noexcept(NO_EXCEPT) { f(this->in[v], this->out[v]); }
};
} // namespace uni
#line 2 "graph/connected_components.hpp"
#line 5 "graph/connected_components.hpp"
#line 7 "graph/connected_components.hpp"
#line 11 "graph/connected_components.hpp"
template<class Graph>
uni::disjoint_set uni::internal::graph_impl::mixin<Graph>::components() const noexcept(NO_EXCEPT) {
uni::disjoint_set disjoint_set(this->vertices());
ITR(edges, *this) ITR(_id, u, v, _w, _idx, edges) {
disjoint_set.merge(u, v);
}
return disjoint_set;
}
#line 2 "graph/is_bipartite.hpp"
#line 6 "graph/is_bipartite.hpp"
#line 8 "graph/is_bipartite.hpp"
#line 11 "graph/is_bipartite.hpp"
template<class Graph>
bool uni::internal::graph_impl::mixin<Graph>::is_bipartite() const noexcept(NO_EXCEPT) {
valarray<std::int8_t> color(0, this->vertices());
this->is_bipartite(&color);
return true;
}
template<class Graph>
template<class Colors>
bool uni::internal::graph_impl::mixin<Graph>::is_bipartite(Colors *const color) const noexcept(NO_EXCEPT) {
color->assign(this->vertices(), 0);
REP(s, this->vertices()) {
if(color->operator[](s) != 0) continue;
std::stack<size_type> stack;
stack.push(s);
color->operator[](s) = 1;
while(not stack.empty()) {
auto v = stack.top(); stack.pop();
auto c = color->operator[](v);
ITR(nv, this->operator[](v)) {
if(color->operator[](nv) == c) return false;
if(color->operator[](nv) == 0) {
color->operator[](nv) = -c;
stack.push(nv);
}
}
}
}
return true;
}
#line 2 "graph/lowest_common_ancestor.hpp"
#line 5 "graph/lowest_common_ancestor.hpp"
#line 8 "graph/lowest_common_ancestor.hpp"
#line 11 "graph/lowest_common_ancestor.hpp"
#line 14 "graph/lowest_common_ancestor.hpp"
#line 16 "graph/lowest_common_ancestor.hpp"
namespace uni {
template<class Graph>
struct lowest_common_ancestor {
using size_type = internal::size_t;
using graph_type = Graph;
using edge_type = typename graph_type::edge_type;
using cost_type = typename graph_type::cost_type;
valarray<valarray<size_type>> parent;
valarray<size_type> depth;
valarray<cost_type> cost;
private:
void dfs(const graph_type &G, const edge_type& e) noexcept(NO_EXCEPT) {
this->parent[0][e.to] = e.from;
if(e.from >= 0) {
this->depth[e.to] = this->depth[e.from] + 1;
this->cost[e.to] = this->cost[e.from] + e.cost;
}
ITR(f, G[e.to]) {
if(f.to != e.from) dfs(G, f);
}
}
public:
lowest_common_ancestor(const graph_type &G, const size_type root = 0) noexcept(NO_EXCEPT) { this->init(G, root); }
void init(const graph_type &G, const size_type root = 0) noexcept(NO_EXCEPT) {
const size_type n = static_cast<size_type>(G.size());
const size_type d = std::bit_width<std::make_unsigned_t<size_type>>(n);
this->parent.assign(d, valarray<size_type>(n, -1));
this->depth.assign(n, 0), this->cost.assign(n, 0);
this->dfs(G, edge_type(-1, root, 0));
REP(k, d-1) REP(v, n) {
if(this->parent[k][v] < 0) this->parent[k+1][v] = -1;
else this->parent[k+1][v] = this->parent[k][this->parent[k][v]];
}
}
size_type operator()(const size_type u, const size_type v) const noexcept(NO_EXCEPT) {
return this->find(u, v);
}
size_type find(size_type u, size_type v) const noexcept(NO_EXCEPT) {
if(this->depth[u] < this->depth[v]) std::swap(u, v);
size_type d = static_cast<size_type>(this->parent.size());
REP(k, d) {
if((this->depth[u] - this->depth[v]) >> k & 1) u = this->parent[k][u];
}
if(u == v) return u;
REPD(k, d) {
if(this->parent[k][u] != this->parent[k][v]) {
u = this->parent[k][u];
v = this->parent[k][v];
}
}
return this->parent[0][u];
}
size_type path_length(const size_type u, const size_type v) const noexcept(NO_EXCEPT) {
return this->depth[u] + this->depth[v] - 2 * this->depth[find(u, v)];
}
size_type distance(const size_type u, const size_type v) const noexcept(NO_EXCEPT) {
return this->cost[u] + this->cost[v] - 2 * this->cost[find(u, v)];
}
};
} // namespace uni
#line 2 "graph/manhattan_minimum_spanning_tree.hpp"
#line 9 "graph/manhattan_minimum_spanning_tree.hpp"
#line 12 "graph/manhattan_minimum_spanning_tree.hpp"
#line 15 "graph/manhattan_minimum_spanning_tree.hpp"
#line 17 "graph/manhattan_minimum_spanning_tree.hpp"
#line 19 "graph/manhattan_minimum_spanning_tree.hpp"
#line 2 "graph/spanning_tree.hpp"
#line 6 "graph/spanning_tree.hpp"
#line 8 "graph/spanning_tree.hpp"
namespace uni {
namespace internal {
namespace graph_impl {
template<class G, template<class...> class Compare, class Cost, class Size>
std::optional<Cost> kruskal(const G& graph, const Compare<std::tuple<Cost, Size, Size>> compare, G *const mst = nullptr) noexcept(NO_EXCEPT) {
disjoint_set ds(graph.size());
std::vector<std::tuple<Cost, Size, Size>> edges;
REP(u, graph.size()) ITR(e, graph[u]) {
edges.emplace_back(e.cost, u, e.to);
}
std::ranges::sort(edges, compare);
if(mst) mst->clear(), mst->resize(graph.size());
Cost res = 0;
typename G::size_type cnt = 0;
ITR(w, u, v, edges) {
if(not ds.same(u, v)) {
ds.merge(u, v);
if(mst) mst->add_edge_bidirectionally(u, v, w);
res += w;
++cnt;
}
}
assert(cnt <= graph.size() - 1);
if(cnt != graph.size() - 1) return {};
return res;
}
} // namespace graph_impl
} // namespace internal
} // namespace uni
template<class Graph>
inline auto uni::internal::graph_impl::mixin<Graph>::minimum_spanning_tree(internal::graph_impl::mixin<Graph> *const mst) const noexcept(NO_EXCEPT) {
return
uni::internal::graph_impl::kruskal<
uni::internal::graph_impl::mixin<Graph>,
std::less, cost_type, size_type
>(*this, {}, mst);
}
template<class Graph>
inline auto uni::internal::graph_impl::mixin<Graph>::maximum_spanning_tree(internal::graph_impl::mixin<Graph> *const mst) const noexcept(NO_EXCEPT) {
return
uni::internal::graph_impl::kruskal<
uni::internal::graph_impl::mixin<Graph>,
std::less, cost_type, size_type
>(*this, {}, mst);
}
#line 22 "graph/manhattan_minimum_spanning_tree.hpp"
namespace uni {
// TODO: Vector View
template <
std::input_iterator I0, std::input_iterator I1,
std::sentinel_for<I0> S0, std::sentinel_for<I1> S1
>
auto manhattan_mst_candidate_edges(
I0 x_first, S0 x_last, I1 y_first, S1 y_last
) noexcept(NO_EXCEPT) {
using size_type = internal::size_t;
using cost_type = std::common_type_t<std::iter_value_t<I0>, std::iter_value_t<I1>>;
std::vector<cost_type> xs(x_first, x_last), ys(y_first, y_last);
assert(xs.size() == ys.size());
std::vector<size_type> indices(xs.size());
std::iota(ALL(indices), 0);
vector<std::tuple<size_type, size_type, cost_type>> res;
REP(_0, 2) {
REP(_1, 2) {
std::ranges::sort(indices, [&](const auto i, const auto j) { return xs[i] + ys[i] < xs[j] + ys[j]; });
std::map<cost_type,size_type> scan;
ITR(i, indices) {
for(auto itr = scan.lower_bound(-ys[i]); itr!=scan.end(); itr=scan.erase(itr)) {
const auto j = itr->second;
if(xs[i] - xs[j] < ys[i] - ys[j]) break;
res.emplace_back(i, j, std::abs(xs[i] - xs[j]) + std::abs(ys[i] - ys[j]));
}
scan[-ys[i]] = i;
}
std::swap(xs, ys);
}
ITRR(x, xs) x *= -1;
}
std::ranges::sort(res, [&](const auto& p, const auto& q) { return std::get<2>(p) < std::get<2>(q); });
return res;
}
template <
std::input_iterator I0, std::input_iterator I1,
std::sentinel_for<I0> S0, std::sentinel_for<I1> S1
>
auto manhattan_mst_edges(
I0 x_first, S0 x_last, I1 y_first, S1 y_last,
std::common_type_t<std::iter_value_t<I0>, std::iter_value_t<I1>> *const cost_sum = nullptr
) noexcept(NO_EXCEPT) {
using cost_type = std::common_type_t<std::iter_value_t<I0>, std::iter_value_t<I1>>;
using size_type = internal::size_t;
assert(std::ranges::distance(x_first, x_last) == std::ranges::distance(y_first, y_last));
if(cost_sum) *cost_sum = 0;
vector<std::tuple<size_type, size_type, cost_type>> res;
disjoint_set uf(std::ranges::distance(x_first, x_last));
ITR(u, v, w, (manhattan_mst_candidate_edges<I0,I1>(x_first, x_last, y_first, y_last))) {
if(not uf.same(u, v)) {
uf.merge(u, v);
res.emplace_back(u, v, w);
if(cost_sum) *cost_sum += w;
}
}
return res;
}
template<class Graph>
template<
std::input_iterator I0, std::input_iterator I1,
std::sentinel_for<I0> S0, std::sentinel_for<I1> S1
>
typename Graph::cost_type internal::graph_impl::mixin<Graph>::build_manhattan_mst(
I0 x_first, S0 x_last, I1 y_first, S1 y_last
) noexcept(NO_EXCEPT)
{
assert(std::ranges::distance(x_first, x_last) == std::ranges::distance(y_first, y_last));
cost_type res = 0;
const auto edges = manhattan_mst_edges<I0, I1, S0, S1>(x_first, x_last, y_first, y_last);
ITR(u, v, w, edges) {
this->add_edge_bidirectionally(u, v, w);
}
return res;
}
} // namespace uni
#line 2 "graph/maximum_bipartite_matching.hpp"
#include <atcoder/maxflow>
#line 9 "graph/maximum_bipartite_matching.hpp"
#line 12 "graph/maximum_bipartite_matching.hpp"
#line 14 "graph/maximum_bipartite_matching.hpp"
namespace uni {
struct maximum_bipartite_matching {
// using size_type = internal::size_t;
using size_type = int;
protected:
using MF = atcoder::mf_graph<size_type>;
size_type _m, _n, _s, _edges = 0;
MF _mf;
public:
explicit maximum_bipartite_matching(const size_type n) noexcept(NO_EXCEPT) : maximum_bipartite_matching(n, n) {}
maximum_bipartite_matching(const size_type m, const size_type n) noexcept(NO_EXCEPT)
: _m(m), _n(n), _s(m + n), _mf(m + n + 2)
{
REP(i, m) {
this->_mf.add_edge(this->_s, i, 1);
}
REP(i, n) {
this->_mf.add_edge(m + i, this->_s + 1, 1);
}
}
inline auto& add(const size_type i, const size_type j) noexcept(NO_EXCEPT) {
assert(0 <= i && i < this->_m);
assert(0 <= j && j < this->_n);
this->_mf.add_edge(i, this->_m + j, 1);
++this->_edges;
return *this;
}
inline size_type max_matched() noexcept(NO_EXCEPT) {
return this->_mf.flow(this->_s, this->_s + 1);
}
inline auto get_matching() noexcept(NO_EXCEPT) {
this->max_matched();
vector<spair<size_type>> res;
REP(i, this->_edges) {
const auto edge = this->_mf.get_edge(this->_s + i);
if(edge.flow == 0) continue;
res.emplace_back(edge.from, edge.to - this->_m);
}
return res;
}
};
} // namespace uni
#line 2 "graph/minimum_paph_cover.hpp"
#include <memory>
#line 8 "graph/minimum_paph_cover.hpp"
#line 11 "graph/minimum_paph_cover.hpp"
template<class Graph>
typename uni::internal::graph_impl::mixin<Graph>::size_type uni::internal::graph_impl::mixin<Graph>::minimum_paph_cover_size_as_dag() const noexcept(NO_EXCEPT) {
uni::maximum_bipartite_matching bm(this->size());
REP(i, this->size()) ITR(j, (*this)[i]) {
bm.add(i, j.to);
}
return this->size() - bm.max_matched();
}
#line 2 "graph/parse_grid.hpp"
#line 4 "graph/parse_grid.hpp"
#line 7 "graph/parse_grid.hpp"
template<class Graph>
template<bool REV, class G, class U>
void uni::internal::graph_impl::mixin<Graph>::parse_grid(const G &grid, U available) noexcept(NO_EXCEPT) {
this->clear();
this->resize(grid.height() * grid.width());
REP(i, grid.height()) REP(j, grid.width()) {
if(REV ^ (grid(i, j) != available)) continue;
if(i+1 < grid.height() and (REV ^ (grid(i+1, j) == available))) {
this->template add_edge_bidirectionally(grid.id(i, j), grid.id(i+1, j));
}
if(j+1 < grid.width() and (REV ^ (grid(i, j+1) == available))) {
this->template add_edge_bidirectionally(grid.id(i, j), grid.id(i, j+1));
}
}
}
#line 2 "graph/reachability_test.hpp"
#line 6 "graph/reachability_test.hpp"
#line 10 "graph/reachability_test.hpp"
#line 12 "graph/reachability_test.hpp"
#line 2 "graph/topological_sort.hpp"
#line 6 "graph/topological_sort.hpp"
#line 10 "graph/topological_sort.hpp"
template<class Graph>
template<class comparer>
bool uni::internal::graph_impl::mixin<Graph>::sort_topologically_with_priority(uni::vector<node_type> *const sorted) const noexcept(NO_EXCEPT) {
sorted->clear();
std::vector<size_type> in_degs(this->size());
ITR(v, *this) ITR(e, v) ++in_degs[e.to];
std::priority_queue<node_type,std::vector<node_type>,comparer> que;
REP(i, this->size()) if(in_degs[i] == 0) que.push(i);
while(not que.empty()) {
const node_type v = que.top(); que.pop();
ITR(u, (*this)[v]) if(!(--in_degs[u.to])) que.push(u.to);
sorted->push_back(v);
}
return std::ranges::ssize(*sorted) == std::ranges::ssize(*this);
}
template<class Graph>
template<class comparer>
bool uni::internal::graph_impl::mixin<Graph>::sort_topologically_with_priority() const noexcept(NO_EXCEPT) {
uni::vector<node_type> vs;
return this->sort_topologically_with_priority<comparer>(&vs);
}
template<class Graph>
bool uni::internal::graph_impl::mixin<Graph>::sort_topologically(uni::vector<node_type> *const sorted) const noexcept(NO_EXCEPT) {
sorted->clear();
std::vector<size_type> in_degs(this->size());
ITR(v, *this) ITR(e, v) ++in_degs[e.to];
std::queue<node_type> que;
REP(i, this->size()) if(in_degs[i] == 0) que.push(i);
while(not que.empty()) {
const node_type v = que.front(); que.pop();
ITR(u, (*this)[v]) if(!(--in_degs[u.to])) que.push(u.to);
sorted->push_back(v);
}
return std::ranges::ssize(*sorted) == std::ranges::ssize(*this);
}
template<class Graph>
bool uni::internal::graph_impl::mixin<Graph>::sort_topologically() const noexcept(NO_EXCEPT) {
std::vector<node_type> vs;
return this->sort_topologically(&vs);
}
#line 15 "graph/reachability_test.hpp"
#line 2 "view/chunk.hpp"
#line 6 "view/chunk.hpp"
#line 9 "view/chunk.hpp"
#line 11 "view/chunk.hpp"
namespace uni {
template<std::ranges::view View>
requires std::ranges::input_range<View>
struct chunk_view : std::ranges::view_interface<chunk_view<View>> {
private:
View _base;
std::ranges::range_difference_t<View> _n;
std::ranges::range_difference_t<View> _remainder = 0;
std::optional<std::ranges::iterator_t<View>> _current;
struct outer_iterator;
struct inner_iterator;
public:
constexpr explicit chunk_view(View base, std::ranges::range_difference_t<View> n)
: _base(std::move(base)), _n(n) {
assert(n >= 0);
}
constexpr View base() const &
requires std::copy_constructible<View>
{
return this->_base;
}
constexpr View base() && { return std::move(this->_base); }
constexpr outer_iterator begin() {
this->_current = std::ranges::begin(this->_base);
this->_remainder = this->_n;
return outer_iterator(*this);
}
constexpr std::default_sentinel_t end() const noexcept {
return std::default_sentinel;
}
constexpr auto size()
requires std::ranges::sized_range<View>
{
return to_unsigned(div_ceil(std::ranges::distance(this->_base), this->_n));
}
constexpr auto size() const
requires std::ranges::sized_range<const View>
{
return to_unsigned(div_ceil(std::ranges::distance(this->_base), this->_n));
}
};
template<class Range>
chunk_view(Range&&, std::ranges::range_difference_t<Range>) -> chunk_view<std::views::all_t<Range>>;
template<std::ranges::view View>
requires std::ranges::input_range<View>
struct chunk_view<View>::outer_iterator {
private:
chunk_view *_parent;
constexpr explicit outer_iterator(chunk_view &parent) noexcept
: _parent(std::addressof(parent))
{}
friend chunk_view;
public:
using iterator_concept = std::input_iterator_tag;
using difference_type = std::ranges::range_difference_t<View>;
struct value_type;
outer_iterator(outer_iterator &&) = default;
outer_iterator &operator=(outer_iterator &&) = default;
constexpr value_type operator*() const {
assert(*this != std::default_sentinel);
return value_type(*this->_parent);
}
constexpr outer_iterator &operator++() {
assert(*this != std::default_sentinel);
std::ranges::advance(*this->_parent->_current, this->_parent->_remainder, std::ranges::end(this->_parent->_base));
this->_parent->_remainder = this->_parent->_n;
return *this;
}
constexpr void operator++(int) { ++*this; }
friend constexpr bool operator==(const outer_iterator &lhs, std::default_sentinel_t) {
return *lhs._parent->_current == std::ranges::end(lhs._parent->_base) && lhs._parent->_remainder != 0;
}
friend constexpr difference_type operator-(std::default_sentinel_t, const outer_iterator &rhs)
requires std::sized_sentinel_for<std::ranges::sentinel_t<View>, std::ranges::iterator_t<View>>
{
const auto dist = std::ranges::end(rhs._parent->_base) - *rhs._parent->_current;
if(dist < rhs._parent->_remainder) return dist == 0 ? 0 : 1;
return 1 + div_ceil(dist - rhs._parent->_remainder, rhs._parent->_n);
}
friend constexpr difference_type operator-(const outer_iterator &lhs, std::default_sentinel_t rhs)
requires std::sized_sentinel_for<std::ranges::sentinel_t<View>, std::ranges::iterator_t<View>>
{
return -(rhs - lhs);
}
};
template<std::ranges::view View>
requires std::ranges::input_range<View>
struct chunk_view<View>::outer_iterator::value_type : std::ranges::view_interface<value_type> {
private:
chunk_view *_parent;
constexpr explicit value_type(chunk_view &parent) noexcept
: _parent(std::addressof(parent))
{}
friend outer_iterator;
public:
constexpr inner_iterator begin() const noexcept {
return inner_iterator(*this->_parent);
}
constexpr std::default_sentinel_t end() const noexcept {
return std::default_sentinel;
}
constexpr auto size() const
requires std::sized_sentinel_for<std::ranges::sentinel_t<View>, std::ranges::iterator_t<View>>
{
return to_unsigned(std::ranges::min(this->_parent->_remainder, std::ranges::end(this->_parent->_base) - *this->_parent->_current));
}
};
template<std::ranges::view View>
requires std::ranges::input_range<View>
struct chunk_view<View>::inner_iterator {
private:
chunk_view *_parent;
constexpr explicit inner_iterator(chunk_view &parent) noexcept
: _parent(std::addressof(parent))
{}
friend outer_iterator::value_type;
public:
using iterator_concept = std::input_iterator_tag;
using difference_type = std::ranges::range_difference_t<View>;
using value_type = std::ranges::range_value_t<View>;
inner_iterator(inner_iterator &&) = default;
inner_iterator &operator=(inner_iterator &&) = default;
constexpr const std::ranges::iterator_t<View> &base() const & {
return *this->_parent->_current;
}
constexpr std::ranges::range_reference_t<View> operator*() const {
assert(*this != std::default_sentinel);
return **this->_parent->_current;
}
constexpr inner_iterator &operator++() {
assert(*this != std::default_sentinel);
++*this->_parent->_current;
if(*this->_parent->_current == std::ranges::end(this->_parent->_base)) {
this->_parent->_remainder = 0;
}
else {
--this->_parent->_remainder;
}
return *this;
}
constexpr void operator++(int) { ++*this; }
friend constexpr bool operator==(const inner_iterator &lhs, std::default_sentinel_t) noexcept {
return lhs._parent->_remainder == 0;
}
friend constexpr difference_type operator-(std::default_sentinel_t, const inner_iterator &rhs)
requires std::sized_sentinel_for<std::ranges::sentinel_t<View>, std::ranges::iterator_t<View>>
{
return std::ranges::min(rhs._parent->_remainder, std::ranges::end(rhs._parent->_base) - *rhs._parent->_current);
}
friend constexpr difference_type operator-(const inner_iterator &lhs, std::default_sentinel_t rhs)
requires std::sized_sentinel_for<std::ranges::sentinel_t<View>, std::ranges::iterator_t<View>>
{
return -(rhs - lhs);
}
};
template<std::ranges::view View>
requires std::ranges::forward_range<View>
struct chunk_view<View> : std::ranges::view_interface<chunk_view<View>> {
private:
View _base;
std::ranges::range_difference_t<View> _n;
template<bool> struct iterator;
public:
constexpr explicit chunk_view(View base, const std::ranges::range_difference_t<View> n)
: _base(std::move(base)), _n(n)
{
assert(n > 0);
}
constexpr View base() const &
requires std::copy_constructible<View>
{
return this->_base;
}
constexpr View base() && { return std::move(this->_base); }
constexpr auto begin()
requires(!internal::simple_view<View>)
{
return iterator<false>(this, std::ranges::begin(this->_base));
}
constexpr auto begin() const
requires std::ranges::forward_range<const View>
{
return iterator<true>(this, std::ranges::begin(this->_base));
}
constexpr auto end()
requires(!internal::simple_view<View>)
{
if constexpr(std::ranges::common_range<View> && std::ranges::sized_range<View>) {
const auto missing = (this->_n - std::ranges::distance(this->_base) % this->_n) % this->_n;
return iterator<false>(this, std::ranges::end(this->_base), missing);
}
else if constexpr(std::ranges::common_range<View> && !std::ranges::bidirectional_range<View>) {
return iterator<false>(this, std::ranges::end(this->_base));
}
else {
return std::default_sentinel;
}
}
constexpr auto end() const
requires std::ranges::forward_range<const View>
{
if constexpr(std::ranges::common_range<const View> && std::ranges::sized_range<const View>) {
auto missing = (this->_n - std::ranges::distance(this->_base) % this->_n) % this->_n;
return iterator<true>(this, std::ranges::end(this->_base), missing);
} else if constexpr(std::ranges::common_range<const View> && !std::ranges::bidirectional_range<const View>) {
return iterator<true>(this, std::ranges::end(this->_base));
}
else {
return std::default_sentinel;
}
}
constexpr auto size()
requires std::ranges::sized_range<View>
{
return to_unsigned(div_ceil(std::ranges::distance(this->_base), this->_n));
}
constexpr auto size() const
requires std::ranges::sized_range<const View>
{
return to_unsigned(div_ceil(std::ranges::distance(this->_base), this->_n));
}
};
template<std::ranges::view View>
requires std::ranges::forward_range<View>
template<bool CONST>
struct chunk_view<View>::iterator {
private:
using Parent = internal::maybe_const_t<CONST, chunk_view>;
using Base = internal::maybe_const_t<CONST, View>;
std::ranges::iterator_t<Base> _current = std::ranges::iterator_t<Base>();
std::ranges::sentinel_t<Base> _end = std::ranges::sentinel_t<Base>();
std::ranges::range_difference_t<Base> _n = 0;
std::ranges::range_difference_t<Base> _missing = 0;
constexpr iterator(Parent *parent, std::ranges::iterator_t<Base> current, const std::ranges::range_difference_t<Base> missing = 0)
: _current(current), _end(std::ranges::end(parent->_base)), _n(parent->_n), _missing(missing)
{}
friend chunk_view;
public:
using iterator_category = std::input_iterator_tag;
using iterator_concept = internal::most_primitive_iterator_concept<false, Base>;
using value_type = decltype(std::views::take(std::ranges::subrange(_current, _end), _n));
using difference_type = std::ranges::range_difference_t<Base>;
iterator() = default;
constexpr iterator(iterator<!CONST> itr)
requires
CONST &&
std::convertible_to<std::ranges::iterator_t<View>, std::ranges::iterator_t<Base>> &&
std::convertible_to<std::ranges::sentinel_t<View>, std::ranges::sentinel_t<Base>>
: _current(std::move(itr._current)), _end(std::move(itr._end)), _n(itr._n), _missing(itr._missing)
{}
constexpr std::ranges::iterator_t<Base> base() const { return this->_current; }
constexpr value_type operator*() const {
assert(this->_current != this->_end);
return std::views::take(std::ranges::subrange(this->_current, this->_end), this->_n);
}
constexpr iterator &operator++() {
assert(this->_current != this->_end);
this->_missing = std::ranges::advance(this->_current, this->_n, this->_end);
return *this;
}
constexpr iterator operator++(int) {
auto temp = *this;
return ++*this, temp;
}
constexpr iterator &operator--()
requires std::ranges::bidirectional_range<Base>
{
std::ranges::advance(this->_current, this->_missing - this->_n);
this->_missing = 0;
return *this;
}
constexpr iterator operator--(int)
requires std::ranges::bidirectional_range<Base>
{
auto temp = *this;
return --*this, temp;
}
constexpr iterator &operator+=(difference_type lhs)
requires std::ranges::random_access_range<Base>
{
if(lhs > 0) {
assert(std::ranges::distance(this->_current, this->_end) > this->_n * (lhs - 1));
this->_missing = std::ranges::advance(this->_current, this->_n * lhs, this->_end);
}
else if(lhs < 0) {
std::ranges::advance(this->_current, this->_n * lhs + this->_missing);
this->_missing = 0;
}
return *this;
}
constexpr iterator &operator-=(difference_type lhs)
requires std::ranges::random_access_range<Base>
{
return *this += -lhs;
}
constexpr value_type operator[](difference_type n) const
requires std::ranges::random_access_range<Base>
{
return *(*this + n);
}
friend constexpr bool operator==(const iterator &lhs, const iterator &rhs) {
return lhs._current == rhs._current;
}
friend constexpr bool operator==(const iterator &lhs, std::default_sentinel_t) {
return lhs._current == lhs._end;
}
friend constexpr bool operator<(const iterator &lhs, const iterator &rhs)
requires std::ranges::random_access_range<Base>
{
return lhs._current > rhs._current;
}
friend constexpr bool operator>(const iterator &lhs, const iterator &rhs)
requires std::ranges::random_access_range<Base>
{
return rhs < lhs;
}
friend constexpr bool operator<=(const iterator &lhs, const iterator &rhs)
requires std::ranges::random_access_range<Base>
{
return !(rhs < lhs);
}
friend constexpr bool operator>=(const iterator &lhs, const iterator &rhs)
requires std::ranges::random_access_range<Base>
{
return !(lhs < rhs);
}
friend constexpr auto operator<=>(const iterator &lhs, const iterator &rhs)
requires std::ranges::random_access_range<Base> && std::three_way_comparable<std::ranges::iterator_t<Base>>
{
return lhs._current <=> rhs._current;
}
friend constexpr iterator operator+(const iterator &itr, const difference_type count)
requires std::ranges::random_access_range<Base>
{
auto res = itr;
return res += count, res;
}
friend constexpr iterator operator+(const difference_type count, const iterator &itr)
requires std::ranges::random_access_range<Base>
{
auto res = itr;
return res += count, res;
}
friend constexpr iterator operator-(const iterator &itr, const difference_type count)
requires std::ranges::random_access_range<Base>
{
auto res = itr;
return res -= count, res;
}
friend constexpr difference_type operator-(const iterator &lhs, const iterator &rhs)
requires std::sized_sentinel_for<std::ranges::iterator_t<Base>, std::ranges::iterator_t<Base>>
{
return (lhs._current - rhs._current + lhs._missing - rhs._missing) / lhs._n;
}
friend constexpr difference_type operator-(std::default_sentinel_t rhs, const iterator &lhs)
requires std::sized_sentinel_for<std::ranges::sentinel_t<Base>, std::ranges::iterator_t<Base>>
{
return div_ceil(lhs._end - lhs._current, lhs._n);
}
friend constexpr difference_type operator-(const iterator &lhs, std::default_sentinel_t rhs)
requires std::sized_sentinel_for<std::ranges::sentinel_t<Base>, std::ranges::iterator_t<Base>>
{
return -(rhs - lhs);
}
};
namespace views {
namespace internal {
template<class Range, typename Diff>
concept can_chunk_view = requires { chunk_view(std::declval<Range>(), std::declval<Diff>()); };
} // namespace internal
struct Chunk : adaptor::range_adaptor<Chunk> {
template<std::ranges::viewable_range Range, class Diff = std::ranges::range_difference_t<Range>>
requires internal::can_chunk_view<Range, Diff>
constexpr auto operator() [[nodiscard]] (Range &&res, std::type_identity_t<Diff> n) const {
return chunk_view(std::forward<Range>(res), n);
}
using adaptor::range_adaptor<Chunk>::operator();
static constexpr int arity = 2;
static constexpr bool has_simple_extra_args = true;
};
inline constexpr Chunk chunk;
} // namespace views
} // namespace uni
namespace std::ranges {
template<class View>
inline constexpr bool enable_borrowed_range<uni::chunk_view<View>> = forward_range<View> && enable_borrowed_range<View>;
} // namespace std::ranges
#line 2 "view/enumerate.hpp"
#line 6 "view/enumerate.hpp"
#line 10 "view/enumerate.hpp"
namespace uni {
namespace internal {
template<class Range>
concept range_with_movable_reference =
std::ranges::input_range<Range> && std::move_constructible<std::ranges::range_reference_t<Range>> &&
std::move_constructible<std::ranges::range_rvalue_reference_t<Range>>;
} // namespace internal
template<std::ranges::view View>
requires internal::range_with_movable_reference<View>
struct enumerate_view : public std::ranges::view_interface<enumerate_view<View>> {
private:
View _base = View();
template<bool Const> class iterator;
template<bool Const> class sentinel;
public:
enumerate_view()
requires std::default_initializable<View>
= default;
constexpr explicit enumerate_view(View base) : _base(std::move(base)) {}
constexpr auto begin()
requires(!internal::simple_view<View>)
{
return iterator<false>(std::ranges::begin(this->_base), 0);
}
constexpr auto begin() const
requires internal::range_with_movable_reference<const View>
{
return iterator<true>(std::ranges::begin(this->_base), 0);
}
constexpr auto end()
requires(!internal::simple_view<View>)
{
if constexpr(std::ranges::common_range<View> && std::ranges::sized_range<View>) {
return iterator<false>(std::ranges::end(_base), std::ranges::distance(this->_base));
}
else {
return sentinel<false>(std::ranges::end(_base));
}
}
constexpr auto end() const
requires internal::range_with_movable_reference<const View>
{
if constexpr(std::ranges::common_range<const View> && std::ranges::sized_range<const View>) {
return iterator<true>(std::ranges::end(_base), std::ranges::distance(_base));
}
else {
return sentinel<true>(std::ranges::end(_base));
}
}
constexpr auto size()
requires std::ranges::sized_range<View>
{
return std::ranges::size(_base);
}
constexpr auto size() const
requires std::ranges::sized_range<const View>
{
return std::ranges::size(_base);
}
constexpr View base() const &
requires std::copy_constructible<View>
{
return _base;
}
constexpr View base() && { return std::move(_base); }
};
template<class Range>
enumerate_view(Range&& ) -> enumerate_view<std::views::all_t<Range>>;
template<std::ranges::view View>
requires internal::range_with_movable_reference<View>
template<bool Const>
class enumerate_view<View>::iterator {
using Base = internal::maybe_const_t<Const, View>;
friend enumerate_view;
public:
using iterator_category = std::iterator_traits<std::ranges::iterator_t<Base>>::iterator_category;
using iterator_concept = internal::most_primitive_iterator_concept<Const, View>;
using difference_type = std::ranges::range_difference_t<Base>;
using value_type = std::tuple<difference_type, std::ranges::range_value_t<Base>>;
private:
using rangeeference_type = std::tuple<difference_type, std::ranges::range_reference_t<Base>>;
std::ranges::iterator_t<Base> _current = std::ranges::iterator_t<Base>();
difference_type _pos = 0;
constexpr explicit iterator(std::ranges::iterator_t<Base> current, const difference_type pos)
: _current(std::move(current)), _pos(pos)
{}
public:
iterator()
requires std::default_initializable<std::ranges::iterator_t<Base>>
= default;
constexpr iterator(iterator<!Const> itr)
requires Const && std::convertible_to<std::ranges::iterator_t<View>, std::ranges::iterator_t<Base>>
: _current(std::move(itr._current)), _pos(itr._pos)
{}
constexpr const std::ranges::iterator_t<Base>& base() const & noexcept {
return this->_current;
}
constexpr std::ranges::iterator_t<Base> base() && { return std::move(this->_current); }
constexpr difference_type index() const noexcept { return this->_pos; }
constexpr auto operator*() const {
return rangeeference_type(this->_pos, *this->_current);
}
constexpr iterator& operator++() {
++this->_current;
++this->_pos;
return *this;
}
constexpr void operator++(int) { ++*this; }
constexpr iterator operator++(int)
requires std::ranges::forward_range<Base>
{
auto temp = *this;
++*this;
return temp;
}
constexpr iterator& operator--()
requires std::ranges::bidirectional_range<Base>
{
--this->_current;
--this->_pos;
return *this;
}
constexpr iterator operator--(int)
requires std::ranges::bidirectional_range<Base>
{
auto temp = *this;
--*this;
return temp;
}
constexpr iterator& operator+=(const difference_type diff)
requires std::ranges::random_access_range<Base>
{
this->_current += diff;
this->_pos += diff;
return *this;
}
constexpr iterator& operator-=(const difference_type diff)
requires std::ranges::random_access_range<Base>
{
this->_current -= diff;
this->_pos -= diff;
return *this;
}
constexpr auto operator[](const difference_type diff) const
requires std::ranges::random_access_range<Base>
{
return rangeeference_type(this->_pos + diff, this->_current[diff]);
}
friend constexpr bool operator==(const iterator& lhs, const iterator& rhs) noexcept {
return lhs._pos == rhs._pos;
}
friend constexpr std::strong_ordering
operator<=>(const iterator& lhs, const iterator& rhs) noexcept {
return lhs._pos <=> rhs._pos;
}
friend constexpr iterator operator+(iterator lhs, const difference_type rhs)
requires std::ranges::random_access_range<Base>
{
return (lhs += rhs);
}
friend constexpr iterator operator+(const difference_type lhs, const iterator& rhs)
requires std::ranges::random_access_range<Base>
{
return rhs += lhs;
}
friend constexpr iterator operator-(iterator& lhs, const difference_type rhs)
requires std::ranges::random_access_range<Base>
{
return lhs -= rhs;
}
friend constexpr difference_type operator-(const iterator& lhs, const iterator& rhs) {
return lhs._pos - rhs._pos;
}
friend constexpr auto iter_move(const iterator& itr)
noexcept(
noexcept (std::ranges::iter_move(itr._current)) &&
std::is_nothrow_move_constructible_v<std::ranges::range_rvalue_reference_t<Base>>
)
{
return std::tuple<difference_type, std::ranges::range_rvalue_reference_t<Base>>(
itr._pos, std::ranges::iter_move(itr._current)
);
}
};
template<std::ranges::view View>
requires internal::range_with_movable_reference<View>
template<bool Const>
class enumerate_view<View>::sentinel {
using Base = internal::maybe_const_t<Const, View>;
std::ranges::sentinel_t<Base> _end = std::ranges::sentinel_t<Base>();
constexpr explicit sentinel(std::ranges::sentinel_t<Base> end) : _end(std::move(end)) {}
friend enumerate_view;
public:
sentinel() = default;
constexpr sentinel(sentinel<!Const> other)
requires Const && std::convertible_to<std::ranges::sentinel_t<View>, std::ranges::sentinel_t<Base>>
: _end(std::move(other._end)) {}
constexpr std::ranges::sentinel_t<Base> base() const { return this->_end; }
template<bool Const_>
requires
std::sentinel_for<
std::ranges::sentinel_t<Base>, std::ranges::iterator_t<internal::maybe_const_t<Const_, View>>
>
friend constexpr bool operator==(const iterator<Const_>& lhs, const sentinel& rhs) {
return lhs._current == rhs._end;
}
template<bool Const_>
requires
std::sized_sentinel_for<
std::ranges::sentinel_t<Base>, std::ranges::iterator_t<internal::maybe_const_t<Const_, View>>
>
friend constexpr std::ranges::range_difference_t<internal::maybe_const_t<Const_, View>>
operator-(const iterator<Const_>& lhs, const sentinel& rhs) {
return lhs._current - rhs._end;
}
template<bool Const_>
requires std::sized_sentinel_for<
std::ranges::sentinel_t<Base>, std::ranges::iterator_t<internal::maybe_const_t<Const_, View>>>
friend constexpr std::ranges::range_difference_t<internal::maybe_const_t<Const_, View>>
operator-(const sentinel& lhs, const iterator<Const_>& rhs) {
return lhs._end - rhs._current;
}
};
namespace views {
namespace internal {
template<class T>
concept can_enumerate_view =
requires { enumerate_view<std::views::all_t<T>>(std::declval<T>()); };
} // namespace internal
struct Enumerate : adaptor::range_adaptor_closure<Enumerate> {
template<std::ranges::viewable_range Range>
requires internal::can_enumerate_view<Range>
constexpr auto operator() [[nodiscard]] (Range&& range) const {
return enumerate_view<std::views::all_t<Range>>(std::forward<Range>(range));
}
};
inline constexpr Enumerate enumerate;
} // namespace views
} // namespace uni
namespace std::ranges {
template<class T>
inline constexpr bool enable_borrowed_range<uni::enumerate_view<T>> = enable_borrowed_range<T>;
} // namespace std
#line 18 "graph/reachability_test.hpp"
namespace uni {
template<class Graph>
template<std::ranges::sized_range R>
auto uni::internal::graph_impl::mixin<Graph>::test_reachability(R&& queries) const noexcept(NO_EXCEPT) {
using impl_type = u128;
constexpr auto CHUNK_SIZE = std::numeric_limits<impl_type>::digits;
std::vector<bool> res(std::ranges::size(queries));
uni::vector<node_type> vs;
this->sort_topologically(&vs);
debug(queries);
ITR(i, qs, queries | uni::views::chunk(CHUNK_SIZE) | uni::views::enumerate) {
debug(qs);
std::vector<impl_type> bits(this->size());
ITR(j, p, qs | uni::views::enumerate) {
bits[p.first] = uni::set_bit(bits[p.first], j);
}
ITR(v, vs) ITR(nv, this->operator[](v)) {
bits[nv] |= bits[v];
}
ITR(j, p, qs | uni::views::enumerate) {
res[i * CHUNK_SIZE + j] = uni::bit(bits[p.second], j);
}
}
return res;
}
} // namespace uni
#line 2 "graph/shortest_path.hpp"
#line 5 "graph/shortest_path.hpp"
#line 2 "graph/internal/bfs.hpp"
#line 6 "graph/internal/bfs.hpp"
#line 9 "graph/internal/bfs.hpp"
#line 11 "graph/internal/bfs.hpp"
#line 14 "graph/internal/bfs.hpp"
#line 17 "graph/internal/bfs.hpp"
template<class Graph>
template<uni::internal::item_or_convertible_range<typename Graph::node_type> Source, class Dist, class Prev>
void uni::internal::graph_impl::mixin<Graph>::shortest_path_without_cost(
Source&& s, Dist *const dist, Prev *const prev,
const node_type& unreachable, const node_type& root
) const noexcept(NO_EXCEPT) {
dist->assign(this->size(), uni::numeric_limits<cost_type>::arithmetic_infinity());
if constexpr(!std::is_same_v<Prev, std::nullptr_t>) prev->assign(this->size(), unreachable);
std::queue<node_type> que;
if constexpr(std::ranges::range<Source>) {
ITR(v, s) {
que.push(v), dist->operator[](v) = 0;
if constexpr(!std::is_same_v<Prev, std::nullptr_t>) prev->operator[](v) = root;
}
}
else {
que.push(s), dist->operator[](s) = 0;
if constexpr(!std::is_same_v<Prev, std::nullptr_t>) prev->operator[](s) = root;
}
while(!que.empty()) {
const node_type v = que.front(); que.pop();
ITR(nv, this->operator[](v)) {
if(dist->operator[](nv.to) < uni::numeric_limits<cost_type>::arithmetic_infinity()) { continue; }
dist->operator[](nv.to) = dist->operator[](v) + 1;
if constexpr(!std::is_same_v<Prev, std::nullptr_t>) prev->operator[](nv.to) = v;
que.push(nv.to);
}
}
}
template<class Graph>
template<uni::internal::item_or_convertible_range<typename Graph::node_type> Source>
auto uni::internal::graph_impl::mixin<Graph>::shortest_path_without_cost(Source&& s) const noexcept(NO_EXCEPT) {
uni::auto_holder<node_type, cost_type> dist;
this->shortest_path_without_cost(std::forward<Source>(s), &dist);
return dist;
}
#line 2 "graph/internal/01bfs.hpp"
#line 7 "graph/internal/01bfs.hpp"
#line 9 "graph/internal/01bfs.hpp"
#line 12 "graph/internal/01bfs.hpp"
#line 15 "graph/internal/01bfs.hpp"
#line 18 "graph/internal/01bfs.hpp"
template<class Graph>
template<uni::internal::item_or_convertible_range<typename Graph::node_type> Source, class Dist, class Prev>
void uni::internal::graph_impl::mixin<Graph>::shortest_path_with_01cost(
Source&& s, Dist *const dist, Prev *const prev,
const node_type& unreachable, const node_type& root
) const noexcept(NO_EXCEPT) {
std::deque<node_type> que;
dist->assign(this->size(), uni::numeric_limits<cost_type>::arithmetic_infinity());
if constexpr(!std::is_same_v<Prev, std::nullptr_t>) prev->assign(this->size(), unreachable);
if constexpr(std::ranges::range<Source>) {
ITR(v, s) {
que.push_back(v), dist->operator[](v) = 0;
if constexpr(!std::is_same_v<Prev, std::nullptr_t>) prev->operator[](v) = root;
}
}
else {
que.push_back(s), dist->operator[](s) = 0;
if constexpr(!std::is_same_v<Prev, std::nullptr_t>) prev->operator[](s) = root;
}
while(!que.empty()) {
const auto u = que.front(); que.pop_front();
const cost_type d = dist->operator[](u);
ITR(e, (*this)[u]) {
const node_type v = e.to; const auto cost = e.cost;
if(dist->operator[](v) <= d + cost) continue;
dist->operator[](v) = d + cost;
if constexpr(!std::is_same_v<Prev, std::nullptr_t>) prev->operator[](v) = u;
if(cost) que.push_back(v);
else que.push_front(v);
}
}
}
template<class Graph>
template<uni::internal::item_or_convertible_range<typename Graph::node_type> Source>
auto uni::internal::graph_impl::mixin<Graph>::shortest_path_with_01cost(Source&& s) const noexcept(NO_EXCEPT) {
uni::auto_holder<typename uni::internal::graph_impl::mixin<Graph>::node_type, cost_type> dist;
this->shortest_path_with_01cost(std::forward<Source>(s), &dist);
return dist;
}
#line 2 "graph/internal/dijkstra.hpp"
#line 7 "graph/internal/dijkstra.hpp"
#line 9 "graph/internal/dijkstra.hpp"
#line 11 "graph/internal/dijkstra.hpp"
#line 13 "graph/internal/dijkstra.hpp"
#line 16 "graph/internal/dijkstra.hpp"
template<class Graph>
template<uni::internal::item_or_convertible_range<typename Graph::node_type> Source, class Dist, class Prev>
void uni::internal::graph_impl::mixin<Graph>::shortest_path_with_cost(
Source&& s, Dist *const dist, Prev *const prev,
const node_type& unreachable, const node_type& root
) const noexcept(NO_EXCEPT) {
using state = std::pair<cost_type, node_type>;
std::priority_queue<state, std::vector<state>, std::greater<state>> que;
dist->assign(this->size(), uni::numeric_limits<cost_type>::arithmetic_infinity());
if constexpr(!std::same_as<Prev, std::nullptr_t>) prev->assign(this->size(), unreachable);
if constexpr(std::ranges::range<Source>) {
ITR(v, s) {
que.emplace(0, v), dist->operator[](v) = 0;
if constexpr(!std::is_same_v<Prev, std::nullptr_t>) prev->operator[](v) = root;
}
}
else {
que.emplace(0, s), dist->operator[](s) = 0;
if constexpr(!std::is_same_v<Prev, std::nullptr_t>) prev->operator[](s) = root;
}
while(!que.empty()) {
const auto [d, u] = que.top(); que.pop();
if(dist->operator[](u) < d) continue;
ITR(e, this->operator[](u)) {
const node_type v = e.to; const auto next = d + e.cost;
if(dist->operator[](v) <= next) continue;
dist->operator[](v) = next;
if constexpr(!std::same_as<Prev, std::nullptr_t>) prev->operator[](v) = u;
que.emplace(dist->operator[](v), v);
}
}
}
template<class Graph>
template<uni::internal::item_or_convertible_range<typename Graph::node_type> Source>
auto uni::internal::graph_impl::mixin<Graph>::shortest_path_with_cost(Source&& s) const noexcept(NO_EXCEPT) {
uni::auto_holder<node_type, cost_type> dist;
this->shortest_path_with_cost(std::forward<Source>(s), &dist);
return dist;
}
#line 10 "graph/shortest_path.hpp"
#line 12 "graph/shortest_path.hpp"
namespace uni {
template<class Node, class Prev, class Res>
void restore_path(Node back, const Prev& prev, Res *const res) {
res->clear();
while(back >= 0) {
res->emplace_back(back);
back = prev[back];
}
std::ranges::reverse(*res);
}
template<class Node, class Prev, class Res = uni::vector<Node>>
uni::vector<Node> restore_path(Node back, const Prev& prev) {
uni::vector<Node> res;
restore_path(back, prev, &res);
return res;
}
}
#line 2 "graph/tree_diamiter.hpp"
#line 6 "graph/tree_diamiter.hpp"
#line 8 "graph/tree_diamiter.hpp"
namespace uni {
namespace internal {
template<class Graph>
std::pair<typename Graph::cost_type, typename Graph::node_type> farthest(const Graph& tree, const typename Graph::node_type v, const typename Graph::node_type p, std::vector<typename Graph::node_type> *const prev = nullptr) {
std::pair<typename Graph::cost_type, typename Graph::node_type> res = { 0, v };
for(auto nv : tree[v]) {
if(nv.to == p) continue;
auto next = farthest(tree, nv.to, v, prev);
next.first += nv.cost;
if(res.first < next.first) {
if(prev) prev->operator[](nv.to) = v;
res = next;
}
}
return res;
}
} // namespace internal
template<class Graph>
auto tree_diamiter(const Graph& tree, std::vector<typename Graph::node_type> *const prev = nullptr) {
const auto p = farthest(tree, 0, -1);
return farthest(tree, p.second, -1, prev);
}
} // namespace uni
#line 2 "graph/tree_hash.hpp"
#line 6 "graph/tree_hash.hpp"
#line 9 "graph/tree_hash.hpp"
namespace uni {
template<class Graph>
auto tree_centers(const Graph& tree) {
std::vector<typename Graph::node_type> prev(std::ranges::size(tree), -1);
auto [ diam, v ] = tree_diamiter(tree, &prev);
std::vector<typename Graph::node_type> res;
{
for(typename Graph::size_type i = 0; i < diam / 2; ++i) {
v = prev[v];
}
res.push_back(v);
if(diam % 2 == 1) res.push_back(prev[v]);
}
{
auto rest = std::ranges::unique(res);
res.erase(std::ranges::begin(rest), std::ranges::end(rest));
}
return std::make_pair(diam, res);
}
template<class Graph>
std::size_t tree_hash(const Graph& tree, typename Graph::node_type v, typename Graph::node_type p = -1) {
static std::map<std::vector<typename Graph::node_type>, std::size_t> vals;
std::vector<typename Graph::node_type> children;
for(const auto nv : tree[v]) {
if(nv == p) continue;
children.emplace_back(tree_hash(tree, nv, v));
}
std::ranges::sort(children);
if(!vals.contains(children)) {
vals[children] = 0;
vals[children] = std::ranges::size(vals);
}
return vals[children];
}
} // namespace uni
#line 18 "include/graph_theory.hpp"
include/graph_theory.hpp