// <zgood> -*- Bate&doubao -*-  For Windows only! 仅适配Windows系统! 
#include<bits/stdc++.h>
#include<windows.h>
//注意！！！sab函数控制改到 信息：308行 sabset() 
using namespace std;
// 核心功能：整合版本查询、格式化输出（含多类型逐字输出）、进制转换、数学工具等常用功能
// 设计思路：内部逻辑封装到InternalUtil命名空间，对外暴露简洁接口，保证旧代码零修改使用
/**
 * @brief 设置控制台输出文本的颜色（前景色+背景色）
 * @param bgRed_1_ 背景色是否为红色，默认false
 * @param bgGreen_1_ 背景色是否为绿色，默认false
 * @param bgBlue_1_ 背景色是否为蓝色，默认false
 * @param bgLight_1_ 背景色是否高亮，默认false
 * @param fgRed_1_ 前景色（文字）是否为红色，默认true
 * @param fgGreen_1_ 前景色（文字）是否为绿色，默认true
 * @param fgBlue_1_ 前景色（文字）是否为蓝色，默认true
 * @param fgLight_1_ 前景色（文字）是否高亮，默认false
 * @return void 无返回值
 * @note 1. 颜色原理：通过组合Windows API的颜色常量实现，支持RGB三原色的基础色和高亮色
 *       2. 默认值为：白色文字（红+绿+蓝）、黑色背景（无颜色）、无高亮
 *       3. 仅支持Windows系统，依赖<windows.h>头文件的SetConsoleTextAttribute函数
 */
void color(bool bgRed_1_=false,bool bgGreen_1_=false,bool bgBlue_1_=false,bool bgLight_1_=false,
           bool fgRed_1_=true,bool fgGreen_1_=true,bool fgBlue_1_=true,bool fgLight_1_=false) {
    int colorValue = 0;
    // 组合前景色（文字颜色）常量
    if (fgRed_1_) colorValue += FOREGROUND_RED;
    if (fgGreen_1_) colorValue += FOREGROUND_GREEN;
    if (fgBlue_1_) colorValue += FOREGROUND_BLUE;
    if (fgLight_1_) colorValue += FOREGROUND_INTENSITY;
    // 组合背景色常量
    if (bgRed_1_) colorValue += BACKGROUND_RED;
    if (bgGreen_1_) colorValue += BACKGROUND_GREEN;
    if (bgBlue_1_) colorValue += BACKGROUND_BLUE;
    if (bgLight_1_) colorValue += BACKGROUND_INTENSITY;
    // 设置控制台文本颜色
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), colorValue);
}

/**
 * @brief 内部工具命名空间：封装所有核心逻辑，对外隐藏实现细节
 * @note 1. 包含Version（版本查询）、Output（格式化输出）两个核心类
 *       2. 对外仅暴露适配接口，避免内部逻辑修改影响外部调用
 *       3. 所有内部成员均为静态，无需实例化即可调用
 */
namespace InternalUtil {
    /**
     * @brief 版本查询类：提供C++标准版本、编译器版本的查询功能
     * @note 1. 所有方法均为静态，直接通过类名调用
     *       2. 仅支持MinGW GCC编译器的版本查询，其他编译器会提示错误
     */
    class Version {
    public:
        /**
         * @brief 查询当前编译器使用的C++标准版本
         * @param hongzhi 是否返回原始宏值，默认false（返回简化版本号）
         * @return string C++标准版本（简化版：如"11"、"20"；原始版：如"201103L"对应的数字）
         * @note 1. 依赖__cplusplus宏，不同编译器的宏值可能略有差异
         *       2. 支持的版本：98/03、11、14、17、20、23，未识别版本返回"未知"
         */
        static string getCppStandard(bool hongzhi=false) {
            if(!hongzhi) {
                if (__cplusplus == 199711L) return "98/03";
                else if (__cplusplus == 201103L) return "11";
                else if (__cplusplus == 201402L) return "14";
                else if (__cplusplus == 201703L) return "17";
                else if (__cplusplus == 202002L) return "20";
                else if (__cplusplus == 202302L) return "23";
                else return "未知";
            } else {
                return to_string(__cplusplus);
            }
        }

        /**
         * @brief 查询当前使用的编译器版本（仅支持MinGW GCC）
         * @return string 编译器版本信息（如"13.1.0"）；非MinGW GCC编译器返回空字符串并提示错误
         * @note 1. 依赖__GNUC__和__MINGW32__宏判断编译器类型
         *       2. 版本信息由__VERSION__宏提供，不同编译器的宏定义不同
         */
        static string getCompilerVersion() {
            #if defined(__GNUC__) && defined(__MINGW32__)
                return __VERSION__;
            #else
                cerr << "[错误] 未使用 MinGW GCC 编译器！";
                return "";
            #endif
        }
    };

