Addition of Big Integers

Given two integers $A$ and $B$, compute the sum, $A + B$.

Input

Two integers $A$ and $B$ separated by a space character are given in a line.

Output

Print the sum in a line.

Constraints

* $-1 \times 10^{100000} \leq A, B \leq 10^{100000}$



Sample Input 1


5 8


Sample Output 1


13


Sample Input 2


100 25


Sample Output 2


125


Sample Input 3


-1 1


Sample Output 3


0


Sample Input 4


12 -3


Sample Output 4


9






Example

Input

5 8


Output

13
#include<bits/stdc++.h>
using namespace std;




namespace nv {

	static const unsigned int billion = 10u;

	using sign_t = bool;
	static const sign_t sign_plus = false;
	static const sign_t sign_minus = true;



	static inline sign_t mul_sign(sign_t a, sign_t b) { return !(a && b) && (a || b); }

	bool less_array_bil(
		const unsigned int *a, size_t len_a,
		const unsigned int *b, size_t len_b
	) {
		for (size_t i = len_a; i < len_b; i++)if (b[i] != 0) return true;
		for (size_t i = len_b; i < len_a; i++)if (a[i] != 0) return false;
		for (size_t i = min(len_a, len_b) - 1; i != (size_t)-1; i--) {
			if (a[i] < b[i]) return true;
			if (a[i] > b[i]) return false;
		}
		return false; // a == b
	}

	void add_array_bil(
		const unsigned int *a, size_t len_a,
		const unsigned int *b, size_t len_b,
		unsigned int *result, size_t len_result,
		int *o_carry
	) {
		if (len_a < len_b) { swap(a, b); swap(len_a, len_b); }

		unsigned int carry = 0;

		size_t i = 0;
		for (; i < len_b; i++) {
			if (i >= len_result) return;
			result[i] = a[i] + b[i] + carry;
			if (result[i] < billion) { carry = 0; }
			else { carry = 1; result[i] -= billion; }
		}
		for (; i < len_a; i++) {
			if (i >= len_result) return;
			result[i] = a[i] + carry;
			if (result[i] < billion) { carry = 0; }
			else { carry = 1; result[i] -= billion; }
		}
		if (i < len_result) {
			result[i] = carry; carry = 0; i++;
			for (; i < len_result; i++) result[i] = 0;
		}
		if (o_carry) *o_carry = carry;
	}

	void addequal_array_bil(
		unsigned int *dest, size_t len_dest,
		const unsigned int *b, size_t len_b,
		int *o_carry
	) {
		size_t i = 0;
		unsigned int carry = 0;
		for (; i < len_b; i++) {
			if (i >= len_dest) return;
			dest[i] += b[i] + carry;
			if (dest[i] < billion) { carry = 0; }
			else { carry = 1; dest[i] -= billion; }
		}
		for (; i < len_dest; i++) {
			dest[i] += carry;
			if (dest[i] < billion) { carry = 0; break; }
			else { carry = 1; dest[i] -= billion; }
		}
		if (o_carry) *o_carry += carry;
	}

	void dif_array_bil(
		const unsigned int *a, size_t len_a,
		const unsigned int *b, size_t len_b,
		unsigned int *result, size_t len_result,
		sign_t *o_sign
	) {
		sign_t sign = sign_plus;
		if (less_array_bil(a, len_a, b, len_b)) { swap(a, b); swap(len_a, len_b); sign = !sign; }
		if (o_sign) *o_sign = sign;

		unsigned int borrow = 0;
		size_t i = 0;
		for (; i < len_b; i++) {
			if (i >= len_result) return;
			result[i] = a[i] + billion - b[i] - borrow;
			if (result[i] < billion) { borrow = 1; }
			else { borrow = 0; result[i] -= billion; }
		}
		for (; i < len_a; i++) {
			if (i >= len_result) return;
			result[i] = a[i] + billion - borrow;
			if (result[i] < billion) { borrow = 1; }
			else { borrow = 0; result[i] -= billion; }
		}
		for (; i < len_result; i++) result[i] = 0;
	}

