上一期的函数库有许多人投诉啊，我们这次给出最新版本的好吧。（如果需要实时最新，可以点我个人题库里的“函数库存放地”题目，找到最新的提交记录就是了。）
@Lin.Zikang能帮忙让GPT-5.6 Sol找一下漏洞吗，谢谢。

#pragma GCC optimize("Ofast,inline,omit-frame-pointer,tree-vectorize,tree-slp-vectorize,vect-cost-model=dynamic,ivopts,tree-loop-optimize,tree-loop-distribution,tree-loop-im,tree-loop-ivcanon,loop-interchange,loop-unroll-and-jam,predictive-commoning,tree-dse,tree-fre,tree-sra,tree-ter,tree-copy-prop,tree-ccp,tree-ch,isolate-erroneous-paths,split-loops,split-paths,reassociate,schedule-insns,schedule-insns2,cse-follow-jumps,cse-skip-blocks,gcse-after-reload,gcse-lm,hoist-adjacent-loads,ipa-cp,ipa-cp-clone,ipa-bit-cp,ipa-vrp,ipa-pta,ipa-sra,ipa-icf,ipa-icf-functions,ipa-icf-variables,ipa-profile,ipa-pure-const,ipa-reference,ipa-modref,ipa-jump-function,ipa-devirt,ipa-strlen,fgraphite,fgraphite-identity,floop-nest-optimize,floop-parallelize-all,ftree-parallelize-loops=4,frename-registers,fweb,fira-hoist-pressure,fira-loop-pressure,flto,flto-partition=max,flto-compression-level=9,fuse-linker-plugin,fno-stack-protector,fno-stack-protector-all,fno-stack-check,fno-omit-frame-pointer")
#pragma GCC target("avx512f", "avx512vl", "sse", "sse2", "sse3", "ssse3", "sse4", "sse4.1", "sse4.2", "popcnt", "abm", "mmx", "avx", "avx2", "fma", "bmi", "bmi2", "lzcnt", "tune=native")
extern "C" long read(int, void *, unsigned long);
extern "C" long write(int, const void *, unsigned long);
typedef long long ll;
typedef long long ssize_t;
typedef unsigned long long ull;
typedef unsigned long long size_t;
typedef double lf;
typedef __builtin_va_list va_list;
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
#define fnlikely(cond) __builtin_unpredictable((cond))
#define memcpy(r1, s, len) __builtin_memcpy((r1), (s), (len))
#define strlen(r1) __builtin_strlen((r1))
#define memcmp(s1, s2, n) __builtin_memcmp((s1), (s2), (n))
#define strcmp(s1, s2) __builtin_strcmp((s1), (s2))
#define strstr(s1, s2) __builtin_strstr((s1), (s2))
#define abs(x) __builtin_llabs(x)
#define sin(x) __builtin_sin((x))
#define cos(x) __builtin_cos((x))
#define clz(x) __builtin_clz((x))
#define clzll(x) __builtin_clzll((x))
#define ctz(x) __builtin_ctz((x))
#define ctzll(x) __builtin_ctzll((x))
#define ffs(x) __builtin_ffs((x))
#define parity(x) __builtin_parity((x))
#define ceil(x) __builtin_ceil((x))
#define floor(x) __builtin_floor((x))
#define round(x) __builtin_round((x))
#define roundll(x) __builtin_roundll((x))
#define exp(x) __builtin_exp((x))
#define exp2(x) __builtin_exp2((x))
#define acos(x) __builtin_acos((x))
#define types_compatible_p(type1, type2) __builtin_types_compatible_p((type1), (type2))
#define constant_p(expr) __builtin_constant_p((expr))
#define assume(cond) __builtin_assume((cond))
#define unreachable(x) __builtin_unreachable((x))
#define popcount(x) __builtin_popcount((x))
#define popcountll(x) __builtin_popcountll((x))
#define add_overflow(x, y, result) __builtin_add_overflow((x), (y), (&result))
#define mul_overflow(x, y, result) __builtin_mul_overflow((x), (y), (&result))
#define bswap16(x) __builtin_bswap16((x))
#define bswap32(x) __builtin_bswap32((x))
#define bswap64(x) __builtin_bswap64((x))
#define assume_aligned(ptr, align) __builtin_assume_aligned((ptr), (align))
#define prefetch(a,b,c) __builtin_prefetch(a,b,c)
#define ln(x) __builtin_log((x))
#define log2(x) __builtin_log2((x))
#define va_arg(a,b) __builtin_va_arg(a,b)
#define va_start(ap, last) __builtin_va_start((ap), (last))
#define va_end(ap)         __builtin_va_end((ap))
#define va_copy(dest, src) __builtin_va_copy((dest), (src))
#define EOF (-1)
#define elif else if
#define LLONG_MAX 9223372036854775807LL
#define ULLONG_MAX 18446744073709551615ULL
#define LLONG_MIN (-9223372036854775807LL-1LL)
#define INT_MAX 2147483647
#define INT_MIN (-2147483647-1)
#define UINT_MAX 4294967295U
#define NAN __builtin_nan("0x7fc00000")
template <typename T>
__attribute__((always_inline))
inline T max(T a,T b){return a>b?a:b;}
template <typename T>
__attribute__((always_inline))
inline T min(T a,T b){return a<b?a:b;}
static const lf pi = acos(-1.0), e = exp(1.0);
inline lf log(lf x,lf n){if(n==2)return log2(x);if(n==e)return ln(x);return ln(x) / ln(n);}
static char _rbuf[1 << 16] __attribute__((aligned(64)));
static char* _rptr = _rbuf;static char* _rend = _rbuf;
__attribute__((always_inline))
static inline char _gc() {
    if (unlikely(_rptr == _rend)) {
        ssize_t bytes_read = read(0, _rbuf, sizeof(_rbuf));
        _rend = _rbuf + bytes_read; _rptr = _rbuf;
        if (unlikely(bytes_read <= 0)) return EOF;
    }
    return *_rptr++;
}
static char _wbuf[1 << 16] __attribute__((aligned(64)));
static char* _wptr = _wbuf;
__attribute__((always_inline))
static inline void _pc(char c) {
    if (unlikely(_wptr == _wbuf + sizeof(_wbuf))) {
        write(1, _wbuf, _wptr - _wbuf);
        _wptr = _wbuf;
    }
    *_wptr++ = c;
}
__attribute__((always_inline))
static inline void _return() {
    if (likely(_wptr != _wbuf)) {
        write(1, _wbuf, _wptr - _wbuf);
        _wptr = _wbuf;
    }
}
namespace std {
template<typename T>
struct remove_reference { using type = T; };
template<typename T>
struct remove_reference<T&> { using type = T; };
template<typename T>
struct remove_reference<T&&> { using type = T; };
template<typename T>
using remove_reference_t = typename remove_reference<T>::type;
template<typename T>
constexpr remove_reference_t<T>&& move(T&& t) noexcept {return static_cast<remove_reference_t<T>&&>(t);}
template<typename T>
constexpr T&& forward(remove_reference_t<T>& t) noexcept {return static_cast<T&&>(t);}
template<typename T>
constexpr T&& forward(remove_reference_t<T>&& t) noexcept {return static_cast<T&&>(t);}
template<typename R1, typename R2>
struct tie_type {R1& first;R2& second;};
template<typename R1, typename R2>
constexpr tie_type<R1, R2> tie(R1& a, R2& b) {return tie_type<R1, R2>{a, b};}
template <typename T>
__attribute__((always_inline))
inline void swap(T& a, T& b) {T t = move(a); a = move(b); b = move(t);}
template<typename T1, typename T2>
struct pair {
    T1 first,second;
    constexpr pair() : first(), second() {}
    template<typename U1, typename U2>
    constexpr pair(U1&& a, U2&& b): first(forward<U1>(a)), second(forward<U2>(b)) {}
    constexpr pair(const pair& other): first(other.first), second(other.second) {}
    pair(pair&& other) noexcept: first(move(other.first)), second(move(other.second)) {}
    pair& operator=(const pair& other) {if (this != &other) {first = other.first;second = other.second;}return *this;}
    pair& operator=(pair&& other) noexcept {
        if (this != &other) {
            first = move(other.first);
            second = move(other.second);
        }
        return *this;
    }
    template<typename R1, typename R2>
    pair& operator=(const tie_type<R1, R2>& t) {first = t.first;second = t.second;return *this;}
    constexpr bool operator==(const pair& other) const {return first == other.first && second == other.second;}
    constexpr bool operator!=(const pair& other) const {return !(*this == other);}
    constexpr bool operator<(const pair& other) const {return first < other.first || (!(other.first < first) && second < other.second);}
};
template<typename T1, typename T2>
constexpr pair<remove_reference_t<T1>, remove_reference_t<T2>>
make_pair(T1&& a, T2&& b) {return pair<remove_reference_t<T1>, remove_reference_t<T2>>(forward<T1>(a), forward<T2>(b));}
template<typename T>
struct vector {
    T* data;
    size_t sz,cap;
    typedef T* iterator;
    typedef const T* const_iterator;
    iterator begin() { return data; }
    iterator end() { return data + sz; }
    const_iterator begin() const { return data; }
    const_iterator end() const { return data + sz; }
    vector() : data(nullptr), sz(0), cap(0) {}
    explicit vector(size_t n) : data(new T[n]), sz(n), cap(n) { for (size_t i = 0; i < n; i++) data[i] = T(); }
    vector(size_t n, const T& value) : data(new T[n]), sz(n), cap(n) { for (size_t i = 0; i < n; i++) data[i] = value; }
    vector(const vector& other) : data(new T[other.cap]), sz(other.sz), cap(other.cap) { for (size_t i = 0; i < sz; i++) data[i] = other.data[i]; }
    vector(vector&& other) noexcept : data(other.data), sz(other.sz), cap(other.cap) {other.data = nullptr;other.sz = other.cap = 0;}
    vector& operator=(const vector& other) {
        if (this != &other) {
            delete[] data;
            cap = other.cap;
            sz = other.sz;
            data = new T[cap];
            for (size_t i = 0; i < sz; i++) data[i] = other.data[i];
        }
        return *this;
    }
    vector& operator=(vector&& other) noexcept {
        if (this != &other) {
            delete[] data;
            data = other.data;sz = other.sz;cap = other.cap;
            other.data = nullptr;other.cap = other.sz = 0;
        }
        return *this;
    }
    ~vector() { delete[] data; }
    void push_back(const T& value) {
        if (sz == cap) {size_t new_cap = (cap == 0) ? 1 : cap * 2;reserve(new_cap);}
        data[sz++] = value;
    }
    void push_back(T&& value) {
        if (sz == cap) reserve(cap * 2);
        data[sz++] = move(value);
    }
    void pop_back() { if (sz > 0) sz--; }
    void reserve(size_t new_cap) {
        if (new_cap <= cap) return;
        T* new_data = new T[new_cap];
        for (size_t i = 0; i < sz; i++) new_data[i] = move(data[i]);
        delete[] data;
        data = new_data;
        cap = new_cap;
    }
    void resize(size_t new_sz, const T& value = T()) {
        if (new_sz > cap) reserve(new_sz * 2);
        for (size_t i = sz; i < new_sz; i++) data[i] = value;
        sz = new_sz;
    }
    T& at(size_t index) { return data[index]; }
    T& operator[](size_t index) { return data[index]; }
    const T& operator[](size_t index) const { return data[index]; }
    T& front() { return data[0]; }
    T& back() { return data[sz - 1]; }
    size_t size() const { return sz; }
    size_t capacity() const { return cap; }
    bool empty() const { return sz == 0; }
    void clear() { sz = 0; }
};
struct string {
    char* data;
    size_t len;
    size_t capacity;
    string() : len(0), capacity(1) {data = new char[capacity];data[0] = '\0';}
    ~string() {delete[] data;}
    string(const char* s) {
        if (!s) {
            len = 0;
            capacity = 1;
            data = new char[capacity];
            data[0] = '\0';
            return;
        }
        len = strlen(s);
        capacity = len + 1;
        data = new char[capacity];
        memcpy(data, s, len + 1);
    }
    string(const string& other) : len(other.len), capacity(other.capacity) {
        data = new char[capacity];
        memcpy(data, other.data, len + 1);
    }
    string(string&& other) noexcept 
        : data(other.data), len(other.len), capacity(other.capacity) {
        other.data = nullptr;
        other.len = 0;
        other.capacity = 1;
        other.data = new char[1];
        other.data[0] = '\0';
    }
    string& operator=(const string& other) {
        if (this != &other) {
            delete[] data;
            len = other.len;
            capacity = other.capacity;
            data = new char[capacity];
            memcpy(data, other.data, len + 1);
        }
        return *this;
    }
    string& operator=(string&& other) noexcept {
        if (this != &other) {
            delete[] data;
            data = other.data;
            len = other.len;
            capacity = other.capacity;
            other.data = nullptr;
            other.len = 0;
            other.capacity = 1;
            other.data = new char[1];
            other.data[0] = '\0';
        }
        return *this;
    }
    inline int size() const { return (int)len; }
    inline bool empty() const { return len == 0; }
    inline void clear() { len = 0; data[0] = '\0'; }
    char* begin() { return data; }
    char* end() { return data + len; }
    const char* begin() const { return data; }
    const char* end() const { return data + len; }
    inline const char* c_str() const { return data; }
    inline char& operator[](int i) { return data[i]; }
    inline const char& operator[](int i) const { return data[i]; }
    inline void push_back(char c) {
        if (len + 1 >= capacity) {
            size_t new_capacity = capacity * 2;
            char* new_data = new char[new_capacity];
            memcpy(new_data, data, len);
            delete[] data;
            data = new_data;
            capacity = new_capacity;
        }
        data[len++] = c;
        data[len] = '\0';
    }
    inline int find(const string& sub) const {
        if (sub.len == 0) return 0;
        if (len < sub.len) return -1;
        const char* pos = strstr(data, sub.data);
        if (pos == nullptr) return -1;
        return (int)(pos - data);
    }
    inline int find(const char* sub) const {
        if (!sub || sub[0] == '\0') return 0;
        const char* pos = strstr(data, sub);
        if (pos == nullptr) return -1;
        return (int)(pos - data);
    }
    inline string substr(size_t pos, size_t len = (size_t)-1) const {
        if (pos >= len) return string(); 
        size_t actual_len = len - pos;
        if (len < actual_len) actual_len = len;
        string result;
        if (actual_len + 1 > result.capacity) {
            delete[] result.data;
            result.capacity = actual_len + 1;
            result.data = new char[result.capacity];
        }
        memcpy(result.data, data + pos, actual_len);
        result.data[actual_len] = '\0';
        result.len = actual_len;
        return result;
    }
    string& operator+=(const string& other) {
        if (other.len == 0) return *this;
        if (len + other.len >= capacity) {
            size_t new_capacity = (len + other.len + 1) * 2;
            char* new_data = new char[new_capacity];
            memcpy(new_data, data, len);
            delete[] data;
            data = new_data;
            capacity = new_capacity;
        }
        memcpy(data + len, other.data, other.len + 1); // +1 复制 '\0'
        len += other.len;
        return *this;
    }
    string& operator+=(const char* s) {
        if (!s) return *this;
        size_t other_size = strlen(s);
        if (other_size == 0) return *this;
        if (len + other_size >= capacity) {
            size_t new_capacity = (len + other_size + 1) * 2;
            char* new_data = new char[new_capacity];
            memcpy(new_data, data, len);
            delete[] data;
            data = new_data;
            capacity = new_capacity;
        }
        memcpy(data + len, s, other_size + 1);
        len += other_size;
        return *this;
    }
    string& operator+=(char c) {
        push_back(c);
        return *this;
    }
    inline void reverse() {
    if (len <= 1) return;
    size_t left = 0;
    size_t right = len - 1;
    while (left < right) {
        char temp = data[left];
        data[left] = data[right];
        data[right] = temp;
        left++;
        right--;
    }
}
};
inline string operator+(const string& lhs, const string& rhs) {
    string res = lhs;
    res += rhs;
    return res;
}
inline string operator+(const char* s, const string& str) {
    string res(s);
    res += str;
    return res;
}
inline string operator+(char c, const string& str) {
    string res;
    res.push_back(c);
    res += str;
    return res;
}
inline string operator+(const string& str, const char* s) {
    string res = str;
    res += s;
    return res;
}
inline string operator+(const string& str, char c) {
    string res = str;
    res.push_back(c);
    return res;
}
__attribute__((always_inline))
inline string read_s() {
    string a;
    char c = _gc();
    while (c <= 32) {
        if (c == EOF) return a;
        c = _gc();
    }
    while (c > 32) {
        if (a.len + 1 >= a.capacity) {
            size_t new_capacity = a.capacity * 2;
            char* new_data = new char[new_capacity];
            memcpy(new_data, a.data, a.len);
            delete[] a.data;
            a.data = new_data;
            a.capacity = new_capacity;
        }
        a.data[a.len++] = c;
        c = _gc();
    }
    a.data[a.len] = '\0';
    return a;
}
__attribute__((always_inline))
inline void getline(string& s) {
    s.clear();
    char c = _gc();
    while (c != '\n' && c != '\r' && c != EOF) {
        if (s.len + 1 >= s.capacity) {
            size_t new_capacity = s.capacity * 2;
            char* new_data = new char[new_capacity];
            memcpy(new_data, s.data, s.len);
            delete[] s.data;
            s.data = new_data;
            s.capacity = new_capacity;
        }
        s.data[s.len++] = c;
        c = _gc();
    }
    s.data[s.len] = '\0';
}
}; // string 类型 字符串 和 vector
using namespace std;
namespace Code{
__attribute__((always_inline))
inline ll read_d() {
    ll x = 0;
    int f = 1;
    char c = _gc();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = _gc();
        if (unlikely(c == EOF)) break;
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48); 
        c = _gc();
    }
    return f == 1 ? x : -x;
}
__attribute__((always_inline))
inline lf read_f() {
    ll ip = 0;
    lf f = 1.00;
    char c = _gc();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1.00;
        c = _gc();
        if (unlikely(c == EOF)) break;
    }
    while (c >= '0' && c <= '9') {
        ip = (ip << 3) + (ip << 1) + (c ^ 48); 
        c = _gc(); // 此时 c 已经是小数点或者分隔符（如空格）
    }
    lf fp = 0.00, base = 0.1;
    if (c == '.') {
        c = _gc(); // 只有确认是小数点后，才读取下一位小数
        while (c >= '0' && c <= '9') {
            fp += (c ^ 48) * base;
            base *= 0.1;
            c = _gc();
        }
    }
    return double(ip + fp) * f;
}
inline void scanf(const char* fmt, ...) {
        va_list args;
        va_start(args, fmt);
        char c;
        while (*fmt) {
            if (*fmt == '%') {
                fmt++;
                if (!*fmt) break;
                if (*fmt == 's') {
                    string* s = va_arg(args, string*);
                    s -> clear();
                    c = _gc();
                    while (c <= 32) { if (c == EOF) goto end; c = _gc(); }
                    while (c > 32) {
                        s->push_back(c);
                        c = _gc();
                        if(c == -1) break;
                    }
                }else if (*fmt == 'd') {
                    ll* val = va_arg(args, ll*);
                    *val = read_d();
                }else if (*fmt == 'c') {
                    char* val = va_arg(args, char*);
                    *val = _gc();
                }else if (*fmt == 'l') {
                    if (*(fmt+1) == 'f') {
                        fmt++;
                        lf* val = va_arg(args, lf*);
                        *val = read_f();
                    }
                }else if (*fmt == 'f') {
                     lf temp = read_f();
                     float* val = va_arg(args, float*);
                     *val = (float)temp;
                }
            } else {
                c = _gc();
                while (c <= 32 && *fmt != '%') c = _gc();
            }
            fmt++;
        }
        end:
        va_end(args);
    }