    /**
     * @brief 格式化输出类：整合所有输出相关逻辑（say/ysay/sai/ysai/sab/ysab）
     * @note 1. 封装基础输出、多类型逐字输出、bool格式化输出的核心逻辑
     *       2. bool格式化的配置参数为私有静态成员，仅通过接口修改，避免全局变量污染
     *       3. 所有输出方法均支持延迟输出和换行控制，风格统一
     */
    class Output {
    private:
        // ========== bool格式化私有配置（原全局变量，私有化后更安全） ==========
        static bool suoxie;        // 是否输出精简格式（T/F/Y/N），默认false
        static bool shouzimu_daxie;// 首字母是否大写，默认true
        static bool qita_zimu_daxie;// 非首字母是否大写，默认false
        static bool true_tf_false_yn;// true/false用T/F还是Y/N，默认true（T/F）

    public:
        /**
         * @brief 通用基础输出方法（供say/sai/sac调用）
         * @tparam T 输出内容类型（支持string、int、char等可直接输出的类型）
         * @param neirong 输出的内容
         * @param miaoshu 输出后延迟的秒数，默认1秒
         * @param huanhang 输出后是否换行，默认true
         * @return void 无返回值
         * @note 1. 延迟逻辑：通过Sleep函数实现，秒数转换为毫秒（1秒=1000毫秒）
         *       2. 模板函数支持多类型输出，无需为每种类型单独编写方法
         */
        template <typename T>
        static void print(T neirong, double miaoshu=1, bool huanhang=true) {
            cout << neirong;
            Sleep(static_cast<DWORD>(miaoshu * 1000));
            if (huanhang) cout << "\n";
        }

        /**
         * @brief 通用逐字输出核心方法（支持string、int、bool，供ysay/ysai/ysab调用）
         * @tparam T 输入类型（string、int、bool，需支持转换为string进行逐字输出）
         * @param neirong 待逐字输出的内容
         * @param miaoshu 整个字符串输出完成的总延迟秒数，默认1秒
         * @param huanhang 输出完成后是否换行，默认true
         * @return void 无返回值
         * @note 1. 编译期类型判断，统一转换为string后执行逐字输出，避免重复逻辑
         *       2. bool类型复用generateBoolString格式化逻辑，格式受sabset配置影响
         *       3. 总延迟均匀分配到每个字符，空内容直接换行（若需要），无延迟
         */
        template <typename T>
        static void printCharByChar(T neirong, double miaoshu=1, bool huanhang=true) {
            // 统一将输入类型转换为string，便于逐字处理
            string content;
            if constexpr (is_same_v<T, string>) {
                // 直接使用原始字符串
                content = neirong;
            } else if constexpr (is_same_v<T, int>) {
                // 整数转换为字符串（支持正负数）
                content = to_string(neirong);
            } else if constexpr (is_same_v<T, bool>) {
                // bool值复用格式化逻辑，生成对应字符串后再逐字输出
                content = generateBoolString(neirong);
            } else {
                // 其他支持to_string的类型，兜底转换（如long、float等）
                content = to_string(neirong);
            }

            // 逐字输出核心逻辑
            if (content.empty()) {
                if (huanhang) cout << "\n";
                return;
            }
            // 计算每个字符的延迟毫秒数（总延迟均匀分配）
            DWORD sleepTime = static_cast<DWORD>((miaoshu * 1000) / content.length());
            // 逐字输出并添加间隔延迟
            for (char c : content) {
                cout << c;
                Sleep(sleepTime);
            }
            // 输出完成后换行（若需要）
            if (huanhang) cout << "\n";
        }

        /**
         * @brief 设置bool值的格式化输出规则（供sabset调用）
         * @param suoxie_val 是否输出精简格式，默认false
         * @param shouzimu_daxie_val 首字母是否大写，默认true
         * @param qita_zimu_daxie_val 非首字母是否大写，默认false
         * @param true_tf_false_yn_val true/false用T/F还是Y/N，默认true
         * @return void 无返回值
         * @note 1. 配置修改后，后续所有sab、ysab调用均生效，直到再次修改
         *       2. 参数默认值与私有成员的初始值一致，保持配置默认行为不变
         */
        static void setBoolFormat(bool suoxie_val=false, bool shouzimu_daxie_val=true,
                                  bool qita_zimu_daxie_val=false, bool true_tf_false_yn_val=true) {
            suoxie = suoxie_val;
            shouzimu_daxie = shouzimu_daxie_val;
            qita_zimu_daxie = qita_zimu_daxie_val;
            true_tf_false_yn = true_tf_false_yn_val;
        }