	void subequal_array_bil(
		unsigned int *dest, size_t len_dest,
		const unsigned int *b, size_t len_b,
		int *o_carry
	) {
		size_t i = 0;
		unsigned int borrow = 0; // 0 or 1
		for (; i < len_b; i++) {
			if (i >= len_dest) return;
			dest[i] += billion - b[i] - borrow;
			if (dest[i] < billion) { borrow = 1; }
			else { borrow = 0; dest[i] -= billion; }
		}
		for (; i < len_dest; i++) {
			if (!borrow) break;
			if (dest[i]) { dest[i]--; borrow = 0; }
			else { dest[i] += billion - 1; }
		}
		if (o_carry) *o_carry -= borrow;
	}

	void mul_array_bil(
		const unsigned int *a, size_t len_a,
		const unsigned int *b, size_t len_b,
		unsigned int *result, size_t len_result
	) {
		if (len_a > len_result) len_a = len_result;
		if (len_b > len_result) len_b = len_result;
		if (len_a < len_b) { swap(a, b); swap(len_a, len_b); }

		for (int i = 0; i < len_result; i++) result[i] = 0;
		while (len_a != 0) { if (a[len_a - 1] != 0) break; len_a--; }
		while (len_b != 0) { if (a[len_b - 1] != 0) break; len_b--; }
		if (len_a == 0 || len_b == 0) return;

		len_result = min(len_result, len_a + len_b);

		if (len_result <= 2) {
			for (size_t ib = 0; ib < len_b; ib++) {
				unsigned int carry = 0;
				for (size_t ia = 0; ia < len_a && ib + ia < len_result; ia++) {
					unsigned long long buf = (unsigned long long)a[ia] * b[ib] + result[ia + ib] + carry;
					carry = (unsigned int)(buf / billion);
					result[ia + ib] = buf % billion;
				}
				if (len_a + ib < len_result) result[len_a + ib] = carry;
			}
			return;
		}

		size_t sep = (len_a + 1) / 2;
		int carry = 0;

		if (len_b <= sep) {
			vector<unsigned int> buf(sep + len_b);
			mul_array_bil(a, sep, b, len_b, &buf.front(), sep + len_b);
			for (size_t i = 0; i < sep + len_b; i++) { result[i] = buf[i]; }
			mul_array_bil(a + sep, len_a - sep, b, len_b, &buf.front(), len_a - sep + len_b);
			addequal_array_bil(result + sep, len_result - sep, &buf.front(), len_a - sep + len_b, nullptr);
			return;
		}


		vector<unsigned int> buf1(sep * 2);
		vector<unsigned int> buf2(sep * 2);


		mul_array_bil(a, sep, b, sep, &buf1.front(), sep * 2);
		mul_array_bil(a + sep, len_a - sep, b + sep, len_b - sep, &buf2.front(), len_result - sep * 2);


		for (size_t i = 0; i < sep * 2; i++) { result[i] = buf1[i]; }
		addequal_array_bil(result + sep, len_result - sep, &buf1.front(), sep * 2, &carry);
		addequal_array_bil(result + sep, len_result - sep, &buf2.front(), sep * 2, &carry);
		if (len_result > sep * 3) result[sep * 3] = carry;
		addequal_array_bil(result + sep * 2, len_result - sep * 2, &buf2.front(), sep * 2, nullptr);

		bool signa, signb;


		dif_array_bil(a, sep, a + sep, len_a - sep, &buf1.front(), sep, &signa);
		dif_array_bil(b, sep, b + sep, len_b - sep, &buf1.at(sep), sep, &signb);

		mul_array_bil(&buf1.front(), sep, &buf1.at(sep), sep, &buf2.front(), sep * 2);
		signa = mul_sign(mul_sign(signa, signb), sign_minus);
		if (signa == sign_plus) {
			addequal_array_bil(result + sep, len_result - sep, &buf2.front(), sep * 2, nullptr);
		}
		else {
			subequal_array_bil(result + sep, len_result - sep, &buf2.front(), sep * 2, nullptr);
		}
	}

}


class VLInteger
{
public:

	using sign_t = nv::sign_t;
	static const sign_t vl_plus = nv::sign_plus;
	static const sign_t vl_minus = nv::sign_minus;

private:

	using digit_t = unsigned int;
	using vector_t = vector<digit_t>;

	vector_t m;

	sign_t m_sign;

