#pragma once
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <cstddef>
#include <stdint.h>  // 提供 SIZE_MAX，C++98 环境必备
#define fast 0
#define normal 50
#define science SIZE_MAX
using namespace std;

// 比较无符号大整数：1=a>b  0=相等  -1=a<b
int cmp_num(const string &a, const string &b) {
    if (a.size() != b.size())
        return a.size() > b.size() ? 1 : -1;
    for (int i = 0; i < (int)a.size(); ++i) {
        if (a[i] != b[i])
            return a[i] > b[i] ? 1 : -1;
    }
    return 0;
}

// 去除前导零
string strip_leading_zeros(const string &s) {
    size_t i = 0;
    while (i < s.size() && s[i] == '0') i++;
    if (i == s.size()) return "0";
    return s.substr(i);
}

// 去除小数末尾零
string strip_trailing_zeros(const string &s) {
    int i = (int)s.size() - 1;
    while (i >= 0 && s[i] == '0') i--;
    if (i < 0) return "";
    return s.substr(0, i + 1);
}

// 无符号大整数加法
string add_num(const string &a, const string &b) {
    string res;
    int i = (int)a.size() - 1, j = (int)b.size() - 1;
    int carry = 0;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        carry = sum / 10;
        res += (char)(sum % 10 + '0');
    }
    reverse(res.begin(), res.end());
    return strip_leading_zeros(res);
}

// 无符号大整数减法（仅支持 a >= b）
string sub_num(const string &a, const string &b) {
    string res;
    int i = (int)a.size() - 1, j = (int)b.size() - 1;
    int borrow = 0;
    while (i >= 0) {
        int da = (a[i--] - '0') - borrow;
        int db = (j >= 0) ? (b[j--] - '0') : 0;
        borrow = 0;
        if (da < db) {
            da += 10;
            borrow = 1;
        }
        res += (char)(da - db + '0');
    }
    reverse(res.begin(), res.end());
    return strip_leading_zeros(res);
}

// 无符号大整数乘法
string mul_num(const string &a, const string &b) {
    int n = a.size(), m = b.size();
    vector<int> res(n + m, 0);
    for (int i = n - 1; i >= 0; --i) {
        int da = a[i] - '0';
        for (int j = m - 1; j >= 0; --j) {
            int db = b[j] - '0';
            res[i + j + 1] += da * db;
            res[i + j] += res[i + j + 1] / 10;
            res[i + j + 1] %= 10;
        }
    }
    string s;
    for (int i = 0; i < n + m; ++i) s += (char)(res[i] + '0');
    return strip_leading_zeros(s);
}

// 连减实现大整数除法，prec为保留小数位数
// 【C++98修复】移除范围for，改用下标遍历
string div_num(const string &a, const string &b, int prec) {
    string quotient;
    string rem;
    // 计算整数商
    for (int i = 0; i < (int)a.size(); ++i) {
        char ch = a[i];
        rem += ch;
        rem = strip_leading_zeros(rem);
        int cnt = 0;
        while (cmp_num(rem, b) >= 0) {
            rem = sub_num(rem, b);
            cnt++;
        }
        quotient += (char)(cnt + '0');
    }
    quotient = strip_leading_zeros(quotient);
    if (prec <= 0) return quotient;
    // 补0减小单位，计算小数位
    quotient += '.';
    for (int i = 0; i < prec; ++i) {
        rem += '0';
        int cnt = 0;
        while (cmp_num(rem, b) >= 0) {
            rem = sub_num(rem, b);
            cnt++;
        }
        quotient += (char)(cnt + '0');
        if (rem == "0") {
            while (++i < prec) quotient += '0';
            break;
        }
    }
    return quotient;
}

bool cmp(double x){
    int y = (int)x;
    // 注意：1/2 是整数除法结果为0，此处必须写 1.0 才是浮点运算
    double a = 1.0 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2
    /2/2/2/2/2/2/2/2/2/2/2/2/2/2/2/2/2/2/2/2/2/2
    /2/2/2/2/2/2/2/2/2/2/2/2/2/2/2;
    double i = ((double)y) - x;
    if(i < 0) i = -i;
    return i < a;
}

string tostr(int x){
    string a;
    do{
        int b = x % 10;
        a = char('0' + b) + a;
    } while (x /= 10);
    return a;
}



class lldouble{
    string a;
    string b;
    bool sign;
    bool is_int;
    int div_mode;  // 【C++98修复】去掉类内默认初始化，移到构造函数里
public:
    ~lldouble() {}