        /**
         * @brief 生成bool值的格式化字符串（供printBool、printCharByChar调用）
         * @param neirong 待格式化的bool值（true/false）
         * @return string 格式化后的字符串（如"True"、"f"、"YES"、"n"等）
         * @note 1. 格式化规则由私有静态成员决定，无需外部传参
         *       2. 支持四种组合：精简/完整、首字母大写/小写、非首字母大写/小写、T/F/Y/N
         */
        static string generateBoolString(bool neirong) {
            string a = "";
            if (suoxie) {
                // 精简格式：T/F 或 Y/N
                if (true_tf_false_yn) {
                    a += shouzimu_daxie ? (neirong ? "T" : "F") : (neirong ? "t" : "f");
                } else {
                    a += shouzimu_daxie ? (neirong ? "Y" : "N") : (neirong ? "y" : "n");
                }
            } else {
                // 完整格式：True/False 或 Yes/No
                if (true_tf_false_yn) {
                    if (neirong) {
                        a += shouzimu_daxie ? "T" : "t";
                        a += qita_zimu_daxie ? "RUE" : "rue";
                    } else {
                        a += shouzimu_daxie ? "F" : "f";
                        a += qita_zimu_daxie ? "ALSE" : "alse";
                    }
                } else {
                    if (neirong) {
                        a += shouzimu_daxie ? "Y" : "y";
                        a += qita_zimu_daxie ? "ES" : "es";
                    } else {
                        a += shouzimu_daxie ? "N" : "n";
                        a += qita_zimu_daxie ? "O" : "o";
                    }
                }
            }
            return a;
        }

        /**
         * @brief bool值格式化输出方法（供sab调用）
         * @param neirong 待输出的bool值
         * @param miaoshu 输出后延迟的秒数，默认0秒（无延迟）
         * @param huanhang 输出后是否换行，默认true
         * @return void 无返回值
         * @note 1. 核心逻辑：先调用generateBoolString生成格式化字符串，再调用print输出
         *       2. 延迟默认值为0秒，与其他输出函数区分（say/sai等默认1秒）
         */
        static void printBool(bool neirong, double miaoshu=0, bool huanhang=true) {
            string boolStr = generateBoolString(neirong);
            print(boolStr, miaoshu, huanhang);
        }
    };

    // ========== 初始化Output类的私有静态成员（设置默认值） ==========
    bool Output::suoxie = false;
    bool Output::shouzimu_daxie = true;
    bool Output::qita_zimu_daxie = false;
    bool Output::true_tf_false_yn = true;
}

// ===================== 对外兼容接口（完整：原有接口 + 新增逐字输出接口） =====================
/**
 * @brief 对外接口：查询编译器版本（转发至InternalUtil::Version::getCompilerVersion）
 * @return string 编译器版本信息
 * @note 原ver()函数，接口不变，内部逻辑迁移至工具类
 */
string ver() { return InternalUtil::Version::getCompilerVersion(); }

/**
 * @brief 对外接口：查询C++标准版本（转发至InternalUtil::Version::getCppStandard）
 * @param h 是否返回原始宏值，默认0（false，返回简化版本号）
 * @return string C++标准版本
 * @note 原veb()函数，接口不变，内部逻辑迁移至工具类
 */
string veb(bool h=0) { return InternalUtil::Version::getCppStandard(h); }

/**
 * @brief 对外接口：字符串输出（转发至InternalUtil::Output::print）
 * @param neirong 输出的字符串
 * @param miaoshu 输出后延迟秒数，默认1秒
 * @param huanhang 输出后是否换行，默认true
 * @return void 无返回值
 * @note 原say()函数，接口不变，复用工具类通用输出逻辑
 */
void say(string neirong, double miaoshu=1, bool huanhang=true) {
    InternalUtil::Output::print(neirong, miaoshu, huanhang);
}

/**
 * @brief 对外接口：整数输出（转发至InternalUtil::Output::print）
 * @param neirong 输出的整数
 * @param miaoshu 输出后延迟秒数，默认1秒
 * @param huanhang 输出后是否换行，默认true
 * @return void 无返回值
 * @note 原sai()函数，接口不变，复用工具类通用输出逻辑
 */
void sai(int neirong, double miaoshu=1, bool huanhang=true) {
    InternalUtil::Output::print(neirong, miaoshu, huanhang);
}

/**
 * @brief 对外接口：字符输出（转发至InternalUtil::Output::print）
 * @param neirong 输出的字符
 * @param miaoshu 输出后延迟秒数，默认1秒
 * @param huanhang 输出后是否换行，默认true
 * @return void 无返回值
 * @note 原sac()函数，接口不变，复用工具类通用输出逻辑
 */
void sac(char neirong, double miaoshu=1, bool huanhang=true) {
    InternalUtil::Output::print(neirong, miaoshu, huanhang);
}