	static const digit_t base = 10; // 10^9
	static const digit_t baseBase = 10;
	static const digit_t baseDigits = 1;

public:

	VLInteger() : m(), m_sign(vl_plus) {}

	VLInteger(const VLInteger & s) : m(s.m), m_sign(s.m_sign) {}

	VLInteger(VLInteger && s) : m(move(s.m)), m_sign(s.m_sign) {}

	VLInteger(const string &s);

	VLInteger(const vector_t &s, sign_t sign = vl_plus) : m(s), m_sign(sign) {}

	VLInteger(vector_t &&s) : m(s) {}

	virtual ~VLInteger() = default;


	bool operator==(const VLInteger &b) const { return m == b.get(); }
	bool operator<(const VLInteger &b) const;

	bool operator>(const VLInteger &b) const { return b < *this; }
	bool operator>=(const VLInteger &b) const { return !(operator<(b)); }
	bool operator<=(const VLInteger &b) const { return !operator>(b); }


	bool iszero() const { return getdigitnum() == 0; }

	operator bool() const { return !iszero(); }


	void set_sign(sign_t sign) { m_sign = sign; }

	void set_digit(digit_t digit, size_t pos);

	void set(digit_t digit, size_t pos);

	void regularize();

	void shrink_to_fit() { m.shrink_to_fit(); }


	VLInteger operator*(const VLInteger &) const;

	VLInteger & operator*=(const VLInteger &);


	VLInteger operator+(const VLInteger &) const;

	VLInteger & operator+=(const VLInteger &);


	VLInteger operator-(const VLInteger &) const;

	VLInteger & operator-=(const VLInteger &);

	sign_t getsign() const { return m_sign; }

	const vector<unsigned int> &get() const { return m; }

	const digit_t getdigit(size_t p) const;

	const digit_t at(size_t p) const { return m.at(p); }

	const size_t getdigitnum() const;

	void clear() { m.clear(); }

	string toString() const;

	VLInteger & operator=(VLInteger && rv) {
		m = move(rv.m); m_sign = rv.m_sign;
		return *this;
	}
	VLInteger & operator=(const VLInteger & lv) {
		m = lv.m; m_sign = lv.m_sign;
		return *this;
	}
};

istream &operator>>(istream &cin, VLInteger &v);
ostream &operator<<(ostream &cout, const VLInteger &v);


static VLInteger operator"" _VLI(const char *s, std::size_t len) {
	return move(VLInteger(string({ s, len })));
}




VLInteger::VLInteger(const string & s) :
	m(), m_sign(vl_plus)
{
	size_t i = 0;
	if (!s.size()) return;
	if (s[i] == '-') { m_sign = vl_minus; i++; }
	else if (s[i] == '+') { m_sign = vl_plus; i++; }

	size_t len = (s.size() - i - 1) / 9 + 1;
	m.resize(len);
	for (; i < s.size(); i++) {
		if (s[i] < '0' || '9' < s[i]) { clear(); return; }
		set_digit(s[i] - '0', s.size() - i - 1);
	}
	regularize();
}





bool VLInteger::operator<(const VLInteger &b) const {
	if (getsign() != b.getsign()) {
		return !(iszero() && b.iszero()) && (getsign() == vl_minus);
	}
	const VLInteger &A = (getsign() == vl_plus) ? *this : b;
	const VLInteger &B = (getsign() == vl_minus) ? *this : b;
	if (B.m.size() != A.m.size()) return A.m.size() < B.m.size();
	for (size_t i = A.m.size() - 1; i != (size_t)-1; i--) {
		if (A.m[i] == B.m[i]) return A.m[i] < B.m[i];
	}
	return false; // A == B
}





void VLInteger::set_digit(digit_t digit, size_t p) {
	assert(digit < baseBase);
	size_t arrp = p / baseDigits;
	if (arrp >= m.size()) {
		if (digit == 0) return;
		m.resize(arrp + 1);
	}
	digit_t shift = 1; for (int i = 0; i < p % baseDigits; i++) shift *= 10;
	digit_t old = m[arrp] / shift % 10 * shift;
	m[arrp] = m[arrp] - old + digit * shift;
	regularize();
}

void VLInteger::set(digit_t digit, size_t p) {
	assert(digit < base);
	if (p >= m.size()) m.resize(p + 1);
	m[p] = digit;
}