    // 默认构造
    lldouble(){
        a = "0";
        b = "";
        sign = false;
        is_int = true;
        div_mode = normal;  // 初始化除法精度模式
    }

    // string 构造
    lldouble(const string& x) {
        div_mode = normal;
        if(x == ""){
            a = "0";
            b = "";
            sign = false;
            is_int = true;
            return;
        }
        sign = false;
        a = "0";
        b.clear();
        is_int = true;

        size_t start_idx = 0;
        if (!x.empty() && x[0] == '-') {
            sign = true;
            start_idx = 1;
        }

        size_t dot_pos = x.find('.', start_idx);
        if (dot_pos == string::npos) {
            a = x.substr(start_idx);
            b.clear();
            is_int = true;
        } else {
            a = x.substr(start_idx, dot_pos - start_idx);
            b = x.substr(dot_pos + 1);
            is_int = false;

            while (!b.empty() && b[b.size() - 1] == '0') {
                b.erase(b.end() - 1);
            }
            if (b.empty()) {
                is_int = true;
            }
        }
    }

    void setspeed(int x){
        div_mode = x;
    }

    // int 构造
    lldouble(int x){
        div_mode = normal;
        sign = (x < 0);
        if (sign) x = -x;
        is_int = true;
        a = tostr(x);
        b = "";
    }

    // 拷贝构造
    lldouble (const lldouble& x){
        a = x.a;
        b = x.b;
        sign = x.sign;
        is_int = x.is_int;
        div_mode = x.div_mode;
    }

    // double 构造
    lldouble(double x){
        div_mode = normal;
        sign = (x < 0);
        if (sign) x = -x;

        long long inter = (long long)x;
        a = tostr((int)inter);
        x -= inter;

        b.clear();
        is_int = true;

        for (int i = 0; i < 15; ++i) {
            x *= 10;
            int digit = (int)x;
            b += (char)('0' + digit);
            x -= digit;
            if (x < 1e-15) break;
        }

        while (!b.empty() && b[b.size() - 1] == '0') {
            b.erase(b.end() - 1);
        }
        is_int = b.empty();
    }

    // double 赋值
    void operator =(double x) {
        sign = (x < 0);
        if (sign) x = -x;

        long long inter = (long long)x;
        a = tostr((int)inter);
        x -= inter;

        b.clear();
        is_int = true;

        for (int i = 0; i < 15; ++i) {
            x *= 10;
            int digit = (int)x;
            b += (char)('0' + digit);
            x -= digit;
            if (x < 1e-15) break;
        }

        while (!b.empty() && b[b.size() - 1] == '0') {
            b.erase(b.end() - 1);
        }
        is_int = b.empty();
    }

    // int 赋值
    void operator =(int x){
        sign = (x < 0);
        if (sign) x = -x;
        is_int = true;
        a = tostr(x);
        b = "";
    }

    // string 赋值
    void operator =(const string& x) {
        if(x == ""){
            a = "0";
            b = "";
            sign = false;
            is_int = true;
            return;
        }
        sign = false;
        a = "0";
        b.clear();
        is_int = true;

        size_t start_idx = 0;
        if (!x.empty() && x[0] == '-') {
            sign = true;
            start_idx = 1;
        }

        size_t dot_pos = x.find('.', start_idx);
        if (dot_pos == string::npos) {
            a = x.substr(start_idx);
            b.clear();
            is_int = true;
        } else {
            a = x.substr(start_idx, dot_pos - start_idx);
            b = x.substr(dot_pos + 1);
            is_int = false;

            while (!b.empty() && b[b.size() - 1] == '0') {
                b.erase(b.end() - 1);
            }
            if (b.empty()) {
                is_int = true;
            }
        }
    }

    // 拷贝赋值
    void operator =(const lldouble& x){
        a = x.a;
        b = x.b;
        sign = x.sign;
        is_int = x.is_int;
        div_mode = x.div_mode;
    }

    // 输入
    void in(){
        string x;
        cin >> x;
        *this = x;
    }