/**
 * @brief 对外接口：设置bool输出格式（转发至InternalUtil::Output::setBoolFormat）
 * @param suoxie 是否精简格式，默认false
 * @param shouzimu_daxie 首字母是否大写，默认true
 * @param qita_zimu_daxie 非首字母是否大写，默认false
 * @param true_tf___false_yn true/false用T/F还是Y/N，默认true
 * @return void 无返回值
 * @note 原sabset()函数，接口不变，内部配置迁移至工具类私有成员
 */
void sabset(bool suoxie=false,bool shouzimu_daxie=true,bool qita_zimu_daxie=false,bool true_tf___false_yn=true) {
    InternalUtil::Output::setBoolFormat(suoxie, shouzimu_daxie, qita_zimu_daxie, true_tf___false_yn);
}

/**
 * @brief 对外接口：bool值格式化输出（转发至InternalUtil::Output::printBool）
 * @param neirong 待输出的bool值
 * @param miaoshu 输出后延迟秒数，默认0秒
 * @param huanhang 输出后是否换行，默认true
 * @return void 无返回值
 * @note 原sab()函数，接口不变，复用工具类bool格式化和输出逻辑
 */
void sab(bool neirong, double miaoshu=0, bool huanhang=true) {
    InternalUtil::Output::printBool(neirong, miaoshu, huanhang);
}

/**
 * @brief 对外接口：返回固定字符串"ohhhh"
 * @return string 固定字符串"ohhhh"
 * @note 原please()函数，无修改，保持原有功能
 */
string please(){
    return "ohhhh";
}

/**
 * @brief 对外接口：字符串逐字输出（专门处理string类型，对应ysay命名规则）
 * @param neirong 待输出的字符串
 * @param miaoshu 总延迟秒数，默认1秒
 * @param huanhang 输出完成后是否换行，默认true
 * @return void 无返回值
 * @note 转发至InternalUtil::Output::printCharByChar，均匀分配延迟到每个字符
 */
void ysay(string neirong, double miaoshu=1, bool huanhang=true) {
    InternalUtil::Output::printCharByChar(neirong, miaoshu, huanhang);
}

/**
 * @brief 对外接口：整数逐字输出（专门处理int类型，对应ysai命名规则）
 * @param neirong 待输出的整数
 * @param miaoshu 总延迟秒数，默认1秒
 * @param huanhang 输出完成后是否换行，默认true
 * @return void 无返回值
 * @note 转发至InternalUtil::Output::printCharByChar，先转换为字符串再逐字输出
 */
void ysai(int neirong, double miaoshu=1, bool huanhang=true) {
    InternalUtil::Output::printCharByChar(neirong, miaoshu, huanhang);
}

/**
 * @brief 对外接口：bool值逐字输出（专门处理bool类型，对应ysab命名规则）
 * @param neirong 待输出的bool值
 * @param miaoshu 总延迟秒数，默认1秒
 * @param huanhang 输出完成后是否换行，默认true
 * @return void 无返回值
 * @note 1. 转发至InternalUtil::Output::printCharByChar，先格式化再逐字输出
 *       2. 输出格式受sabset()配置影响，与sab()函数格式保持一致
 */
void ysab(bool neirong, double miaoshu=1, bool huanhang=true) {
    InternalUtil::Output::printCharByChar(neirong, miaoshu, huanhang);
}

// ===================== 数学工具函数（带完整注释） =====================
/**
 * @brief 计算n的阶乘（n!）
 * @param n 非负整数
 * @return long long 阶乘结果；n<0返回-1（错误），n>20返回-1（溢出）
 * @note 1. 阶乘定义：0! = 1，1! = 1，n! = n*(n-1)*...*1
 *       2. long long类型最大支持20!（2432902008176640000），超出则溢出
 */
long long factorial(int n) {
    if (n < 0) {
        cerr << "[错误] 阶乘仅支持非负整数！" << endl;
        return -1;
    }
    if (n > 20) {
        cerr << "[错误] 阶乘n>20时long long溢出！" << endl;
        return -1;
    }
    long long res = 1;
    for (int i = 2; i <= n; i++) res *= i;
    return res;
}

/**
 * @brief 判断一个整数是否为质数（素数）
 * @param num 待判断的整数
 * @return bool 是质数返回true，不是质数返回false；num<2返回false并提示错误
 * @note 1. 质数定义：大于1的自然数，除了1和它本身，无法被其他自然数整除
 *       2. 优化算法：仅遍历到sqrt(num)，且跳过偶数（提升效率）
 */
bool isPrime(int num) {
    if (num < 2) {
        if (num < 0) cerr << "[错误] 质数判断仅支持正整数！" << endl;
        return false;
    }
    if (num == 2) return true; // 2是唯一的偶质数
    if (num % 2 == 0) return false; // 偶数（除2外）都不是质数

    // 遍历奇数，仅需判断到sqrt(num)
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0) return false;
    }
    return true;
}

