#line 2 "numeric/boundary_seeker.hpp"
#include <cmath>
#include <utility>
#include <functional>
#include <type_traits>
#line 2 "snippet/iterations.hpp"
#line 2 "macro/overload.hpp"
#define $OVERLOAD2(arg0, arg1, cmd, ...) cmd
#define $OVERLOAD3(arg0, arg1, arg2, cmd, ...) cmd
#define $OVERLOAD4(arg0, arg1, arg2, arg3, cmd, ...) cmd
#define $OVERLOAD5(arg0, arg1, arg2, arg3, arg4, cmd, ...) cmd
#define $OVERLOAD6(arg0, arg1, arg2, arg3, arg4, arg5, cmd, ...) cmd
#line 2 "macro/basic.hpp"
#define TO_STRING_AUX(x) #x
#define TO_STRING(x) TO_STRING_AUX(x)
#define CONCAT_AUX(x, y) x##y
#define CONCAT(x, y) CONCAT_AUX(x, y)
#define UNPAREN_AUX(...) __VA_ARGS__
#define UNPAREN(...) __VA_ARGS__
#line 6 "snippet/iterations.hpp"
#define LOOP(n) REPI(CONCAT(_$, __COUNTER__), n)
#define REPI(i,n) for(std::remove_cvref_t<decltype(n)> i=0, CONCAT(i, $)=(n); i<CONCAT(i, $); ++i)
#define REPF(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); ++i)
#define REPIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); i+=(s))
#define REPR(i,n) for(auto i=(n); --i>=0;)
#define REPB(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); --i>=CONCAT(i, $);)
#define REPRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l)-1)/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); (i-=(s)))
#define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__)
#define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__)
#define FORO(i,n) for(int i=0, CONCAT(i, $)=static_cast<int>(n); i<=CONCAT(i, $); ++i)
#define FORI(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); ++i)
#define FORIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); i+=(s))
#define FORRO(i,n) for(auto i=(n); i>=0; --i)
#define FORR(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); i>=CONCAT(i, $); --i)
#define FORRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l))/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); i-=(s))
#define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI, FORO)(__VA_ARGS__)
#define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR, FORRO)(__VA_ARGS__)
#define ITR1(e0,v) for(const auto &e0 : (v))
#define ITRP1(e0,v) for(auto e0 : (v))
#define ITRR1(e0,v) for(auto &e0 : (v))
#define ITR2(e0,e1,v) for(const auto [e0, e1] : (v))
#define ITRP2(e0,e1,v) for(auto [e0, e1] : (v))
#define ITRR2(e0,e1,v) for(auto &[e0, e1] : (v))
#define ITR3(e0,e1,e2,v) for(const auto [e0, e1, e2] : (v))
#define ITRP3(e0,e1,e2,v) for(auto [e0, e1, e2] : (v))
#define ITRR3(e0,e1,e2,v) for(auto &[e0, e1, e2] : (v))
#define ITR4(e0,e1,e2,e3,v) for(const auto [e0, e1, e2, e3] : (v))
#define ITRP4(e0,e1,e2,e3,v) for(auto [e0, e1, e2, e3] : (v))
#define ITRR4(e0,e1,e2,e3,v) for(auto &[e0, e1, e2, e3] : (v))
#define ITR5(e0,e1,e2,e3,e4,v) for(const auto [e0, e1, e2, e3, e4] : (v))
#define ITRP5(e0,e1,e2,e3,e4,v) for(auto [e0, e1, e2, e3, e4] : (v))
#define ITRR5(e0,e1,e2,e3,e4,v) for(auto &[e0, e1, e2, e3, e4] : (v))
#define ITR(...) $OVERLOAD6(__VA_ARGS__, ITR5, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__)
#define ITRP(...) $OVERLOAD6(__VA_ARGS__, ITRP5, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__)
#define ITRR(...) $OVERLOAD6(__VA_ARGS__, ITRR5, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__)
#line 11 "numeric/boundary_seeker.hpp"
#line 2 "internal/dev_env.hpp"
#ifdef LOCAL_JUDGE
inline constexpr bool DEV_ENV = true;
inline constexpr bool NO_EXCEPT = false;
#else
inline constexpr bool DEV_ENV = false;
inline constexpr bool NO_EXCEPT = true;
#endif // LOCAL_JUDGE
#if __cplusplus >= 202100L
#define CPP20 true
#define CPP23 true
#elif __cplusplus >= 202002L
#define CPP20 true
#define CPP23 false
#else
#define CPP20 false
#define CPP23 false
#endif
#line 2 "internal/types.hpp"
#include <cstdint>
namespace uni {
namespace internal {
using size_t = std::int64_t;
using int128_t = __int128_t;
using uint128_t = __uint128_t;
} // namesapce internal
} // namespace uni
#line 14 "numeric/boundary_seeker.hpp"
#line 2 "numeric/limits.hpp"
#include <limits>
#line 6 "numeric/limits.hpp"
#line 2 "snippet/internal/types.hpp"
#line 4 "snippet/internal/types.hpp"
namespace uni {
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
#ifdef __GNUC__
using i128 = __int128_t;
using u128 = __uint128_t;
using f128 = __float128;
#endif
using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
} // namespace uni
#line 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 "numeric/boundary_seeker.hpp"
namespace uni {
namespace internal {
namespace boundary_seeker_impl {
template<class T>
struct integal {
protected:
std::function<bool(T)> _validate;
public:
integal(std::function<bool(T)> validate) noexcept(NO_EXCEPT) : _validate(validate) {}
template<bool INVERT = false>
T bound(const T _ok, const T _ng) const noexcept(NO_EXCEPT) {
T ok = _ok, ng = _ng;
if constexpr(INVERT) std::swap(ng, ok);
while(std::abs(ok - ng) > 1) {
T mid = ng + (ok - ng) / 2;
(INVERT ^ this->_validate(mid) ? ok : ng) = mid;
}
return ok;
}
template<bool REVERSE = false, bool INVERT = false>
T bound(const T ok) const noexcept(NO_EXCEPT) {
assert(INVERT ^ this->_validate(ok));
T ng = REVERSE ? -1 : 1;
while(INVERT ^ this->_validate(ok + ng)) ng += ng;
return this->bound<INVERT>(ok, ok + ng);
}
template<bool REVERSE = false, bool INVERT = false>
T bound() const noexcept(NO_EXCEPT) {
return this->bound<INVERT>(
REVERSE ?
numeric_limits<T>::arithmetic_infinity() / 2 :
numeric_limits<T>::arithmetic_negative_infinity() / 2
);
}
template<bool INVERT = false>
T bound_or(const T ok, const T ng, const T proxy) const noexcept(NO_EXCEPT) {
const T res = this->bound<INVERT>(ok, ng);
return this->_validate(res) ? res : proxy;
}
template<bool REVERSE = false, bool INVERT = false>
T bound_or(const T ok, const T proxy) const noexcept(NO_EXCEPT) {
const T res = this->bound<REVERSE, INVERT>(ok);
return this->_validate(res) ? res : proxy;
}
template<bool REVERSE = false, bool INVERT = false>
T bound_or(const T proxy) const noexcept(NO_EXCEPT) {
const T res = this->bound<REVERSE, INVERT>();
return this->_validate(res) ? res : proxy;
}
};
template<class T>
struct floating_point {
protected:
std::function<bool(T)> _validate;
public:
floating_point(std::function<bool(T)> validate) noexcept(NO_EXCEPT) : _validate(validate) {}
template<bool INVERT = false, internal::size_t ITERATIONS = 200>
T bound(const T _ok, const T _ng) const noexcept(NO_EXCEPT) {
T ok = _ok, ng = _ng;
if constexpr(INVERT) std::swap(ng, ok);
REP(ITERATIONS) {
T mid = ng + (ok - ng) / 2;
(INVERT ^ this->_validate(mid) ? ok : ng) = mid;
}
return ok;
}
template<bool REVERSE = false, bool INVERT = false, internal::size_t ITERATIONS = 200>
T bound(const T ok) const noexcept(NO_EXCEPT) {
assert(INVERT ^ this->_validate(ok));
T ng = REVERSE ? -1 : 1;
while(INVERT ^ this->_validate(ok + ng)) ng += ng;
return this->bound<INVERT>(ok, ok + ng);
}
template<bool REVERSE = false, bool INVERT = false, internal::size_t ITERATIONS = 200>
T bound() const noexcept(NO_EXCEPT) {
return this->bound<INVERT, ITERATIONS>(
REVERSE ?
numeric_limits<T>::arithmetic_infinity() / 2 :
numeric_limits<T>::arithmetic_negative_infinity() / 2
);
}
template<bool INVERT = false, internal::size_t ITERATIONS = 200>
T bound_or(const T ok, const T ng, const T proxy) const noexcept(NO_EXCEPT) {
const T res = this->bound<INVERT, ITERATIONS>(ok, ng);
return this->_validate(res) ? res : proxy;
}
template<bool REVERSE = false, bool INVERT = false, internal::size_t ITERATIONS = 200>
T bound_or(const T ok, const T proxy) const noexcept(NO_EXCEPT) {
const T res = this->bound<REVERSE, INVERT, ITERATIONS>(ok);
return this->_validate(res) ? res : proxy;
}
template<bool REVERSE = false, bool INVERT = false, internal::size_t ITERATIONS = 200>
T bound_or(const T proxy) const noexcept(NO_EXCEPT) {
const T res = this->bound<REVERSE, INVERT, ITERATIONS>();
return this->_validate(res) ? res : proxy;
}
};
template<class, bool>
struct seeker {};
template<class T>
struct seeker<T,true> : integal<T> {
using integal<T>::integal;
};
template<class T>
struct seeker<T,false> : floating_point<T> {
using floating_point<T>::floating_point;
};
} // namespace boundary_seeker_impl
} // namespace internal
template<class T>
using boundary_seeker = internal::boundary_seeker_impl::seeker<T,std::is_integral_v<T>>;
} // namespace uni
numeric/boundary_seeker.hpp