   // 输出
    void out(lldouble fix = "1000000000", int n = 5){
        if(fix == "1000000000"){
            if(sign && a != "0") putchar('-');
            cout << a;
            if(!is_int && !b.empty()){
                cout << '.' << b;
            }
            return;
        }

        while(b.size() < fix) {
            b += '0';
        }

        int carry = 0;
        if(b.size() > fix){
            carry = (b[fix] - '0') >= n ? 1 : 0;
            b = b.substr(0, fix);
        }

        for(int i = (int)b.size() - 1; i >= 0 && carry; --i){
            int cur_digit = (b[i] - '0') + carry;
            b[i] = (cur_digit % 10) + '0';
            carry = cur_digit / 10;
        }

        if(carry){
            for(int i = (int)a.size() - 1; i >= 0 && carry; --i){
                int cur_digit = (a[i] - '0') + carry;
                a[i] = (cur_digit % 10) + '0';
                carry = cur_digit / 10;
            }
            if(carry){
                a = string("1") + a;
            }
        }

        if(sign) putchar('-');
        cout << a;
        if(fix > 0){
            cout << '.' << b;
        }
    }

    // 加法
    lldouble operator + (const lldouble& x) const {
        lldouble res;
        int dec1 = b.size();
        int dec2 = x.b.size();
        int max_dec = max(dec1, dec2);

        string num1 = a + b + string(max_dec - dec1, '0');
        string num2 = x.a + x.b + string(max_dec - dec2, '0');

        bool same_sign = (sign == x.sign);
        string res_num;
        bool res_sign;

        if (same_sign) {
            res_num = add_num(num1, num2);
            res_sign = sign;
        } else {
            int c = cmp_num(num1, num2);
            if (c >= 0) {
                res_num = sub_num(num1, num2);
                res_sign = sign;
            } else {
                res_num = sub_num(num2, num1);
                res_sign = x.sign;
            }
        }

        int total_len = res_num.size();
        if (total_len > max_dec) {
            res.a = res_num.substr(0, total_len - max_dec);
            res.b = res_num.substr(total_len - max_dec);
        } else {
            res.a = "0";
            res.b = string(max_dec - total_len, '0') + res_num;
        }

        res.b = strip_trailing_zeros(res.b);
        res.is_int = res.b.empty();
        res.sign = res_sign;
        if (res.a == "0" && res.is_int) res.sign = false;
        return res;
    }

    // 减法
    lldouble operator - (const lldouble& x) const {
        lldouble neg_x = x;
        neg_x.sign = !neg_x.sign;
        return *this + neg_x;
    }

    // 乘法
    lldouble operator * (const lldouble& x) const {
        lldouble res;
        res.sign = (sign != x.sign);

        string num1 = a + b;
        string num2 = x.a + x.b;
        int total_dec = b.size() + x.b.size();

        string product = mul_num(num1, num2);

        int len = product.size();
        if (len > total_dec) {
            res.a = product.substr(0, len - total_dec);
            res.b = product.substr(len - total_dec);
        } else {
            res.a = "0";
            res.b = string(total_dec - len, '0') + product;
        }

        res.b = strip_trailing_zeros(res.b);
        res.is_int = res.b.empty();
        if (res.a == "0" && res.is_int) res.sign = false;
        return res;
    }

    // 除法
    lldouble operator / (const lldouble& x) const {
        lldouble res;
        res.sign = (sign != x.sign);

        string num1 = a + b;
        string num2 = x.a + x.b;
        int dec1 = b.size();
        int dec2 = x.b.size();
        const int prec = div_mode;  // 修复变量名笔误

        string dividend = num1 + string(dec2 + prec, '0');
        string quotient = div_num(dividend, num2, 0);

        int total_dec = dec1 + prec;
        int len = quotient.size();
        if (len > total_dec) {
            res.a = quotient.substr(0, len - total_dec);
            res.b = quotient.substr(len - total_dec);
        } else {
            res.a = "0";
            res.b = string(total_dec - len, '0') + quotient;
        }

        res.b = strip_trailing_zeros(res.b);
        res.is_int = res.b.empty();
        if (res.a == "0" && res.is_int) res.sign = false;
        return res;
    }
    
        // +=
    lldouble& operator += (const lldouble& x) {
        *this = *this + x;
        return *this;
    }
    // -=
    lldouble& operator -= (const lldouble& x) {
        *this = *this - x;
        return *this;
    }
    // *=
    lldouble& operator *= (const lldouble& x) {
        *this = *this * x;
        return *this;
    }
    // /=
    lldouble& operator /= (const lldouble& x) {
        *this = *this / x;
        return *this;
    }
    
    
    // 外部只读接口
    int asize() const { return (int)a.size(); }
    int bsize() const { return (int)b.size(); }
    string geta() const { return a; }
    string getb() const { return b; }
    bool getsign() const { return sign; }
    bool get_is_int() const { return is_int; }
    int get_div_mode() const { return div_mode; }
	
	
};
// ========== int  op lldouble ==========
inline lldouble operator+(int lhs, const lldouble& rhs) { return lldouble(lhs) + rhs; }
inline lldouble operator-(int lhs, const lldouble& rhs) { return lldouble(lhs) - rhs; }
inline lldouble operator*(int lhs, const lldouble& rhs) { return lldouble(lhs) * rhs; }
inline lldouble operator/(int lhs, const lldouble& rhs) { return lldouble(lhs) / rhs; }