/**
 * @brief 计算两个整数的最大公约数（GCD，欧几里得算法）
 * @param a 第一个整数
 * @param b 第二个整数
 * @return int 最大公约数；a和b均为0返回-1（错误）
 * @note 1. 最大公约数定义：能同时整除a和b的最大正整数
 *       2. 算法核心：gcd(a, b) = gcd(b, a % b)，直到b=0时，a即为结果
 *       3. 支持负数输入，内部自动转换为绝对值计算
 */
int gcd(int a, int b) {
    a = abs(a);
    b = abs(b);

    if (a == 0 && b == 0) {
        cerr << "[错误] 0和0无最大公约数！" << endl;
        return -1;
    }
    return b == 0 ? a : gcd(b, a % b);
}

/**
 * @brief 计算两个整数的最小公倍数（LCM）
 * @param a 第一个整数
 * @param b 第二个整数
 * @return int 最小公倍数；a或b为0（或最大公约数计算失败）返回-1
 * @note 1. 最小公倍数定义：能被a和b同时整除的最小正整数
 *       2. 计算公式：lcm(a, b) = |a*b| / gcd(a, b)
 *       3. 先通过gcd函数获取最大公约数，再计算最小公倍数
 */
int lcm(int a, int b) {
    int g = gcd(a, b);
    if (g == -1 || a == 0 || b == 0) {
        cerr << "[错误] 最小公倍数不支持0（或双0）！" << endl;
        return -1;
    }
    return (abs(a) / g) * abs(b); // 先除后乘，避免溢出
}

/**
 * @brief 计算斐波那契数列的第n项（1, 1, 2, 3, 5, 8...）
 * @param n 项数（正整数）
 * @return long long 第n项的值；n<1返回-1（错误），溢出返回-1
 * @note 1. 斐波那契数列定义：F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)（n≥3）
 *       2. 采用迭代算法（避免递归的栈溢出和重复计算）
 *       3. 若计算过程中结果为负，视为溢出（long long类型上限不足）
 */
long long fibonacci(int n) {
    if (n < 1) {
        cerr << "[错误] 斐波那契数列仅支持正整数项！" << endl;
        return -1;
    }
    if (n == 1 || n == 2) return 1;

    long long a = 1, b = 1, res;
    for (int i = 3; i <= n; i++) {
        res = a + b;
        if (res < 0) { // 溢出判断（long long溢出后会变为负数）
            cerr << "[错误] 斐波那契第" << n << "项溢出！" << endl;
            return -1;
        }
        a = b;
        b = res;
    }
    return res;
}

/**
 * @brief 计算1到n的累加和（1+2+3+...+n）
 * @param n 正整数
 * @return int 累加和；n<1返回0
 * @note 采用等差数列求和公式：sum = n*(n+1)/2（效率高于循环累加）
 */
int sum1ToN(int n) {
    if (n < 1) return 0;
    return n * (n + 1) / 2;
}

/**
 * @brief 计算1到n的平方和（12+22+32+...+n2）
 * @param n 正整数
 * @return long long 平方和；n<1返回0
 * @note 采用平方和公式：sum = n(n+1)(2n+1)/6（避免循环累加溢出，提升效率）
 */
long long squareSum(int n) {
    if (n < 1) return 0;
    // 拆分计算，先除后乘，减少溢出风险
    return (static_cast<long long>(n) / 6) * (n + 1) * (2 * n + 1) 
           + (static_cast<long long>(n) % 6) * (n + 1) * (2 * n + 1) / 6;
}

/**
 * @brief 判断一个整数是否为偶数
 * @param num 待判断的整数
 * @return bool 是偶数返回true，不是偶数返回false
 * @note 偶数定义：能被2整除的整数（包括0和负数）
 */
bool isEven(int num) {
    return num % 2 == 0;
}

/**
 * @brief 判断一个整数是否为奇数
 * @param num 待判断的整数
 * @return bool 是奇数返回true，不是奇数返回false
 * @note 奇数定义：不能被2整除的整数（包括负数，不包括0）
 */
bool isOdd(int num) {
    return num % 2 != 0;
}

/**
 * @brief 计算一个整数的绝对值
 * @param num 待计算的整数
 * @return int 整数的绝对值
 * @note 封装标准库abs函数，提升代码可读性（仅支持int类型）
 */
int absNum(int num) {
    return num < 0 ? -num : num;
}

/**
 * @brief 计算一个双精度浮点数的绝对值
 * @param num 待计算的双精度浮点数
 * @return double 浮点数的绝对值
 * @note 封装标准库fabs函数，提升代码可读性（支持double类型）
 */
double absDouble(double num) {
    return num < 0 ? -num : num;
}