void VLInteger::regularize() {
	while (m.size() != 0) {
		if (m.back() != 0) return;
		m.pop_back();
	}
	// m.size() == 0
	m_sign = vl_plus;
}

const VLInteger::digit_t VLInteger::getdigit(size_t p) const {
	digit_t buf = m.at(p / baseDigits);
	unsigned int shift = 1; for (int i = 0; i < p % baseDigits; i++) shift *= 10;
	return buf / shift % 10;
}

const size_t VLInteger::getdigitnum() const {
	size_t ans = 0;
	digit_t big = 0;
	for (int i = m.size() - 1; i >= 0; i--) {
		if (m[i] != 0) {
			big = m[i];
			ans += i * baseDigits;
			break;
		}
	}
	for (digit_t bigdig = 1; bigdig <= big; bigdig *= 10) {
		ans++;
	}
	return ans;
}

string VLInteger::toString() const {
	size_t pre = (getsign() == vl_minus ? 1 : 0);
	size_t dignum = getdigitnum();
	string buf; buf.resize(dignum + pre);
	if (pre) buf[0] = '-';
	if (dignum == 0) return buf + "0";
	for (size_t i = 0; i < dignum; i++) {
		buf[i + pre] = '0' + getdigit(dignum - i - 1);
	}
	return move(buf);
}





VLInteger VLInteger::operator+(const VLInteger & r) const {
	VLInteger result; result.m.resize(1 + max(m.size(), r.m.size()));

	if (iszero()) return r;
	if (r.iszero()) return *this;

	if (getsign() == r.getsign()) {
		result.set_sign(getsign());
		nv::add_array_bil(
			&m.front(), m.size(), &r.m.front(), r.m.size(),
			&result.m.front(), result.m.size(), nullptr
		);
	}
	else {
		sign_t signbuf;
		nv::dif_array_bil(
			&m.front(), m.size(), &r.m.front(), r.m.size(),
			&result.m.front(), result.m.size(),
			&signbuf
		);
		result.set_sign(nv::mul_sign(getsign(), signbuf));
	}
	result.regularize();
	return move(result);
}

VLInteger & VLInteger::operator+=(const VLInteger & r) {
	return *this = *this + r;
}

VLInteger VLInteger::operator-(const VLInteger & r) const {
	VLInteger result; result.m.resize(1 + max(m.size(), r.m.size()));
	if (r.iszero()) return *this;
	if (iszero()) {
		result = r; result.set_sign(!r.getsign());
		result.regularize();
		return move(result);
	}

	if (getsign() != r.getsign()) {
		result.set_sign(getsign());
		nv::add_array_bil(
			&m.front(), m.size(), &r.m.front(), r.m.size(),
			&result.m.front(), result.m.size(), nullptr
		);
	}
	else {
		sign_t signbuf;
		nv::dif_array_bil(
			&m.front(), m.size(), &r.m.front(), r.m.size(),
			&result.m.front(), result.m.size(),
			&signbuf
		);
		result.set_sign(nv::mul_sign(getsign(), signbuf));
	}
	result.regularize();
	return move(result);
}

VLInteger & VLInteger::operator-=(const VLInteger & r) {
	return *this = *this - r;
}




VLInteger VLInteger::operator*(const VLInteger & r) const {
	if (m.size() == 0 || r.m.size() == 0) return "0"_VLI;
	VLInteger ans; ans.m.resize(m.size() + r.m.size());
	nv::mul_array_bil(
		&m.front(), m.size(), &r.m.front(), r.m.size(),
		&ans.m.front(), ans.m.size()
	);
	ans.m_sign = nv::mul_sign(m_sign, r.m_sign);
	ans.regularize();
	return move(ans);
}

VLInteger & VLInteger::operator*=(const VLInteger & r) {
	*this = move(*this * r);
	return *this;
}


istream &operator>>(istream &cin, VLInteger &v) {
	string s; cin >> s;
	v = s;
	return cin;
}

ostream &operator<<(ostream &cout, const VLInteger &v) {
	return cout << v.toString();
}



int main() {
	VLInteger a, b;
	
	cin >> a >> b;
	cout << a+b << endl;

	return 0;
}