// ========== double op lldouble ==========
inline lldouble operator+(double lhs, const lldouble& rhs) { return lldouble(lhs) + rhs; }
inline lldouble operator-(double lhs, const lldouble& rhs) { return lldouble(lhs) - rhs; }
inline lldouble operator*(double lhs, const lldouble& rhs) { return lldouble(lhs) * rhs; }
inline lldouble operator/(double lhs, const lldouble& rhs) { return lldouble(lhs) / rhs; }

// ========== string op lldouble ==========
inline lldouble operator+(const string& lhs, const lldouble& rhs) { return lldouble(lhs) + rhs; }
inline lldouble operator-(const string& lhs, const lldouble& rhs) { return lldouble(lhs) - rhs; }
inline lldouble operator*(const string& lhs, const lldouble& rhs) { return lldouble(lhs) * rhs; }
inline lldouble operator/(const string& lhs, const lldouble& rhs) { return lldouble(lhs) / rhs; }

// int += lldouble
inline lldouble& operator += (lldouble& lhs, int rhs) {
    lhs = lhs + lldouble(rhs);
    return lhs;
}
inline lldouble& operator -= (lldouble& lhs, int rhs) {
    lhs = lhs - lldouble(rhs);
    return lhs;
}
inline lldouble& operator *= (lldouble& lhs, int rhs) {
    lhs = lhs * lldouble(rhs);
    return lhs;
}
inline lldouble& operator /= (lldouble& lhs, int rhs) {
    lhs = lhs / lldouble(rhs);
    return lhs;
}

// double += lldouble
inline lldouble& operator += (lldouble& lhs, double rhs) {
    lhs = lhs + lldouble(rhs);
    return lhs;
}
inline lldouble& operator -= (lldouble& lhs, double rhs) {
    lhs = lhs - lldouble(rhs);
    return lhs;
}
inline lldouble& operator *= (lldouble& lhs, double rhs) {
    lhs = lhs * lldouble(rhs);
    return lhs;
}
inline lldouble& operator /= (lldouble& lhs, double rhs) {
    lhs = lhs / lldouble(rhs);
    return lhs;
}

// string += lldouble
inline lldouble& operator += (lldouble& lhs, const string& rhs) {
    lhs = lhs + lldouble(rhs);
    return lhs;
}
inline lldouble& operator -= (lldouble& lhs, const string& rhs) {
    lhs = lhs - lldouble(rhs);
    return lhs;
}
inline lldouble& operator *= (lldouble& lhs, const string& rhs) {
    lhs = lhs * lldouble(rhs);
    return lhs;
}
inline lldouble& operator /= (lldouble& lhs, const string& rhs) {
    lhs = lhs / lldouble(rhs);
    return lhs;
}


/*
	string a;
    string b;
    bool sign;
    bool is_int;
    int div_mode;
*/
// 相等判断
bool operator==(const lldouble& x, const lldouble& y)
{
    return (x.getsign() == y.getsign())
        && (x.geta() == y.geta())
        && (x.getb() == y.getb());
}

bool operator!=(const lldouble& x, const lldouble& y)
{
    return !(x == y);
}

// 大于
bool operator>(const lldouble& x, const lldouble& y)
{
    bool sx = x.getsign();
    bool sy = y.getsign();
    // 正负不同：负数 < 正数
    if (sx != sy)
        return sy;
    // 同为负数：绝对值大的更小
    if (sx)
    {
        int c = cmp_num(x.geta(), y.geta());
        if (c != 0) return c < 0;
        return cmp_num(x.getb(), y.getb()) < 0;
    }
    // 同为正数：绝对值大的更大
    int c = cmp_num(x.geta(), y.geta());
    if (c != 0) return c > 0;
    return cmp_num(x.getb(), y.getb()) > 0;
}

// 小于
bool operator<(const lldouble& x, const lldouble& y)
{
    return y > x;
}

