#include "aplusb.h"
#include <bits/stdc++.h>
using namespace std;
using cd = complex<double>;
const double PI = acos(-1);
void fft(vector<cd> &a, bool invert) {
int n = a.size();
if (n == 1) return;
vector<cd> a0(n / 2), a1(n / 2);
for (int i = 0; 2 * i < n; i++) {
a0[i] = a[i * 2];
a1[i] = a[i * 2 + 1];
}
fft(a0, invert);
fft(a1, invert);
for (int i = 0; 2 * i < n; i++) {
cd w = polar(1.0, 2 * PI * i / n * (invert ? -1 : 1));
a[i] = a0[i] + w * a1[i];
a[i + n / 2] = a0[i] - w * a1[i];
if (invert) {
a[i] /= 2;
a[i + n / 2] /= 2;
}
}
}
vector<int> multiplyFFT(const vector<int> &a, const vector<int> &b) {
vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
int n = 1;
while (n < a.size() + b.size()) n <<= 1;
fa.resize(n); fb.resize(n);
fft(fa, false);
fft(fb, false);
for (int i = 0; i < n; i++) fa[i] *= fb[i];
fft(fa, true);
vector<int> result(n);
long long carry = 0;
for (int i = 0; i < n; i++) {
long long val = (long long)(round(fa[i].real())) + carry;
result[i] = val % 10;
carry = val / 10;
}
while (carry) {
result.push_back(carry % 10);
carry /= 10;
}
while (result.size() > 1 && result.back() == 0) result.pop_back();
return result;
}
vector<int> intToVector(int n) {
if (n == 0) return {0};
vector<int> res;
while (n > 0) {
res.push_back(n % 10);
n /= 10;
}
return res;
}
int vectorToInt(const vector<int>& v) {
int res = 0;
for (int i = v.size() - 1; i >= 0; i--) {
res = res * 10 + v[i];
}
return res;
}
int sum(int A, int B) {
vector<int> a = intToVector(A);
vector<int> b = intToVector(B);
vector<int> oneA(a.size(), 1);
vector<int> oneB(b.size(), 1);
vector<int> addA = multiplyFFT(a, oneA);
vector<int> addB = multiplyFFT(b, oneB);
int n = max(addA.size(), addB.size());
vector<int> result(n);
int carry = 0;
for (int i = 0; i < n; i++) {
int d = (i < addA.size() ? addA[i] : 0) +
(i < addB.size() ? addB[i] : 0) + carry;
result[i] = d % 10;
carry = d / 10;
}
if (carry) result.push_back(carry);
return vectorToInt(result);
}
