#line 2 "internal/point_reference.hpp"
#include <iterator>
#include <concepts>
#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 9 "internal/point_reference.hpp"
#line 2 "global/constants.hpp"
#include <cstdint>
#line 6 "global/constants.hpp"
#include <utility>
#include <cmath>
#line 2 "snippet/aliases.hpp"
#line 6 "snippet/aliases.hpp"
#include <vector>
#include <ranges>
#line 2 "snippet/internal/types.hpp"
#line 4 "snippet/internal/types.hpp"
namespace uni {
using i16 = std :: int16_t ;
using u16 = std :: uint16_t ;
using i32 = std :: int32_t ;
using u32 = std :: uint32_t ;
using i64 = std :: int64_t ;
using u64 = std :: uint64_t ;
#ifdef __GNUC__
using i128 = __int128_t ;
using u128 = __uint128_t ;
using f128 = __float128 ;
#endif
using uint = unsigned ;
using ll = long long ;
using ull = unsigned long long ;
using ld = long double ;
} // namespace uni
#line 12 "snippet/aliases.hpp"
#define until(...) while(!(__VA_ARGS__))
#define CONTINUE(...) { __VA_ARGS__; continue; }
#define BREAK(...) { __VA_ARGS__; break; }
#define ALL(x) std::ranges::begin((x)),std::ranges::end((x))
#define RALL(x) std::ranges::rbegin((x)),std::ranges::rend((x))
#define $F first
#define $S second
namespace uni {
constexpr char LN = '\n' ;
constexpr char SPC = ' ' ;
constexpr std :: pair < int , int > DIRS4 [] = { { - 1 , 0 }, { 0 , 1 }, { 1 , 0 }, { 0 , - 1 } };
constexpr std :: pair < int , int > DIRS4P [] = { { - 1 , 0 }, { 0 , 1 }, { 1 , 0 }, { 0 , - 1 }, { 0 , 0 } };
constexpr std :: pair < int , int > DIRS8 [] = { { - 1 , 0 }, { - 1 , 1 }, { 0 , 1 }, { 1 , 1 }, { 1 , 0 }, { 1 , - 1 }, { 0 , - 1 }, { - 1 , - 1 } };
constexpr std :: pair < int , int > DIRS8P [] = { { - 1 , 0 }, { - 1 , 1 }, { 0 , 1 }, { 1 , 1 }, { 1 , 0 }, { 1 , - 1 }, { 0 , - 1 }, { - 1 , - 1 }, { 0 , 0 } };
template < class T > using spair = std :: pair < T , T > ;
} // namespace uni
namespace std {
using bit_reference = std :: vector < bool >:: reference ;
bit_reference operator |= ( bit_reference a , const bool b ) noexcept ( NO_EXCEPT ) { return a = a | b ; }
bit_reference operator &= ( bit_reference a , const bool b ) noexcept ( NO_EXCEPT ) { return a = a & b ; }
}
#line 11 "global/constants.hpp"
#line 2 "internal/type_traits.hpp"
#include <iostream>
#line 6 "internal/type_traits.hpp"
#include <type_traits>
#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 2 "internal/exception.hpp"
namespace uni {
namespace internal {
template < class ... T > inline constexpr bool EXCEPTION_ON_TYPE = false ;
template < auto T > inline constexpr bool EXCEPTION_ON_VALUE = false ;
} // namespace internal
} // namespace uni
#line 14 "global/constants.hpp"
#line 2 "numeric/limits.hpp"
#include <limits>
#line 6 "numeric/limits.hpp"
#line 9 "numeric/limits.hpp"
#line 11 "numeric/limits.hpp"
namespace uni {
template < class T >
struct numeric_limits : std :: numeric_limits < T > {
static constexpr long double FLOAT_EPSILON = 1E-14 ;
static constexpr T arithmetic_infinity () noexcept ( NO_EXCEPT ) {
return std :: numeric_limits < T >:: max () / 2 - 1 ;
}
static constexpr T arithmetic_negative_infinity () noexcept ( NO_EXCEPT ) {
return std :: numeric_limits < T >:: lowest () / 2 + 1 ;
}
static constexpr T arithmetic_epsilon () noexcept ( NO_EXCEPT ) {
if constexpr ( std :: is_floating_point_v < T > ) {
return numeric_limits :: FLOAT_EPSILON ;
}
else {
return 0 ;
}
}
};
constexpr i32 INF32 = numeric_limits < i32 >:: arithmetic_infinity ();
constexpr i64 INF64 = numeric_limits < i64 >:: arithmetic_infinity ();
template < class T >
constexpr T INF = numeric_limits < T >:: arithmetic_infinity ();
template < class T >
constexpr T EPSILON = numeric_limits < T >:: arithmetic_epsilon ();
} // namespace uni
#line 16 "global/constants.hpp"
namespace uni {
namespace internal {
template < class T >
consteval auto get_pi () {
if constexpr ( std :: integral < T > ) {
return static_cast < T > ( 3 );
}
else if constexpr ( std :: same_as < T , float > ) {
return M_PIf ;
}
else if constexpr ( std :: same_as < T , double > ) {
return M_PI ;
}
else if constexpr ( std :: same_as < T , ld > ) {
return M_PIl ;
}
else {
static_assert ( EXCEPTION_ON_TYPE < T > );
}
}
} // namespace internal
template < class T = ld >
constexpr auto PI = internal :: get_pi < T > ();
enum class comparison : std :: uint8_t {
equal_to ,
not_equal_to ,
equals = equal_to ,
eq = equal_to ,
under ,
over ,
or_under ,
or_over ,
less = under ,
more = over ,
less_than = under ,
more_than = over ,
not_less_than = or_over ,
not_more_than = or_under ,
leq = or_under ,
geq = or_over
};
enum class interval_notation : std :: uint8_t {
right_open ,
left_open ,
open ,
closed ,
};
enum class replacement_policy : std :: uint8_t {
insert_sync ,
overwrite_sync ,
overwrite_async
};
enum class rotation : std :: int8_t {
clockwise ,
counter_clockwise ,
anti_clockwise = counter_clockwise ,
};
enum class positional_relation : std :: int8_t {
clockwise ,
counter_clockwise ,
anti_clockwise = counter_clockwise ,
backward ,
forward ,
in ,
on ,
out ,
included = in ,
inscribed ,
intersecting ,
circumscribed ,
distant ,
};
enum class alignment : std :: int8_t {
left ,
center ,
right
};
} // namespace uni
#line 11 "internal/point_reference.hpp"
namespace uni {
namespace internal {
template < class Super , std :: integral SizeType = typename Super :: size_type >
struct point_reference {
using size_type = SizeType ;
using iterator = typename Super :: iterator ;
protected:
Super * const _super ;
const size_type _pos ;
point_reference ( Super * const super , const size_type pos ) noexcept ( NO_EXCEPT ) : _super ( super ), _pos ( pos ) {}
inline auto index () noexcept ( NO_EXCEPT ) { return this -> _pos ; }
};
} // namespace internal
} // namespace uni 
internal/point_reference.hpp