// num a, b = {2, 3};
// a + b
// a - b
// a * b
// a / b

// a.real()
// a.imag()


// // ~20% 
// struct Complex {

// };

// double // 8 байт
// long double // 10 байт | g++

using num = complex<double>;

// a[0] + a[1]*x^1 + a[2]*x^2 + ...
vector<num> FFT(vector<num> &a) {
	int n = a.size();
	if (n == 1) {
		// A(1) = a[0]
		return a;
	}
	vector<num> a0, a1;
	forn(i, n)
		(i % 2 ? a1 : a0).push_back(a[i]);
	auto f0 = FFT(a0);
	auto f1 = FFT(a1);
	vector<num> f(n);
	int n1 = n / 2;
	forn(i, n) {
		double ang = 2 * M_PI / n * i;
		num w = {cos(ang), sin(ang)}; 
		f[i] = f0[i % n1] + w * f1[i % n1];
	}
	return f;
}
// T(n) = 2T(n/2) + n = Theta(nlogn)


w^0 = w^0
w^{-1} = w^{n-1}
w^{-2} = w^{n-2}
...
w^{-(n-1)} = w^{1}

vector<num> FFT_inverse(vector<num> &f) {
	auto a = FFT(f);
	reverse(a.begin() + 1, a.end());
	forn(i, n)
		a[i] /= num(n, 0);
}
vector<int> mul(vector<int> &a, vector<int> &b) {
	a -> A | int -> complex
	A[i] = {a[i], 0}

	b -> B
	A = FFT(A)
	B = FFT(B)
	C : C[i] = A[i]*B[i]
	C = FFT_inverse(C)
	C -> c
	vector<int> res(n);
	forn(i, n)
		res[i] = round(c[i].real())
	return res;
}

double | 10^{15} | 8 байт
long double | 10^{18} | 10 байт

a[i] < C, b[i] < C
ab[i] < C^2 * n
ab[k] = sum a[i]*b[k-i]

C = 10^4, n = 10^5 | 10^{13} | double
C = 10^3, n = 10^6 | 10^{12} | double

C = 10^5, n = 10^6 | 10^{16} | long double
C = 10^4, n = 10^6 | 10^{14} | long double

Умножение чисел = умножение многочленов

number = sum_i (BASE^i * a[i])
N
BASE=10^k
N/k
3*FFT(N/k) = 3 N/k log(N/k)

a -> fa
b -> fb

z = (a,b)
z -> fz
fa[k] = 0.5 * (fz[k] + fz[(n-k)%n].conj())
fb[k] = ?!


// const int n = 1 << 20;
// n = 2^m

void init() {
	forn(i, n)
		rev[i] = rev[i/2] + (i%2)<<(m-1);
	forn(i, n) {
		double ang = 2 * M_PI / n * i;
		roots[i] = {cos(ang), sin(ang)}; 
	}
	
	// roots[i+1] = roots[i]*roots[1]
	// BASE=10

	double ang = 2 * M_PI / n;
	roots[0] = {1, 0};
	roots[1] = {cos(ang), sin(ang)}; 
	for (int i = 2; i < n; i++) {
		roots[2*i] = roots[i]*roots[i]
		roots[2*i+1] = roots[i]*roots[i]*roots[1]
	}
}

vector<num> FFT(vector<num> &a) {
	int n = a.size();
	// if (n == 1) {
	// 	// A(1) = a[0]
	// 	return a;
	// }
	// vector<num> a0, a1;
	// forn(i, n)
	// 	(i % 2 ? a1 : a0).push_back(a[i]);
	vector<num> f(n);
	forn(i, n)
		f[i] = a[rev[i]];

	for (int k = 1; k < n; k *= 2, logk++) {
		// k, k --> 2k
		for (int s = 0; s < n; s += 2 * k) {
			// auto f0 = FFT(a0);
			// [s,s+k)

			// auto f1 = FFT(a1);
			// [s+k,s+2k)

			// f : [s,s+2k]

			forn(i, k) {
				// k + k = 2k
				// double ang = 2 * M_PI / (2*k) * i;
				// num w = {cos(ang), sin(ang)}; 
				// auto w = roots[logk][i];
				auto w = roots[i * (n / (2*k))];

				// Преобразования бабочки
				auto F0 = f[s+i];
				auto F1 = f[s+k+i]
				auto tmp = w * F1;
				f[s+i] = F0 + tmp;
				f[s+k+i] = F0 - tmp;
			}
			// forn(i, n1) {
			// 	double ang = 2 * M_PI / n * i;
			// 	num w = {cos(ang), sin(ang)}; 
			// 	f[i] = f0[i] + w * f1[i];
			// 	f[i+n1] = f0[i] - w * f1[i];
			// }
		}
	}
}



const int BASE = 1e9;
const int BLEN = 9;
const int LEN = 100/BLEN + 1;

struct Long {
	vector<int> a;
	int len = i; // a[i] != 0 : i = max
	Long(int x = 0) : a(LEN) {
		a[0] = x; // x < 10^9
	}
};

Long operator + (Long x, Long y) {
	forn(i, LEN)
		if ((x.a[i] += y.a[i]) >= BASE)
			x.a[i] -= BASE, x.a[i+1]++;
}

Long operator / (Long x, int y) {
	int64_t carry = 0;
	for (int i = LEN - 1; i >= 0; i--) {
		carry += x.a[i];
		x.a[i] = carry / y;
		carry %= y, carry *= BASE;
	}
}

bool operator < (Long x, Long y) {
	for (int i = LEN - 1; i >= 0; i--) 
		if (x.a[i] != y.a[i])
			return x.a[i] < y.a[i];
	return 0;
}
int cmp(Long x, Long y) { // <0, =0, >0
	for (int i = LEN - 1; i >= 0; i--) 
		if (x.a[i] != y.a[i])
			return x.a[i] - y.a[i];
	return 0;
}