#include "bits/stdc++.h" #pragma GCC optimize("Ofast") // Begin Header {{{ #pragma region using namespace std; #ifndef DEBUG #define dump(...) #endif #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define rep(i, b, e) for (intmax_t i = (b), i##_limit = (e); i < i##_limit; ++i) #define repc(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i) #define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i) #define var(Type, ...) \ Type __VA_ARGS__; \ input(__VA_ARGS__) #define let const auto constexpr size_t operator""_zu(unsigned long long value) { return value; }; constexpr intmax_t operator""_jd(unsigned long long value) { return value; }; constexpr uintmax_t operator""_ju(unsigned long long value) { return value; }; constexpr int INF = 0x3f3f3f3f; constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd; using usize = size_t; using imax = intmax_t; using uimax = uintmax_t; using ld = long double; template > using MaxHeap = priority_queue, Compare>; template > using MinHeap = priority_queue, Compare>; inline void input() {} template inline void input(Head&& head, Tail&&... tail) { cin >> head; input(forward(tail)...); } template ::value, nullptr_t> = nullptr> inline istream& operator>>(istream& is, Container& vs) { for (auto& v: vs) is >> v; return is; } template inline istream& operator>>(istream& is, pair& p) { is >> p.first >> p.second; return is; } inline void output() { cout << "\n"; } template inline void output(Head&& head, Tail&&... tail) { cout << head; if (sizeof...(tail)) cout << " "; output(forward(tail)...); } template ::value, nullptr_t> = nullptr> inline ostream& operator<<(ostream& os, const Container& vs) { static constexpr const char* delim[] = {" ", ""}; for (auto it = begin(vs); it != end(vs); ++it) { os << delim[it == begin(vs)] << *it; } return os; } template inline void join(const Iterator& Begin, const Iterator& End, const string& delim = "\n", const string& last = "\n") { for (auto it = Begin; it != End; ++it) { cout << ((it == Begin) ? "" : delim) << *it; } cout << last; } template inline vector makeVector(const T& init_value, size_t sz) { return vector(sz, init_value); } template inline auto makeVector(const T& init_value, size_t sz, Args... args) { return vector(init_value, args...))>( sz, makeVector(init_value, args...)); } template class FixPoint : Func { public: explicit constexpr FixPoint(Func&& f) noexcept : Func(forward(f)) {} template constexpr decltype(auto) operator()(Args&&... args) const { return Func::operator()(*this, std::forward(args)...); } }; template static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept { return FixPoint {forward(f)}; } template struct reverse_t { Container& c; reverse_t(Container& c) : c(c) {} auto begin() { return c.rbegin(); } auto end() { return c.rend(); } }; template auto reversed(Container& c) { return reverse_t(c); } template inline bool chmax(T& a, const T& b) noexcept { return b > a && (a = b, true); } template inline bool chmin(T& a, const T& b) noexcept { return b < a && (a = b, true); } template inline T diff(const T& a, const T& b) noexcept { return a < b ? b - a : a - b; } template inline T sigma(const T& l, const T& r) noexcept { return (l + r) * (r - l + 1) / 2; } template inline T ceildiv(const T& n, const T& d) noexcept { return (n + d - 1) / d; } void operator|=(vector::reference lhs, const bool rhs) { lhs = lhs | rhs; } void operator&=(vector::reference lhs, const bool rhs) { lhs = lhs & rhs; } void operator^=(vector::reference lhs, const bool rhs) { lhs = lhs ^ rhs; } void ioinit() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); clog << fixed << setprecision(10); } #pragma endregion // }}} End Header // BigInt {{{ // base and base_digits must be consistent const intmax_t base = 1000000000; const int base_digits = 9; struct BigInt { vector ds; int sign; BigInt() : sign(1) {} BigInt(intmax_t v) { *this = v; } BigInt(const string& s) { read(s); } void operator=(const BigInt& v) { sign = v.sign; ds = v.ds; } void operator=(intmax_t v) { sign = 1; if (v < 0) sign = -1, v = -v; for (; v > 0; v = v / base) ds.push_back(v % base); } BigInt operator+(const BigInt& v) const { if (sign == v.sign) { BigInt res = v; for (int i = 0, carry = 0; i < (int) max(ds.size(), v.ds.size()) || carry; ++i) { if (i == (int) res.ds.size()) res.ds.push_back(0); res.ds[i] += carry + (i < (int) ds.size() ? ds[i] : 0); carry = res.ds[i] >= base; if (carry) res.ds[i] -= base; } return res; } return *this - (-v); } BigInt operator-(const BigInt& v) const { if (sign == v.sign) { if (abs() >= v.abs()) { BigInt res = *this; for (int i = 0, carry = 0; i < (int) v.ds.size() || carry; ++i) { res.ds[i] -= carry + (i < (int) v.ds.size() ? v.ds[i] : 0); carry = res.ds[i] < 0; if (carry) res.ds[i] += base; } res.trim(); return res; } return -(v - *this); } return *this + (-v); } void operator*=(intmax_t v) { if (v < 0) sign = -sign, v = -v; for (intmax_t i = 0, carry = 0; i < (intmax_t) ds.size() || carry; ++i) { if (i == (intmax_t) ds.size()) ds.push_back(0); intmax_t cur = ds[i] * v + carry; carry = cur / base; ds[i] = cur % base; } trim(); } BigInt operator*(intmax_t v) const { BigInt res = *this; res *= v; return res; } friend pair divmod(const BigInt& a1, const BigInt& b1) { intmax_t norm = base / (b1.ds.back() + 1); BigInt a = a1.abs() * norm; BigInt b = b1.abs() * norm; BigInt q, r; q.ds.resize(a.ds.size()); for (int i = a.ds.size() - 1; i >= 0; i--) { r *= base; r += a.ds[i]; intmax_t s1 = r.ds.size() <= b.ds.size() ? 0 : r.ds[b.ds.size()]; intmax_t s2 = r.ds.size() <= b.ds.size() - 1 ? 0 : r.ds[b.ds.size() - 1]; intmax_t d = (base * s1 + s2) / b.ds.back(); r -= b * d; while (r < BigInt(0)) r += b, --d; q.ds[i] = d; } q.sign = a1.sign * b1.sign; r.sign = a1.sign; q.trim(); r.trim(); return make_pair(q, r / norm); } BigInt operator/(const BigInt& v) const { return divmod(*this, v).first; } BigInt operator%(const BigInt& v) const { return divmod(*this, v).second; } void operator/=(intmax_t v) { if (v < 0) sign = -sign, v = -v; for (intmax_t i = (intmax_t) ds.size() - 1, rem = 0; i >= 0; --i) { intmax_t cur = ds[i] + rem * base; ds[i] = cur / v; rem = cur % v; } trim(); } BigInt operator/(intmax_t v) const { BigInt res = *this; res /= v; return res; } int operator%(intmax_t v) const { if (v < 0) v = -v; intmax_t m = 0; for (int i = ds.size() - 1; i >= 0; --i) m = (ds[i] + m * base) % v; return m * sign; } void operator+=(const BigInt& v) { *this = *this + v; } void operator-=(const BigInt& v) { *this = *this - v; } void operator*=(const BigInt& v) { *this = *this * v; } void operator/=(const BigInt& v) { *this = *this / v; } bool operator<(const BigInt& v) const { if (sign != v.sign) return sign < v.sign; if (ds.size() != v.ds.size()) return ds.size() * sign < v.ds.size() * v.sign; for (int i = ds.size() - 1; i >= 0; i--) if (ds[i] != v.ds[i]) return ds[i] * sign < v.ds[i] * sign; return false; } bool operator>(const BigInt& v) const { return v < *this; } bool operator<=(const BigInt& v) const { return !(v < *this); } bool operator>=(const BigInt& v) const { return !(*this < v); } bool operator==(const BigInt& v) const { return !(*this < v) && !(v < *this); } bool operator!=(const BigInt& v) const { return *this < v || v < *this; } void trim() { while (!ds.empty() && !ds.back()) ds.pop_back(); if (ds.empty()) sign = 1; } bool is_zero() const { return ds.empty() || (ds.size() == 1 && !ds[0]); } BigInt operator-() const { BigInt res = *this; res.sign = -sign; return res; } BigInt abs() const { BigInt res = *this; res.sign *= res.sign; return res; } friend string to_string(const BigInt& v) { stringstream ss; if (v.sign == -1) ss << '-'; ss << (v.ds.empty() ? 0 : v.ds.back()); for (int i = (int) v.ds.size() - 2; i >= 0; --i) ss << setw(base_digits) << setfill('0') << v.ds[i]; return ss.str(); } template operator Tp() const { Tp res = 0; for (int i = ds.size() - 1; i >= 0; i--) res = res * base + ds[i]; return res * sign; } friend BigInt gcd(const BigInt& a, const BigInt& b) { return b.is_zero() ? a : gcd(b, a % b); } friend BigInt lcm(const BigInt& a, const BigInt& b) { return a / gcd(a, b) * b; } void read(const string& s) { sign = 1; ds.clear(); int pos = 0; while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) { if (s[pos] == '-') sign = -sign; ++pos; } for (int i = s.size() - 1; i >= pos; i -= base_digits) { int x = 0; for (int j = max(pos, i - base_digits + 1); j <= i; j++) x = x * 10 + s[j] - '0'; ds.push_back(x); } trim(); } friend istream& operator>>(istream& stream, BigInt& v) { string s; stream >> s; v.read(s); return stream; } friend ostream& operator<<(ostream& stream, const BigInt& v) { if (v.sign == -1) stream << '-'; stream << (v.ds.empty() ? 0 : v.ds.back()); for (int i = (int) v.ds.size() - 2; i >= 0; --i) stream << setw(base_digits) << setfill('0') << v.ds[i]; return stream; } static vector convert_base(const vector& a, int old_digits, int new_digits) { vector p(max(old_digits, new_digits) + 1); p[0] = 1; for (int i = 1; i < (int) p.size(); i++) p[i] = p[i - 1] * 10; vector res; intmax_t cur = 0; int cur_digits = 0; for (int i = 0; i < (int) a.size(); i++) { cur += a[i] * p[cur_digits]; cur_digits += old_digits; while (cur_digits >= new_digits) { res.push_back(cur % p[new_digits]); cur /= p[new_digits]; cur_digits -= new_digits; } } res.push_back(cur); while (!res.empty() && !res.back()) res.pop_back(); return res; } static vector karatsuba_multiply(const vector& a, const vector& b) { int n = a.size(); vector res(n + n); if (n <= 32) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) res[i + j] += a[i] * b[j]; return res; } int k = n >> 1; vector a1(a.begin(), a.begin() + k); vector a2(a.begin() + k, a.end()); vector b1(b.begin(), b.begin() + k); vector b2(b.begin() + k, b.end()); vector a1b1 = karatsuba_multiply(a1, b1); vector a2b2 = karatsuba_multiply(a2, b2); for (int i = 0; i < k; i++) a2[i] += a1[i]; for (int i = 0; i < k; i++) b2[i] += b1[i]; vector r = karatsuba_multiply(a2, b2); for (int i = 0; i < (int) a1b1.size(); i++) r[i] -= a1b1[i]; for (int i = 0; i < (int) a2b2.size(); i++) r[i] -= a2b2[i]; for (int i = 0; i < (int) r.size(); i++) res[i + k] += r[i]; for (int i = 0; i < (int) a1b1.size(); i++) res[i] += a1b1[i]; for (int i = 0; i < (int) a2b2.size(); i++) res[i + n] += a2b2[i]; return res; } BigInt operator*(const BigInt& v) const { vector a6 = convert_base(this->ds, base_digits, 6); vector b6 = convert_base(v.ds, base_digits, 6); vector a(a6.begin(), a6.end()); vector b(b6.begin(), b6.end()); while (a.size() < b.size()) a.push_back(0); while (b.size() < a.size()) b.push_back(0); while (a.size() & (a.size() - 1)) a.push_back(0), b.push_back(0); vector c = karatsuba_multiply(a, b); BigInt res; res.sign = sign * v.sign; for (intmax_t i = 0, carry = 0; i < (intmax_t) c.size(); i++) { intmax_t cur = c[i] + carry; res.ds.push_back(cur % 1000000); carry = cur / 1000000; } res.ds = convert_base(res.ds, 6, base_digits); res.trim(); return res; } }; // }}} int main() { ioinit(); var(BigInt, A, B); output(A + B); return 0; }