/**
 * @brief 计算a的b次幂（a^b，仅支持非负整数次幂）
 * @param a 底数（整数）
 * @param b 指数（非负整数）
 * @return long long 幂运算结果；b<0返回-1，a=0且b=0返回-1（无意义）
 * @note 1. 定义：a^0=1（a≠0），a^1=a，a^b=a*a*...*a（b个a相乘）
 *       2. 采用循环累乘实现，支持负数底数（结果符号由b决定）
 */
long long power(int a, int b) {
    if (b < 0) {
        cerr << "[错误] 幂次仅支持非负整数！" << endl;
        return -1;
    }
    if (a == 0 && b == 0) {
        cerr << "[错误] 0^0无数学意义！" << endl;
        return -1;
    }
    if (b == 0) return 1;

    long long res = 1;
    for (int i = 1; i <= b; i++) res *= a;
    return res;
}

/**
 * @brief 反转一个整数的各位数字（例如：123→321，-456→-654）
 * @param num 待反转的整数
 * @return int 反转后的整数；溢出返回0并提示错误
 * @note 1. 支持负数反转，负号保留在最前面
 *       2. 溢出判断：反转结果超出int类型范围（[-2^31, 2^31-1]）返回0
 */
int reverseNum(int num) {
    bool isNegative = num < 0;
    long long numLL = llabs(static_cast<long long>(num)); // 转换为long long避免中间溢出
    long long res = 0;

    while (numLL != 0) {
        res = res * 10 + numLL % 10;
        numLL /= 10;
    }

    // 溢出判断（int类型范围：-2147483648 ~ 2147483647）
    if (res > INT_MAX || res < INT_MIN) {
        cerr << "[错误] 逆序后整数溢出！" << endl;
        return 0;
    }

    return isNegative ? -static_cast<int>(res) : static_cast<int>(res);
}

/**
 * @brief 统计一个整数的位数（不包括负号）
 * @param num 待统计的整数
 * @return int 整数的位数；0返回1位
 * @note 1. 正数、负数、0均支持，例如：123→3位，-456→3位，0→1位
 *       2. 内部转换为绝对值计算，忽略负号
 */
int countDigits(int num) {
    if (num == 0) return 1;
    int cnt = 0;
    num = abs(num);

    while (num != 0) {
        cnt++;
        num /= 10;
    }
    return cnt;
}

/**
 * @brief 计算一个整数数组的平均值
 * @param arr 整数数组指针
 * @param len 数组长度
 * @return double 数组的平均值；数组无效（空或长度≤0）返回NAN并提示错误
 * @note 1. 支持任意长度的有效数组，返回双精度浮点数保证精度
 *       2. 数组无效判断：arr为nullptr 或 len≤0
 */
double avgArray(int arr[], int len) {
    if (len <= 0 || arr == nullptr) {
        cerr << "[错误] 数组长度不能为0或指针为空！" << endl;
        return NAN;
    }

    long long sum = 0;
    for (int i = 0; i < len; i++) sum += arr[i];

    return static_cast<double>(sum) / len;
}

/**
 * @brief 判断一个整数是否为完全平方数（某个整数的平方）
 * @param num 待判断的整数
 * @return bool 是完全平方数返回true，不是返回false；num<0返回false
 * @note 1. 完全平方数定义：存在整数k，使得k2=num
 *       2. 优化算法：先计算sqrt(num)取整，再验证其平方是否等于num（避免浮点误差）
 */
bool isPerfectSquare(int num) {
    if (num < 0) return false;

    long long numLL = num;
    long long sqrtNum = static_cast<long long>(sqrt(numLL) + 1e-9); // 加微小值避免浮点误差

    return sqrtNum * sqrtNum == numLL;
}

/**
 * @brief 查找一个整数数组中的最大值
 * @param arr 整数数组指针
 * @param len 数组长度
 * @return int 数组的最大值；数组无效返回INT_MIN并提示错误
 * @note 1. 支持任意长度的有效数组，遍历数组找到最大值
 *       2. 数组无效判断：arr为nullptr 或 len≤0
 */
int maxArray(int arr[], int len) {
    if (len <= 0 || arr == nullptr) {
        cerr << "[错误] 数组长度不能为0或指针为空！" << endl;
        return INT_MIN;
    }

    int maxVal = arr[0];
    for (int i = 1; i < len; i++) {
        if (arr[i] > maxVal) maxVal = arr[i];
    }
    return maxVal;
}

/**
 * @brief 查找一个整数数组中的最小值
 * @param arr 整数数组指针
 * @param len 数组长度
 * @return int 数组的最小值；数组无效返回INT_MAX并提示错误
 * @note 1. 支持任意长度的有效数组，遍历数组找到最小值
 *       2. 数组无效判断：arr为nullptr 或 len≤0
 */
int minArray(int arr[], int len) {
    if (len <= 0 || arr == nullptr) {
        cerr << "[错误] 数组长度不能为0或指针为空！" << endl;
        return INT_MAX;
    }

    int minVal = arr[0];
    for (int i = 1; i < len; i++) {
        if (arr[i] < minVal) minVal = arr[i];
    }
    return minVal;
}

