This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub shiomusubi496/library
#include "template/out.hpp"
#pragma once #include <bits/stdc++.h> #include <unistd.h> #include "macros.hpp" #include "alias.hpp" #include "type_traits.hpp" struct NumberToString { char buf[10000][4]; constexpr NumberToString() : buf{} { rep (i, 10000) { int n = i; rrep (j, 4) { buf[i][j] = (char)('0' + n % 10); n /= 10; } } } } constexpr precalc_number_to_string; template<std::size_t buf_size = IO_BUFFER_SIZE, bool debug = false> class Printer { private: template<class, bool = debug, class = void> struct has_print : std::false_type {}; template<class T> struct has_print<T, false, decltype(std::declval<T>().print(std::declval<Printer&>()), (void)0)> : std::true_type {}; template<class T> struct has_print<T, true, decltype(std::declval<T>().debug(std::declval<Printer&>()), (void)0)> : std::true_type {}; int fd; std::size_t idx; std::array<char, buf_size> buffer; std::size_t decimal_precision; public: inline void print_char(char c) { #if SHIO_LOCAL buffer[idx++] = c; if (idx == buf_size) flush(); #else if IF_CONSTEXPR (!debug) { buffer[idx++] = c; if (idx == buf_size) flush(); } #endif } inline void flush() { idx = write(fd, buffer.begin(), idx); idx = 0; } Printer(int fd) : fd(fd), idx(0), decimal_precision(16) {} Printer(FILE* fp) : fd(fileno(fp)), idx(0), decimal_precision(16) {} ~Printer() { flush(); } void set_decimal_precision(std::size_t decimal_precision) { this->decimal_precision = decimal_precision; } void print(char c) { if IF_CONSTEXPR (debug) print_char('\''); print_char(c); if IF_CONSTEXPR (debug) print_char('\''); } void print(bool b) { print_char((char)(b + '0')); } void print(const char* a) { if IF_CONSTEXPR (debug) print_char('"'); for (; *a != '\0'; ++a) print_char(*a); if IF_CONSTEXPR (debug) print_char('"'); } template<std::size_t len> void print(const char (&a)[len]) { if IF_CONSTEXPR (debug) print_char('"'); for (auto i : a) print_char(i); if IF_CONSTEXPR (debug) print_char('"'); } void print(const std::string& a) { if IF_CONSTEXPR (debug) print_char('"'); for (auto i : a) print_char(i); if IF_CONSTEXPR (debug) print_char('"'); } template<std::size_t len> void print(const std::bitset<len>& a) { rrep (i, len) print_char((char)(a[i] + '0')); } template<class T, typename std::enable_if<is_int<T>::value && !has_print<T>::value>::type* = nullptr> void print(T a) { if (!a) { print_char('0'); return; } if IF_CONSTEXPR (is_signed_int<T>::value) { if (a < 0) { print_char('-'); using U = typename make_unsigned_int<T>::type; print(static_cast<U>(-static_cast<U>(a))); return; } } if (idx + 40 >= buf_size) flush(); static char s[40]; int t = 40; while (a >= 10000) { int i = a % 10000; a /= 10000; t -= 4; std::memcpy(s + t, precalc_number_to_string.buf[i], 4); } if (a >= 1000) { std::memcpy(buffer.begin() + idx, precalc_number_to_string.buf[a], 4); idx += 4; } else if (a >= 100) { std::memcpy(buffer.begin() + idx, precalc_number_to_string.buf[a] + 1, 3); idx += 3; } else if (a >= 10) { std::memcpy(buffer.begin() + idx, precalc_number_to_string.buf[a] + 2, 2); idx += 2; } else { buffer[idx++] = '0' | a; } std::memcpy(buffer.begin() + idx, s + t, 40 - t); idx += 40 - t; } template<class T, typename std::enable_if<std::is_floating_point<T>::value && !has_print<T>::value>::type* = nullptr> void print(T a) { if (a == std::numeric_limits<T>::infinity()) { print("inf"); return; } if (a == -std::numeric_limits<T>::infinity()) { print("-inf"); return; } if (std::isnan(a)) { print("nan"); return; } if (a < 0) { print_char('-'); a = -a; } T b = a; if (b < 1) { print_char('0'); } else { std::string s; while (b >= 1) { s += (char)('0' + (int)std::fmod(b, 10.0)); b /= 10; } for (auto i = s.rbegin(); i != s.rend(); ++i) print_char(*i); } print_char('.'); rep (decimal_precision) { a *= 10; print_char((char)('0' + (int)std::fmod(a, 10.0))); } } private: template<std::size_t i, class... Args> void print(const std::tuple<Args...>& a) { if IF_CONSTEXPR (i < sizeof...(Args)) { if IF_CONSTEXPR (debug) print_char(','); print_char(' '); print(std::get<i>(a)); print<i + 1, Args...>(a); } } public: template<class... Args> void print(const std::tuple<Args...>& a) { if IF_CONSTEXPR (debug) print_char('('); if IF_CONSTEXPR (sizeof...(Args) != 0) print(std::get<0>(a)); print<1, Args...>(a); if IF_CONSTEXPR (debug) print_char(')'); } template<class T, class U> void print(const std::pair<T, U>& a) { if IF_CONSTEXPR (debug) print_char('('); print(a.first); if IF_CONSTEXPR (debug) print_char(','); print_char(' '); print(a.second); if IF_CONSTEXPR (debug) print_char(')'); } template<class T, typename std::enable_if<is_range<T>::value && !has_print<T>::value>::type* = nullptr> void print(const T& a) { if IF_CONSTEXPR (debug) print_char('{'); for (auto i = std::begin(a); i != std::end(a); ++i) { if (i != std::begin(a)) { if IF_CONSTEXPR (debug) print_char(','); print_char(' '); } print(*i); } if IF_CONSTEXPR (debug) print_char('}'); } template<class T, typename std::enable_if<has_print<T>::value && !debug>::type* = nullptr> void print(const T& a) { a.print(*this); } template<class T, typename std::enable_if<has_print<T>::value && debug>::type* = nullptr> void print(const T& a) { a.debug(*this); } void operator()() {} template<class Head, class... Args> void operator()(const Head& head, const Args&... args) { print(head); operator()(args...); } template<class T> Printer& operator<<(const T& a) { print(a); return *this; } Printer& operator<<(Printer& (*pf)(Printer&)) { return pf(*this); } }; template<std::size_t buf_size, bool debug> Printer<buf_size, debug>& endl(Printer<buf_size, debug>& pr) { pr.print_char('\n'); pr.flush(); return pr; } template<std::size_t buf_size, bool debug> Printer<buf_size, debug>& flush(Printer<buf_size, debug>& pr) { pr.flush(); return pr; } struct SetPrec { int n; template<class Pr> void print(Pr& pr) const { pr.set_decimal_precision(n); } template<class Pr> void debug(Pr& pr) const { pr.set_decimal_precision(n); } }; SetPrec setprec(int n) { return SetPrec{n}; }; Printer<> print(1), eprint(2); void prints() { print.print_char('\n'); } template<class T> auto prints(const T& v) -> decltype(print << v, (void)0) { print << v; print.print_char('\n'); } template<class Head, class... Tail> auto prints(const Head& head, const Tail&... tail) -> decltype(print << head, (void)0) { print << head; print.print_char(' '); prints(tail...); } Printer<IO_BUFFER_SIZE, true> debug(1), edebug(2); void debugs() { debug.print_char('\n'); } template<class T> auto debugs(const T& v) -> decltype(debug << v, (void)0) { debug << v; debug.print_char('\n'); } template<class Head, class... Tail> auto debugs(const Head& head, const Tail&... tail) -> decltype(debug << head, (void)0) { debug << head; debug.print_char(' '); debugs(tail...); }
#line 2 "template/out.hpp" #include <bits/stdc++.h> #include <unistd.h> #line 2 "template/macros.hpp" #line 4 "template/macros.hpp" #ifndef __COUNTER__ #define __COUNTER__ __LINE__ #endif #define OVERLOAD5(a, b, c, d, e, ...) e #define REP1_0(b, c) REP1_1(b, c) #define REP1_1(b, c) \ for (ll REP_COUNTER_##c = 0; REP_COUNTER_##c < (ll)(b); ++REP_COUNTER_##c) #define REP1(b) REP1_0(b, __COUNTER__) #define REP2(i, b) for (ll i = 0; i < (ll)(b); ++i) #define REP3(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i) #define REP4(i, a, b, c) for (ll i = (ll)(a); i < (ll)(b); i += (ll)(c)) #define rep(...) OVERLOAD5(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) #define RREP2(i, a) for (ll i = (ll)(a)-1; i >= 0; --i) #define RREP3(i, a, b) for (ll i = (ll)(a)-1; i >= (ll)(b); --i) #define RREP4(i, a, b, c) for (ll i = (ll)(a)-1; i >= (ll)(b); i -= (ll)(c)) #define rrep(...) OVERLOAD5(__VA_ARGS__, RREP4, RREP3, RREP2)(__VA_ARGS__) #define REPS2(i, b) for (ll i = 1; i <= (ll)(b); ++i) #define REPS3(i, a, b) for (ll i = (ll)(a) + 1; i <= (ll)(b); ++i) #define REPS4(i, a, b, c) for (ll i = (ll)(a) + 1; i <= (ll)(b); i += (ll)(c)) #define reps(...) OVERLOAD5(__VA_ARGS__, REPS4, REPS3, REPS2)(__VA_ARGS__) #define RREPS2(i, a) for (ll i = (ll)(a); i > 0; --i) #define RREPS3(i, a, b) for (ll i = (ll)(a); i > (ll)(b); --i) #define RREPS4(i, a, b, c) for (ll i = (ll)(a); i > (ll)(b); i -= (ll)(c)) #define rreps(...) OVERLOAD5(__VA_ARGS__, RREPS4, RREPS3, RREPS2)(__VA_ARGS__) #define each_for(...) for (auto&& __VA_ARGS__) #define each_const(...) for (const auto& __VA_ARGS__) #define all(v) std::begin(v), std::end(v) #define rall(v) std::rbegin(v), std::rend(v) #if __cpp_if_constexpr >= 201606L #define IF_CONSTEXPR constexpr #else #define IF_CONSTEXPR #endif #define IO_BUFFER_SIZE (1 << 17) #line 2 "template/alias.hpp" #line 4 "template/alias.hpp" using ll = long long; using uint = unsigned int; using ull = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; using ld = long double; using PLL = std::pair<ll, ll>; template<class T> using prique = std::priority_queue<T, std::vector<T>, std::greater<T>>; template<class T> struct infinity { static constexpr T value = std::numeric_limits<T>::max() / 2; static constexpr T mvalue = std::numeric_limits<T>::lowest() / 2; static constexpr T max = std::numeric_limits<T>::max(); static constexpr T min = std::numeric_limits<T>::lowest(); }; #if __cplusplus <= 201402L template<class T> constexpr T infinity<T>::value; template<class T> constexpr T infinity<T>::mvalue; template<class T> constexpr T infinity<T>::max; template<class T> constexpr T infinity<T>::min; #endif #if __cpp_variable_templates >= 201304L template<class T> constexpr T INF = infinity<T>::value; #endif constexpr ll inf = infinity<ll>::value; constexpr ld EPS = 1e-8; constexpr ld PI = 3.1415926535897932384626; #line 2 "template/type_traits.hpp" #line 5 "template/type_traits.hpp" template<class T, class... Args> struct function_traits_impl { using result_type = T; template<std::size_t idx> using argument_type = typename std::tuple_element<idx, std::tuple<Args...>>::type; using argument_tuple = std::tuple<Args...>; static constexpr std::size_t arg_size() { return sizeof...(Args); } }; template<class> struct function_traits_helper; template<class Res, class Tp, class... Args> struct function_traits_helper<Res (Tp::*)(Args...)> { using type = function_traits_impl<Res, Args...>; }; template<class Res, class Tp, class... Args> struct function_traits_helper<Res (Tp::*)(Args...)&> { using type = function_traits_impl<Res, Args...>; }; template<class Res, class Tp, class... Args> struct function_traits_helper<Res (Tp::*)(Args...) const> { using type = function_traits_impl<Res, Args...>; }; template<class Res, class Tp, class... Args> struct function_traits_helper<Res (Tp::*)(Args...) const&> { using type = function_traits_impl<Res, Args...>; }; #if __cpp_noexcept_function_type >= 201510L template<class Res, class Tp, class... Args> struct function_traits_helper<Res (Tp::*)(Args...) noexcept> { using type = function_traits_impl<Res, Args...>; }; template<class Res, class Tp, class... Args> struct function_traits_helper<Res (Tp::*)(Args...)& noexcept> { using type = function_traits_impl<Res, Args...>; }; template<class Res, class Tp, class... Args> struct function_traits_helper<Res (Tp::*)(Args...) const noexcept> { using type = function_traits_impl<Res, Args...>; }; template<class Res, class Tp, class... Args> struct function_traits_helper<Res (Tp::*)(Args...) const& noexcept> { using type = function_traits_impl<Res, Args...>; }; #endif template<class F> using function_traits = typename function_traits_helper< decltype(&std::remove_reference<F>::type::operator())>::type; template<class F> using function_result_type = typename function_traits<F>::result_type; template<class F, std::size_t idx> using function_argument_type = typename function_traits<F>::template argument_type<idx>; template<class F> using function_argument_tuple = typename function_traits<F>::argument_tuple; template<class T> using is_signed_int = std::integral_constant<bool, (std::is_integral<T>::value && std::is_signed<T>::value) || std::is_same<T, i128>::value>; template<class T> using is_unsigned_int = std::integral_constant<bool, (std::is_integral<T>::value && std::is_unsigned<T>::value) || std::is_same<T, u128>::value>; template<class T> using is_int = std::integral_constant<bool, is_signed_int<T>::value || is_unsigned_int<T>::value>; template<class T> using make_signed_int = typename std::conditional< std::is_same<T, i128>::value || std::is_same<T, u128>::value, std::common_type<i128>, std::make_signed<T>>::type; template<class T> using make_unsigned_int = typename std::conditional< std::is_same<T, i128>::value || std::is_same<T, u128>::value, std::common_type<u128>, std::make_unsigned<T>>::type; template<class T, class = void> struct is_range : std::false_type {}; template<class T> struct is_range< T, decltype(all(std::declval<typename std::add_lvalue_reference<T>::type>()), (void)0)> : std::true_type {}; template<class T, bool = is_range<T>::value> struct range_rank : std::integral_constant<std::size_t, 0> {}; template<class T> struct range_rank<T, true> : std::integral_constant<std::size_t, range_rank<typename T::value_type>::value + 1> {}; template<std::size_t size> struct int_least { static_assert(size <= 128, "size must be less than or equal to 128"); using type = typename std::conditional< size <= 8, std::int_least8_t, typename std::conditional< size <= 16, std::int_least16_t, typename std::conditional< size <= 32, std::int_least32_t, typename std::conditional<size <= 64, std::int_least64_t, i128>::type>::type>::type>::type; }; template<std::size_t size> using int_least_t = typename int_least<size>::type; template<std::size_t size> struct uint_least { static_assert(size <= 128, "size must be less than or equal to 128"); using type = typename std::conditional< size <= 8, std::uint_least8_t, typename std::conditional< size <= 16, std::uint_least16_t, typename std::conditional< size <= 32, std::uint_least32_t, typename std::conditional<size <= 64, std::uint_least64_t, u128>::type>::type>::type>::type; }; template<std::size_t size> using uint_least_t = typename uint_least<size>::type; template<class T> using double_size_int = int_least<std::numeric_limits<T>::digits * 2 + 1>; template<class T> using double_size_int_t = typename double_size_int<T>::type; template<class T> using double_size_uint = uint_least<std::numeric_limits<T>::digits * 2>; template<class T> using double_size_uint_t = typename double_size_uint<T>::type; template<class T> using double_size = typename std::conditional<is_signed_int<T>::value, double_size_int<T>, double_size_uint<T>>::type; template<class T> using double_size_t = typename double_size<T>::type; #line 8 "template/out.hpp" struct NumberToString { char buf[10000][4]; constexpr NumberToString() : buf{} { rep (i, 10000) { int n = i; rrep (j, 4) { buf[i][j] = (char)('0' + n % 10); n /= 10; } } } } constexpr precalc_number_to_string; template<std::size_t buf_size = IO_BUFFER_SIZE, bool debug = false> class Printer { private: template<class, bool = debug, class = void> struct has_print : std::false_type {}; template<class T> struct has_print<T, false, decltype(std::declval<T>().print(std::declval<Printer&>()), (void)0)> : std::true_type {}; template<class T> struct has_print<T, true, decltype(std::declval<T>().debug(std::declval<Printer&>()), (void)0)> : std::true_type {}; int fd; std::size_t idx; std::array<char, buf_size> buffer; std::size_t decimal_precision; public: inline void print_char(char c) { #if SHIO_LOCAL buffer[idx++] = c; if (idx == buf_size) flush(); #else if IF_CONSTEXPR (!debug) { buffer[idx++] = c; if (idx == buf_size) flush(); } #endif } inline void flush() { idx = write(fd, buffer.begin(), idx); idx = 0; } Printer(int fd) : fd(fd), idx(0), decimal_precision(16) {} Printer(FILE* fp) : fd(fileno(fp)), idx(0), decimal_precision(16) {} ~Printer() { flush(); } void set_decimal_precision(std::size_t decimal_precision) { this->decimal_precision = decimal_precision; } void print(char c) { if IF_CONSTEXPR (debug) print_char('\''); print_char(c); if IF_CONSTEXPR (debug) print_char('\''); } void print(bool b) { print_char((char)(b + '0')); } void print(const char* a) { if IF_CONSTEXPR (debug) print_char('"'); for (; *a != '\0'; ++a) print_char(*a); if IF_CONSTEXPR (debug) print_char('"'); } template<std::size_t len> void print(const char (&a)[len]) { if IF_CONSTEXPR (debug) print_char('"'); for (auto i : a) print_char(i); if IF_CONSTEXPR (debug) print_char('"'); } void print(const std::string& a) { if IF_CONSTEXPR (debug) print_char('"'); for (auto i : a) print_char(i); if IF_CONSTEXPR (debug) print_char('"'); } template<std::size_t len> void print(const std::bitset<len>& a) { rrep (i, len) print_char((char)(a[i] + '0')); } template<class T, typename std::enable_if<is_int<T>::value && !has_print<T>::value>::type* = nullptr> void print(T a) { if (!a) { print_char('0'); return; } if IF_CONSTEXPR (is_signed_int<T>::value) { if (a < 0) { print_char('-'); using U = typename make_unsigned_int<T>::type; print(static_cast<U>(-static_cast<U>(a))); return; } } if (idx + 40 >= buf_size) flush(); static char s[40]; int t = 40; while (a >= 10000) { int i = a % 10000; a /= 10000; t -= 4; std::memcpy(s + t, precalc_number_to_string.buf[i], 4); } if (a >= 1000) { std::memcpy(buffer.begin() + idx, precalc_number_to_string.buf[a], 4); idx += 4; } else if (a >= 100) { std::memcpy(buffer.begin() + idx, precalc_number_to_string.buf[a] + 1, 3); idx += 3; } else if (a >= 10) { std::memcpy(buffer.begin() + idx, precalc_number_to_string.buf[a] + 2, 2); idx += 2; } else { buffer[idx++] = '0' | a; } std::memcpy(buffer.begin() + idx, s + t, 40 - t); idx += 40 - t; } template<class T, typename std::enable_if<std::is_floating_point<T>::value && !has_print<T>::value>::type* = nullptr> void print(T a) { if (a == std::numeric_limits<T>::infinity()) { print("inf"); return; } if (a == -std::numeric_limits<T>::infinity()) { print("-inf"); return; } if (std::isnan(a)) { print("nan"); return; } if (a < 0) { print_char('-'); a = -a; } T b = a; if (b < 1) { print_char('0'); } else { std::string s; while (b >= 1) { s += (char)('0' + (int)std::fmod(b, 10.0)); b /= 10; } for (auto i = s.rbegin(); i != s.rend(); ++i) print_char(*i); } print_char('.'); rep (decimal_precision) { a *= 10; print_char((char)('0' + (int)std::fmod(a, 10.0))); } } private: template<std::size_t i, class... Args> void print(const std::tuple<Args...>& a) { if IF_CONSTEXPR (i < sizeof...(Args)) { if IF_CONSTEXPR (debug) print_char(','); print_char(' '); print(std::get<i>(a)); print<i + 1, Args...>(a); } } public: template<class... Args> void print(const std::tuple<Args...>& a) { if IF_CONSTEXPR (debug) print_char('('); if IF_CONSTEXPR (sizeof...(Args) != 0) print(std::get<0>(a)); print<1, Args...>(a); if IF_CONSTEXPR (debug) print_char(')'); } template<class T, class U> void print(const std::pair<T, U>& a) { if IF_CONSTEXPR (debug) print_char('('); print(a.first); if IF_CONSTEXPR (debug) print_char(','); print_char(' '); print(a.second); if IF_CONSTEXPR (debug) print_char(')'); } template<class T, typename std::enable_if<is_range<T>::value && !has_print<T>::value>::type* = nullptr> void print(const T& a) { if IF_CONSTEXPR (debug) print_char('{'); for (auto i = std::begin(a); i != std::end(a); ++i) { if (i != std::begin(a)) { if IF_CONSTEXPR (debug) print_char(','); print_char(' '); } print(*i); } if IF_CONSTEXPR (debug) print_char('}'); } template<class T, typename std::enable_if<has_print<T>::value && !debug>::type* = nullptr> void print(const T& a) { a.print(*this); } template<class T, typename std::enable_if<has_print<T>::value && debug>::type* = nullptr> void print(const T& a) { a.debug(*this); } void operator()() {} template<class Head, class... Args> void operator()(const Head& head, const Args&... args) { print(head); operator()(args...); } template<class T> Printer& operator<<(const T& a) { print(a); return *this; } Printer& operator<<(Printer& (*pf)(Printer&)) { return pf(*this); } }; template<std::size_t buf_size, bool debug> Printer<buf_size, debug>& endl(Printer<buf_size, debug>& pr) { pr.print_char('\n'); pr.flush(); return pr; } template<std::size_t buf_size, bool debug> Printer<buf_size, debug>& flush(Printer<buf_size, debug>& pr) { pr.flush(); return pr; } struct SetPrec { int n; template<class Pr> void print(Pr& pr) const { pr.set_decimal_precision(n); } template<class Pr> void debug(Pr& pr) const { pr.set_decimal_precision(n); } }; SetPrec setprec(int n) { return SetPrec{n}; }; Printer<> print(1), eprint(2); void prints() { print.print_char('\n'); } template<class T> auto prints(const T& v) -> decltype(print << v, (void)0) { print << v; print.print_char('\n'); } template<class Head, class... Tail> auto prints(const Head& head, const Tail&... tail) -> decltype(print << head, (void)0) { print << head; print.print_char(' '); prints(tail...); } Printer<IO_BUFFER_SIZE, true> debug(1), edebug(2); void debugs() { debug.print_char('\n'); } template<class T> auto debugs(const T& v) -> decltype(debug << v, (void)0) { debug << v; debug.print_char('\n'); } template<class Head, class... Tail> auto debugs(const Head& head, const Tail&... tail) -> decltype(debug << head, (void)0) { debug << head; debug.print_char(' '); debugs(tail...); }