bool operator>=(const lldouble& x, const lldouble& y)
{
    return (x > y) || (x == y);
}

bool operator<=(const lldouble& x, const lldouble& y)
{
    return (x < y) || (x == y);
}


// int == lldouble
inline bool operator==(int lhs, const lldouble& rhs)
{
    return lldouble(lhs) == rhs;
}
inline bool operator!=(int lhs, const lldouble& rhs)
{
    return lldouble(lhs) != rhs;
}
inline bool operator>(int lhs, const lldouble& rhs)
{
    return lldouble(lhs) > rhs;
}
inline bool operator<(int lhs, const lldouble& rhs)
{
    return lldouble(lhs) < rhs;
}
inline bool operator>=(int lhs, const lldouble& rhs)
{
    return lldouble(lhs) >= rhs;
}
inline bool operator<=(int lhs, const lldouble& rhs)
{
    return lldouble(lhs) <= rhs;
}

// lldouble == int
inline bool operator==(const lldouble& lhs, int rhs)
{
    return lhs == lldouble(rhs);
}
inline bool operator!=(const lldouble& lhs, int rhs)
{
    return lhs != lldouble(rhs);
}
inline bool operator>(const lldouble& lhs, int rhs)
{
    return lhs > lldouble(rhs);
}
inline bool operator<(const lldouble& lhs, int rhs)
{
    return lhs < lldouble(rhs);
}
inline bool operator>=(const lldouble& lhs, int rhs)
{
    return lhs >= lldouble(rhs);
}
inline bool operator<=(const lldouble& lhs, int rhs)
{
    return lhs <= lldouble(rhs);
}

inline bool operator==(double lhs, const lldouble& rhs)
{
    return lldouble(lhs) == rhs;
}
inline bool operator!=(double lhs, const lldouble& rhs)
{
    return lldouble(lhs) != rhs;
}
inline bool operator>(double lhs, const lldouble& rhs)
{
    return lldouble(lhs) > rhs;
}
inline bool operator<(double lhs, const lldouble& rhs)
{
    return lldouble(lhs) < rhs;
}
inline bool operator>=(double lhs, const lldouble& rhs)
{
    return lldouble(lhs) >= rhs;
}
inline bool operator<=(double lhs, const lldouble& rhs)
{
    return lldouble(lhs) <= rhs;
}

inline bool operator==(const lldouble& lhs, double rhs)
{
    return lhs == lldouble(rhs);
}
inline bool operator!=(const lldouble& lhs, double rhs)
{
    return lhs != lldouble(rhs);
}
inline bool operator>(const lldouble& lhs, double rhs)
{
    return lhs > lldouble(rhs);
}
inline bool operator<(const lldouble& lhs, double rhs)
{
    return lhs < lldouble(rhs);
}
inline bool operator>=(const lldouble& lhs, double rhs)
{
    return lhs >= lldouble(rhs);
}
inline bool operator<=(const lldouble& lhs, double rhs)
{
    return lhs <= lldouble(rhs);
}

inline bool operator==(const string& lhs, const lldouble& rhs)
{
    return lldouble(lhs) == rhs;
}
inline bool operator!=(const string& lhs, const lldouble& rhs)
{
    return lldouble(lhs) != rhs;
}
inline bool operator>(const string& lhs, const lldouble& rhs)
{
    return lldouble(lhs) > rhs;
}
inline bool operator<(const string& lhs, const lldouble& rhs)
{
    return lldouble(lhs) < rhs;
}
inline bool operator>=(const string& lhs, const lldouble& rhs)
{
    return lldouble(lhs) >= rhs;
}
inline bool operator<=(const string& lhs, const lldouble& rhs)
{
    return lldouble(lhs) <= rhs;
}

inline bool operator==(const lldouble& lhs, const string& rhs)
{
    return lhs == lldouble(rhs);
}
inline bool operator!=(const lldouble& lhs, const string& rhs)
{
    return lhs != lldouble(rhs);
}
inline bool operator>(const lldouble& lhs, const string& rhs)
{
    return lhs > lldouble(rhs);
}
inline bool operator<(const lldouble& lhs, const string& rhs)
{
    return lhs < lldouble(rhs);
}
inline bool operator>=(const lldouble& lhs, const string& rhs)
{
    return lhs >= lldouble(rhs);
}
inline bool operator<=(const lldouble& lhs, const string& rhs)
{
    return lhs <= lldouble(rhs);
}