/**
 * @brief 计算一个任意类型数组的元素和（模板函数）
 * @tparam T 数组元素类型（支持int、long long、double等数值类型）
 * @tparam N 数组长度（编译期确定）
 * @param arr 待求和的数组（引用传递）
 * @return T 数组元素的和；空数组（N=0）返回T类型的默认值并提示错误
 * @note 1. 模板函数支持多种数值类型，无需重复编写不同类型的求和逻辑
 *       2. 数组长度N由编译器自动推导，仅支持静态数组（栈上数组）
 */
template <typename T, size_t N>
T sumArray(const T (&arr)[N]) {
    if (N == 0) {
        cerr << "[错误] 数组长度不能为0！" << endl;
        return T();
    }

    T sum = T();
    for (size_t i = 0; i < N; ++i) {
        sum += arr[i];
    }
    return sum;
}

/**
 * @brief 计算三角形的面积（海伦公式）
 * @param a 三角形第一条边长
 * @param b 三角形第二条边长
 * @param c 三角形第三条边长
 * @return long double 三角形的面积；无效三角形返回NAN并提示错误
 * @note 1. 海伦公式：面积=√[p(p-a)(p-b)(p-c)]，其中p=(a+b+c)/2
 *       2. 有效三角形判断：任意两边之和大于第三边，且边长均大于0
 *       3. 使用long double类型保证计算精度
 */
long double triangleArea(long double a, long double b, long double c) {
    // 边长有效性校验
    if (a <= 0 || b <= 0 || c <= 0) {
        cerr << "[错误] 三角形边长必须大于0！" << endl;
        return NAN;
    }
    // 三角形存在性校验（任意两边之和大于第三边）
    if (a + b <= c || a + c <= b || b + c <= a) {
        cerr << "[错误] 输入不是合法的三角形三边！" << endl;
        return NAN;
    }

    long double p = (a + b + c) / 2; // 半周长
    return sqrtl(p * (p - a) * (p - b) * (p - c));
}

/**
 * @brief 判断一个年份是否为闰年
 * @param year 待判断的年份（正整数）
 * @return bool 是闰年返回true，不是闰年返回false；year<1返回false并提示错误
 * @note 闰年判断规则（公历）：
 *       1. 能被4整除但不能被100整除；
 *       2. 能被400整除；
 *       满足以上任一条件即为闰年
 */