__attribute__((always_inline))
inline void out(ll x) {
    if (x == 0) { _pc('0'); return; }
    if (x < 0) { _pc('-'); x = -x; }
    char buf[25]; 
    char* ptr = buf + 24;
    *ptr = '\0';
    while (x > 0) { *--ptr = '0' + (char)(x % 10); x /= 10; }
    while (*ptr) _pc(*ptr++);
}
__attribute__((always_inline))
inline void out(int x) { out((ll)x); }
__attribute__((always_inline))
inline void out(unsigned int x) { out((ll)x); }
__attribute__((always_inline))
inline void out(ull x) {
    if (x == 0) { _pc('0'); return; }
    char buf[25]; 
    char* ptr = buf + 24;
    *ptr = '\0';
    while (x > 0) { *--ptr = '0' + (char)(x % 10); x /= 10; }
    while (*ptr) _pc(*ptr++);
}
inline void write_p(lf x,const int& max_decimal) {
    if (x == 0.0) { _pc('0'); return; }
    if (x < 0) { _pc('-'); x = -x; }
    ll int_part = (ll)x;
    out(int_part);
    if (max_decimal <= 0) return;
    _pc('.');
    lf frac_part = x - (lf)int_part;
    for (int i = 0; i < max_decimal; i++) {
        frac_part *= 10.0;
        ll digit = (ll)frac_part;
        _pc('0' + (char)digit);
        frac_part -= (lf)digit;
    }
}
inline void out(const lf& x) { write_p(x, 16); }
inline void out(const float& x) { write_p(x, 8); }
inline void out(const string& a) { const char* p = a.data; for (size_t i = 0; i < a.len; ++i) _pc(p[i]); }
__attribute__((always_inline))
inline void out(const bool& val) { out(val?"true":"false"); }
__attribute__((always_inline))
inline void out(const char& val) { _pc(val); }
__attribute__((always_inline))
inline void out(const char* val) { string s=val; out(s); }
void printf(const char* fmt, ...) {
    va_list args;
    va_start(args, fmt);
    while (*fmt) {
        if (*fmt == '%') {
            fmt++; 
            if (!*fmt) break;
            ll precision = -1;
            if (*fmt == '.' && *(fmt+1) == '*') fmt += 2,precision = va_arg(args, ll);
            else if (*fmt == '.') {
                fmt++;
                ll p = 0;
                bool has_digit = false;
                while(*fmt >= '0' && *fmt <= '9') {
                    p=(p<<3)+(p<<1)+(*fmt - '0');
                    fmt++;
                    has_digit=true;
                }
                if(has_digit)precision=p;
            }
            switch (*fmt) {
                case 'd':
                case 'i':
                    out((ll)va_arg(args, ll));
                    break;
                case 'l':
                    if (*(fmt+1) == 'd') {
                        out(va_arg(args, ll));
                        fmt++;
                    } else out((ll)va_arg(args, ll));
                    break;
                case 'L':
                     if (*(fmt+1) == 'd') {
                        out(va_arg(args, ll));
                        fmt++;
                     }
                     break;
                case 'f':
                case 'F':
                case 'g':
                case 'G':
                    if (precision >= 0) write_p(va_arg(args, lf), precision);
                    else out(va_arg(args, lf));
                    break;
                case 's': {
                    const char* s = va_arg(args, const char*);
                    out(s);
                    break;
                }
                case 'c':
                    _pc((char)va_arg(args, int));
                    break;
                case '%':
                    _pc('%');
                    break;
                default:
                    _pc('%');
                    _pc(*fmt);
                    break;
            }
        } else if (*fmt == '\\') {
            fmt++;
            if (!*fmt) break;
            switch (*fmt) {
                case 'n': _pc('\n'); break;
                case 't': _pc('\t'); break;
                case 'r': _pc('\r'); break;
                case '\\': _pc('\\'); break;
                case '"': _pc('"'); break;
                default: 
                    _pc('\\'); 
                    _pc(*fmt); 
                    break;
            }
        } else _pc(*fmt);
        fmt++;
    }
    va_end(args);
}
};
using namespace Code; // C语言输出输入工具
namespace math {
    __attribute__((always_inline))
    inline lf pow(lf a, lf b) {
        if(unlikely(b==0))return 1;
        if(unlikely(b==1))return a;
        if(unlikely(b*2==1))return __builtin_sqrt(a);
        if(unlikely(b*3==1))return __builtin_cbrt(a);
        if(unlikely(b==-1))return 1.0L/a;
        return __builtin_pow(a,b);
    }
    lf sqrt(lf x, lf n) {
        if (unlikely(n == 0 || x == 0)) return 0;
        if (unlikely(n == 1)) return x;
        if (likely(n == 2)) return __builtin_sqrt(x);
        if (likely(n == 3)) return __builtin_cbrt(x);
        if (unlikely(x < 0 && static_cast<long long>(n) % 2 == 0)) return NAN;
        long double y = x,prev_y;
        const long double epsilon = 1e-15L;
        do{ prev_y = y;
            long double y_power_n_minus_1 = 1.0L;
            for (int i = 0; i < static_cast<int>(n) - 1; ++i) y_power_n_minus_1 *= prev_y;
            y = ((n - 1) * prev_y + x / y_power_n_minus_1) / n;
        } while (y > prev_y ? y - prev_y > epsilon : prev_y - y > epsilon);
        return y;
    }
__attribute__((always_inline))
inline ll gcd(ll a, ll b) {
    if (a == 0) return b;
    if (b == 0) return a;
    ll shift = ctz(a | b);
    a >>= ctz(a);
    b >>= ctz(b);
    while (a != b) {
        if (a > b) swap(a, b);
        b -= a;
        b >>= ctz(b);
    }
    return a << shift;
}
    inline ll lcm(ll a, ll b) {
        if (a == 0 || b == 0) return 0;
        return a / gcd(a, b) * b;
    }
template<typename T>
struct less {bool operator()(const T& a, const T& b) const { return a < b; }};
template<typename T, typename Compare>
__attribute__((always_inline))
void insertion_sort(T a[],int begin,int end,Compare cmp){
    for(int i=begin+1;i<=end;i++){
        T k=move(a[i]);
        int left=begin,right=i-1,pos=i;
        while(left<=right){
            int mid=(right+left)>>1;
            if(cmp(k,a[mid])){
                right=mid-1;
                pos=mid;
            }else left=mid+1;
        }
        for(int j=i;j>pos;j--)a[j]=move(a[j-1]);
        a[pos]=k;
    }
}
template<typename T>
struct run { int l,r; inline int len()const{return r-l+1;} };
template<typename T, typename C>
__attribute__((always_inline))
inline int find_run(T a[],int n,int st,C cmp){
    if(st>=n-1)return 1;
    bool up=!cmp(a[st+1],a[st]);
    int i=st;
    if(up) while(i<n-1&&!cmp(a[i+1],a[i])) i++;
    else{
        while(i<n-1&&cmp(a[i+1],a[i])) i++;
        int l=st,r=i;
        while(l<r){T t=move(a[l]);a[l]=move(a[r]);a[r]=move(t);l++;r--;}
    }
    return i-st+1;
}
template<typename T, typename C>
__attribute__((always_inline))
inline int get_runs(T a[],int n,run<T>* rs,C cmp){
    int cnt=0,i=0;
    while(i<n){int len=find_run(a,n,i,cmp);rs[cnt].l=i;rs[cnt].r=i+len-1;cnt++;i+=len;}
    return cnt;
}
template<typename T, typename C>
__attribute__((always_inline))
inline void merge_run(T a[],int l1,int r1,int l2,int r2,C cmp){
    int n1=r1-l1+1,n2=r2-l2+1,tot=n1+n2;
    const int SL=4096;
    T stk[SL];
    T* tmp=(tot<=SL)?stk:new T[tot];
    int i=l1,j=l2,k=0;
    while(i<=r1&&j<=r2){
        if(cmp(a[i],a[j])) tmp[k++]=move(a[i++]);
        else tmp[k++]=move(a[j++]);
    }
    while(i<=r1) tmp[k++]=move(a[i++]);
    while(j<=r2) tmp[k++]=move(a[j++]);
    for(int t=0;t<tot;t++) a[l1+t]=move(tmp[t]);
    if(tot>SL) delete[] tmp;
}
template<typename T>
__attribute__((always_inline))
inline int best_pair(run<T>* rs,int cnt){
    if(cnt<=1)return -1;
    if(cnt==2)return 0;
    int bi=0;lf bp=-1.0;
    for(int i=0;i<cnt-1;i++){
        int l1=rs[i].len(),l2=rs[i+1].len();
        lf rt=(l1<l2)?(lf)l1/l2:(lf)l2/l1;
        lf pw=rt*0.7+(1.0-(lf)i/(cnt-1))*0.3;
        if(pw>bp){bp=pw;bi=i;}
    }
    return bi;
}
template<typename T, typename C>
__attribute__((always_inline))
inline void power_sort(T a[],int n,C cmp){
    if(n<=1)return;
    if(n<=16){insertion_sort(a,0,n-1,cmp);return;}
    const int MR=2048;
    run<T> rs[MR];
    int cnt=get_runs(a,n,rs,cmp);
    if(cnt<=1)return;
    if(cnt==2){merge_run(a,rs[0].l,rs[0].r,rs[1].l,rs[1].r,cmp);return;}
    while(cnt>1){
        int id=best_pair(rs,cnt);
        if(id<0)break;
        merge_run(a,rs[id].l,rs[id].r,rs[id+1].l,rs[id+1].r,cmp);
        rs[id].r=rs[id+1].r;
        for(int i=id+1;i<cnt-1;i++) rs[i]=rs[i+1];
        cnt--;
    }
}
template<typename T, typename C>
__attribute__((always_inline))
inline bool use_power(T a[],int l,int r,C cmp){
    int n=r-l+1;
    if(n<=64)return 0;
    int sm=min(n/16,128),ok=0;
    for(int i=0;i<sm-1;i++){int p=l+(i*n/sm);if(!cmp(a[p+1],a[p]))ok++;}
    return (lf)ok/sm>0.3;
}
template<typename T,typename C=less<T>>
void mergesort(T a[],int l,int r,C cmp=C()){
    if(l>=r)return;
    int n=r-l+1;
    if(use_power(a,l,r,cmp)){power_sort(a+l,n,cmp);return;}
    for(int i=l;i<r+16;i+=16)insertion_sort(a,i,min(i+15,r),cmp);
    vector<pair<int,int>> b;
    for(int i=l;i<=r;i+=16)b.push_back({i,min(i+15,r)});
    T* t=new T[n];
    while(b.size()>1){
        vector<pair<int,int>> nb;
        for(size_t i=0;i<b.size();i+=4){
            size_t st=i,ed=min(i+3,b.size()-1);
            int cnt=ed-st+1;
            int L=b[st].first,R=b[ed].second;
            int idx[4],bs[4],be[4];
            for(int j=0;j<cnt;j++){bs[j]=b[st+j].first;be[j]=b[st+j].second;idx[j]=bs[j];}
            int p=0;
            while(1){
                int mb=-1;
                for(int j=0;j<cnt;j++)
                    if(idx[j]<=be[j]&&(mb==-1||cmp(a[idx[j]],a[idx[mb]]))) mb=j;
                if(mb==-1)break;
                t[p++]=move(a[idx[mb]++]);
            }
            for(int j=0;j<p;j++)a[L+j]=t[j];
            nb.push_back({L,R});
        }
        b=move(nb);
    }
    delete[] t;
}
template<typename T, typename Compare>
__attribute__((always_inline))
inline void sort3(T& a, T& b, T& c, Compare cmp) {
    if(cmp(b, a))swap(a, b);
    if(cmp(c, b))swap(b, c);
    if(cmp(b, a))swap(a, b);
}
template<typename T, typename Compare>
inline void five_way_partition(T a[], int l, int h, Compare cmp, int& new_l, int& new_h) {
    if (h - l > 1000) {
        int step=(h-l)>>3,idx[8];
        for(int i=0;i<8;++i)idx[i]=l+i*step;
        sort3(a[idx[0]], a[idx[1]], a[idx[2]], cmp);
        sort3(a[idx[3]], a[idx[4]], a[idx[5]], cmp);
        sort3(a[idx[6]], a[idx[7]], a[h], cmp);
        sort3(a[idx[0]], a[idx[3]], a[idx[6]], cmp);
        sort3(a[idx[2]], a[idx[4]], a[idx[7]], cmp);
        sort3(a[idx[1]], a[idx[5]], a[h], cmp);
        sort3(a[idx[2]], a[idx[4]], a[idx[5]], cmp);
        sort3(a[idx[3]], a[idx[4]], a[idx[5]], cmp);
        sort3(a[idx[4]], a[idx[7]], a[h], cmp);
    } else sort3(a[l], a[(l+h)>>1], a[h], cmp);
    T p1 = move(a[l]), p2 = move(a[h]);
    int e1 = l + 1, k = l + 1, g = h - 1, e2 = h - 1;
    while (k <= g) {
        bool cmp_p1=cmp(a[k], p1),cmp_p2=cmp(a[k], p2);
        if (cmp_p1) swap(a[k], a[e1]),e1++,k++;
        else if (cmp_p2) {
            while (k <= g && cmp(p2, a[g])) g--;
            if (k > g) break;
            swap(a[k], a[g]),g--;
        } else {
            if (!cmp(p1, a[k]) && !cmp_p1) swap(a[k], a[e1]),e1++,k++;
            else if (!cmp(p2, a[k]) && !cmp_p2) swap(a[k], a[e2]),e2--;
            else k++;
        }
    }
    new_l = e1 - 1,new_h = e2 + 1,swap(a[l], a[new_l]),swap(a[h], a[new_h]);
}
template<typename T, typename Compare>
void introsort_logic(T a[], int begin, int end, Compare cmp, int d) {
    while (end - begin + 1 > 16) {
        int i = begin,cnt=0,is=0;
        while (i < end) {
            int run_start = i;
            bool is_ascending = true;
            while (i < end && !cmp(a[i], a[i + 1]) && !cmp(a[i + 1], a[i])) i++;
            if (i < end) is_ascending = !cmp(a[i + 1], a[i]);
            if (is_ascending) while (i < end && !cmp(a[i + 1], a[i])) i++;
            else {
                while (i < end && !cmp(a[i], a[i + 1])) i++;
                int l = run_start, r = i;is=1;
                while (l < r)swap(a[l], a[r]),l++,r--;
            }
            cnt++,i++;
        }
        if(cnt==1)return;
        if (cnt == 2) {
            int run1_start = begin;
            int run1_end = run1_start;
            while (run1_end < end && !cmp(a[run1_end + 1], a[run1_end])) run1_end++;
            int run2_start = run1_end + 1;
            int run2_end = end;
            if (!cmp(a[run2_start], a[run1_end])) return;
            int len1 = run1_end - run1_start + 1,len2 = run2_end - run2_start + 1;
            int total = len1 + len2;
            const int STACK_LIMIT = 1024;
            T temp_stack[STACK_LIMIT];
            T* temp = (total <= STACK_LIMIT) ? temp_stack : new T[total];
            int i = run1_start, j = run2_start, k = 0;
            while (i <= run1_end && j <= run2_end) {
                if (cmp(a[i], a[j])) temp[k++] = move(a[i++]);
                else temp[k++] = move(a[j++]);
            }
            while (i <= run1_end) temp[k++] = move(a[i++]);
            while (j <= run2_end) temp[k++] = move(a[j++]);
            for (int t = 0; t < total; t++) a[run1_start + t] = move(temp[t]);
            if (total > STACK_LIMIT) delete[] temp;
            return;
        }
        if(is==1){
            int l=begin,r=end,flag=1;
            while(l<r){
                if(!cmp(a[l],a[l+1]) || !cmp(a[r-1],a[r])){flag=0;break;}
                l++,r--;
            }
            if(flag)return;
        }
        if (d == 0) {
            mergesort(a,begin,end,cmp);
            return;
        }
        d--;
        int lp, rp;
        five_way_partition(a, begin, end, cmp, lp, rp);
        introsort_logic(a, begin, lp - 1, cmp, d);
        introsort_logic(a, lp + 1, rp - 1, cmp, d);
        begin = rp + 1;
    }
    insertion_sort(a, begin, end, cmp);
}
template<typename T, typename Compare = less<T>>
void sort(T a[], int begin, int end, Compare cmp = Compare()) {
    if (begin >= end) return;
    introsort_logic(a, begin, end, cmp, (int)log(end-begin+1,3)<<1);
}
};
using namespace math;
struct IO{
    template <typename T>
    IO& operator<<(const T& val){ out(val); return *this; }
    IO& operator>>(int& val) { val=read_d(); return *this; }
    IO& operator>>(ll& val) { val=read_d(); return *this; }
    IO& operator>>(float& val) { val=read_f(); return *this; }
    IO& operator>>(lf& val) { val=read_f(); return *this; }
    IO& operator>>(string& val) { val=read_s(); return *this; }
    IO& operator>>(char& val) { val=_gc(); return *this; }
};
IO cin,cout;
int main(){
    prefetch(_rbuf, 0, 3);
    prefetch(_wbuf, 0, 3);
    
    _return();
}

点个赞吧~