//******************************************************
//Загаловочные файлы, использованные в реализации класса
//******************************************************
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

using namespace std;

//*******************************
//Класс, использованный в проекте
//*******************************

class GiantInteger {
private:
    vector <int> number; // vector, хранящий по 9 цифр исходного числа в ячейке, записанных с конца для упрощения алгоритмов вычисления
    bool negative; // флаг отрицательности числа. true - отрицательное, false - положительное
    static const int basis = 1000000000; // ключевое слово static обеспечивает хранение данной переменной в памяти до непосредственного завершения программы
public:
    GiantInteger() {} // конструктор без параметров

    GiantInteger(string str) { // создание числа на основе переменной типа string
        if (str.length() == 0) negative = false;
        else {
            if (str[0] == '-') {
                str = str.substr(1);
                negative = true;
            }
            else negative = false;
        }
        for (int i = str.length(); i > 0; i -= 9) {
            if (i < 9) {
                number.push_back(atoi(str.substr(0, i).c_str())); // функция c_str() используется, поскольку функция atoi принимает на вход указатель на string
            }
            else number.push_back(atoi(str.substr(i-9, 9).c_str()));
        }
    }

    ~GiantInteger() {} // деструктор класса

    friend ostream& operator <<(ostream& out, const GiantInteger& num) { // перегрузка оператора вывода
        if (num.number.empty()) out << 0;
        else {
            if (num.negative) out << '-';
            out << num.number.back();
            char old_fill = out.fill('0'); // задаётся символ заполнения, который заполняет места удалённых нолей
            for (int i = num.number.size() - 2; i >= 0; --i) {
                out << setw(9) << num.number[i]; // задаётся вывод шириной в 9 символов, именно столько хранится в одной ячейке вектора number
            }
            out.fill(old_fill); // возврат стандартного символа заполнения
        }
        return out;
    }

    friend bool operator ==(const GiantInteger& left, const GiantInteger& right) { // перегрузка оператора равенства
        if (left.negative != right.negative) return false;
        if (left.number.empty()) {
            if (right.number.empty() || (right == 0)) return true;
            else return false;
        }
        if (right.number.empty()) {
            if (left == 0) return true;
            else return false;
        }
        if (left.number.size() != right.number.size()) return false;
        for (int i = 0; i < left.number.size(); ++i) if (left.number[i] != right.number[i]) return false;
        return true;
    }

    friend bool operator !=(const GiantInteger& left, const GiantInteger& right) { // перегрузка оператора неравенства
        return !(left == right);
            }

    friend bool operator <(const GiantInteger& left, const GiantInteger& right) { // перегрузка оператора меньше
        if (left == right) return false;
        if (left.negative) {
            if (right.negative) return ((-right) < (-left));
            else return true;
        }
        else if (right.negative) return false;
        else {
            if (left.number.size() != right.number.size()) {
                return left.number.size() < right.number.size();
            }
            else {
                for (int i = left.number.size() - 1; i >= 0; --i) {
                    if (left.number[i] != right.number[i]) return left.number[i] < right.number[i];
                }
                return false;
            }
        }
    }

    friend bool operator <=(const GiantInteger& left, const GiantInteger& right) { // перегрузка оператора меньше или равно
        return (left < right || left == right);
    }

    GiantInteger operator = (const GiantInteger& num) { // перегрузка оператора присваивания
        negative = num.negative;
        number = num.number;
        return num;
    }

    void RemoveZeros() { // функция по удалению ведущих нулей
        while (number.size() > 1 && number.back() == 0) {
            number.pop_back();
        }
        if (number.size() == 1 && number[0] == 0) negative = false;
    }

    GiantInteger operator - () const { // перегрузка оператора унарный минус
        GiantInteger copy(*this);
        copy.negative = !copy.negative;
        return copy;
    }

    friend const GiantInteger operator + (GiantInteger left, GiantInteger right) { // перегрузка оператора сложения
        int carry = 0; // остаток
        if (left.negative) {
            if (right.negative) return -(-left + (-right));
            else return right - (-left);
        }
        else if (right.negative) return left - (-right);
        else {
            for (int i = 0; i < max(left.number.size(), right.number.size()) || carry != 0; ++i) {
                if (i == left.number.size()) left.number.push_back(0);
                left.number[i] += carry + (i < right.number.size() ? right.number[i] : 0); // тернарная условная операция
                carry = left.number[i] >= basis;
                if (carry != 0) left.number[i] -= basis;
            }
        }
        return left;
    }

    friend const GiantInteger operator -(GiantInteger left, GiantInteger right) { // перегрузка оператора вычитания
        if (right.negative) return left + (-right);
        else if (left.negative) return -(-left + right);
        else if (left < right) return -(right - left);
        int carry = 0;
        for (int i = 0; i < right.number.size() || carry != 0; ++i) {
            left.number[i] -= carry + (i < right.number.size() ? right.number[i] : 0);
            carry = left.number[i] < 0;
            if (carry != 0) left.number[i] += basis;
        }
        left.RemoveZeros(); // удаление ведущих нулей
        return left;
    }

    friend const GiantInteger operator *(const GiantInteger& left, const GiantInteger& right) { // перегрузка оператора умножения
        GiantInteger result;
        result.number.resize(left.number.size() + right.number.size());
        for (int i = 0; i < left.number.size(); ++i) {
            int carry = 0;
            for (int j = 0; j < right.number.size() || carry != 0; ++j) {
                long long cur = result.number[i + j] + left.number[i] * 1LL * (j < right.number.size() ? right.number[j] : 0) + carry;
                result.number[i + j] = static_cast<int>(cur % basis);
                carry = static_cast<int>(cur / basis);
            }
        }
        result.negative = left.negative != right.negative;
        result.RemoveZeros();
        return result;
    }

    GiantInteger (int l) { // конструктор объекта класса на основне переменной класса int
        if (l < 0) { this->negative = true; l = -l; }
        else this->negative = false;
        do {
            this->number.push_back(l % basis);
            l /= basis;
        } while (l != 0);
    }

    void Shift() { // функция сдвига вправо, использующаяся в алгоритме деления
        if (number.size() == 0) {
            number.push_back(0);
            return;
        }
        number.push_back(number[number.size() - 1]);
        for (int i = number.size() - 2; i > 0; --i) number[i] = number[i - 1];
        number[0] = 0;
    }

    friend const GiantInteger operator /(const GiantInteger& left, const GiantInteger& right) { // перегрузка оператора деления
        if (right == 0) {
            return left;
        }
        GiantInteger b = right;
        b.negative = false;
        GiantInteger result, current;
        result.number.resize(left.number.size());
        for (int i = (left.number.size()) - 1; i >= 0; --i) {
            current.Shift();
            current.number[0] = left.number[i];
            current.RemoveZeros();
            int x = 0, l = 0, r = basis;
            while (l <= r) { // алгоритм поиска максимального делителя
                int m = (l + r) / 2;
                GiantInteger t = b * m;
                if (t <= current) {
                    x = m;
                    l = m + 1;
                }
                else r = m - 1;
            }
            result.number[i] = x; // записываем найденныый делитель
            current = current - b * x;
        }
        result.negative = left.negative != right.negative;
        result.RemoveZeros();
        return result;
    }
};