bool isLeapYear(int year) {
    if (year < 1) {
        cerr << "[错误] 闰年判断仅支持公元1年及以后！" << endl;
        return false;
    }

    // 闰年判断逻辑
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

/**
 * @brief 计算a到b之间所有整数的累加和（包括a和b，支持a>b）
 * @param a 起始整数
 * @param b 结束整数
 * @return long long 累加和
 * @note 1. 支持a>b、a<b、a=b三种情况，自动调整起始和结束顺序
 *       2. 采用等差数列求和公式，效率高于循环累加，避免溢出
 */
long long sumAB(int a, int b) {
    if (a > b) swap(a, b);

    long long llA = a;
    long long llB = b;
    // 等差数列求和：项数*(首项+末项)/2
    return (llA + llB) * (llB - llA + 1) / 2;
}

/**
 * @brief 大整数类（支持超大整数的加法和乘法，避免普通类型溢出）
 * @note 1. 内部采用vector<int>存储每一位数字（低位在前，高位在后）
 *       2. 支持无符号大整数运算，暂不支持负数
 *       3. 提供toString()方法，将大整数转换为字符串输出
 */
class BigInteger {
private:
    vector<int> digits; // 存储大整数的每一位（低位在前，例如：123存储为[3,2,1]）

public:
    /**
     * @brief 无参构造函数，初始化空大整数（值为0）
     */
    BigInteger() {}

    /**
     * @brief 有参构造函数，将普通整数转换为大整数
     * @param n 普通非负整数
     */
    BigInteger(int n) {
        if (n == 0) {
            digits.push_back(0);
            return;
        }

        while (n > 0) {
            digits.push_back(n % 10);
            n /= 10;
        }
    }

    /**
     * @brief 重载+=运算符，实现大整数的加法运算（当前对象 += 另一个大整数）
     * @param other 另一个大整数
     * @return BigInteger& 当前对象的引用（支持链式调用）
     */
    BigInteger& operator+=(const BigInteger& other) {
        int carry = 0; // 进位标志
        int maxLen = max(digits.size(), other.digits.size());

        // 扩展当前对象的位数，与另一个对象对齐
        digits.resize(maxLen, 0);

        // 逐位相加
        for (int i = 0; i < maxLen; i++) {
            int otherDigit = (i < other.digits.size()) ? other.digits[i] : 0;
            int sum = digits[i] + otherDigit + carry;
            digits[i] = sum % 10;
            carry = sum / 10;
        }

        // 处理最后的进位
        if (carry > 0) {
            digits.push_back(carry);
        }

        return *this;
    }

    /**
     * @brief 重载*=运算符，实现大整数与普通整数的乘法运算
     * @param multiplier 普通非负整数
     * @return BigInteger& 当前对象的引用（支持链式调用）
     */
    BigInteger& operator*=(int multiplier) {
        int carry = 0; // 进位标志

        // 逐位相乘
        for (int i = 0; i < digits.size(); i++) {
            long long product = static_cast<long long>(digits[i]) * multiplier + carry;
            digits[i] = product % 10;
            carry = product / 10;
        }

        // 处理剩余的进位
        while (carry > 0) {
            digits.push_back(carry % 10);
            carry /= 10;
        }

        return *this;
    }

    /**
     * @brief 将大整数转换为字符串（高位在前，符合常规阅读习惯）
     * @return string 大整数对应的字符串
     */
    string toString() const {
        string result;
        for (int i = digits.size() - 1; i >= 0; i--) {
            result.push_back(digits[i] + '0');
        }
        return result;
    }
};

/**
 * @brief 计算1到n的阶乘和（1!+2!+3!+...+n!），使用大整数避免溢出
 * @param n 正整数
 * @return long long 阶乘和（普通类型，n≤20）；n>20返回大整数对应的字符串（通过重载可扩展）
 * @note 1. n≤20时，返回long long类型结果；n>20时，使用BigInteger类计算，避免溢出
 *       2. 此处为兼容原有接口，n>20时返回-1，实际可扩展为返回string类型
 */
long long factorialSum(int n) {
    if (n < 1) return 0;
    if (n > 20) {
        cerr << "[错误] 阶乘和n>20时long long溢出！建议使用BigInteger类！" << endl;
        return -1;
    }

    long long sum = 0;
    long long fact = 1;
    for (int i = 1; i <= n; i++) {
        fact *= i;
        sum += fact;
        if (sum < 0) { // 溢出判断
            cerr << "[错误] 阶乘和第" << n << "项溢出！" << endl;
            return -1;
        }
    }
    return sum;
}

/**
 * @brief 计算1到n的阶乘和（使用BigInteger类，支持超大n，无溢出）
 * @param n 正整数
 * @return string 阶乘和对应的字符串
 * @note 支持任意正整数n，无溢出风险，返回结果为字符串格式
 */
string factorialSumBigInt(int n) {
    if (n < 1) return "0";

    BigInteger factorial(1);
    BigInteger sum(1);

    for (int i = 2; i <= n; i++) {
        factorial *= i;
        sum += factorial;
    }

    return sum.toString();
}

/**
 * @brief 判断一个整数是否为回文数（正读和反读都相同）
 * @param num 待判断的整数
 * @return bool 是回文数返回true，不是回文数返回false
 * @note 1. 支持负数判断（负数因负号存在，均不是回文数）
 *       2. 例如：121→true，-121→false，123→false，0→true
 */
bool isPalindrome(int num) {
    long long numLL = num;
    if (numLL < 0) return false; // 负数不是回文数

    long long original = numLL;
    long long reversed = 0;

    // 反转整数
    while (numLL != 0) {
        reversed = reversed * 10 + numLL % 10;
        numLL /= 10;
    }

    // 比较原数和反转后的数是否相等
    return original == reversed;
}

/**
 * @brief 打印任意类型数组的所有元素（模板函数，支持格式化输出）
 * @tparam T 数组元素类型（支持int、bool、string、char等）
 * @tparam N 数组长度（编译期确定）
 * @param arr 待打印的数组（引用传递）
 * @note 1. 模板函数支持多种元素类型，自动适配不同类型的输出格式
 *       2. bool类型元素调用sab()函数输出，其他类型直接输出
 *       3. 仅支持静态数组（栈上数组），数组长度N由编译器自动推导
 */
template <typename T, size_t N>
void printlist(const T (&arr)[N]) {
    if (N == 0) {
        cerr << "[错误] 数组长度不能为0！" << endl;
        return;
    }

    cout << "数组元素：";
    for (size_t i = 0; i < N; ++i) {
        // 针对bool类型，调用sab()输出格式化结果
        if constexpr (is_same_v<T, bool>) {
            sab(arr[i], 0, 0);
        } else if constexpr (is_same_v<T, string>) {
            cout << "\"" << arr[i] << "\"";
        } else if constexpr (is_same_v<T, char>) {
            cout << "'" << arr[i] << "'";
        } else {
            cout << arr[i];
        }

        // 输出分隔符（最后一个元素后不输出）
        if (i != N - 1) {
            cout << ", ";
        }
    }
    cout << endl;
}