/**
(A0 + A1*10^(n/2)) * (B0 + B1*10^(n/2)) =
A0*B0 + A1*B1*10^n + (A0*B1 + A1*B0)*10^(n/2)

(A0+A1)(B0+B1) - A0*B0 - A1*B1 = A0*B1 + A1*B0

n^{log_2(4)} = n^2
n^{log_2(3)} = n^{1.58}
*/

/***
		1. N = 2^k
		
		2. Переносов нет!
		   Алгоритм Карацубы умножает многочлены
		   123456 = 1*10^5 + 2*10^4 + 3*10^3 + ...
		   = 1*x^5 + 2*x^4 + 3*x^3 + ... (x=10)

		3. if (N <= 16) то умножай за квадрат					  
*/

// a[0..n) b[0..n) c[0..2n) 
// a[0] -- младший разряд
void multiply( int n, int *a, int *b, int *c ) {
	if (n <= 16) {
		...
		return;
	}
	int n1 = n / 2;
	// (a0+a1), (b0+b1), (a0+a1)*(b0+b1)
	int sa[n1], sb[n1], f[n]; 
	for (int i = 0; i < n1; i++) {
		sa[i] = a[i] + a[i + n1];
		sb[i] = b[i] + b[i + n1];
	}
	multiply(n1, a, b, c); // a0*b0
	multiply(n1, a + n1, b + n1, c + n); // a1*b1
	multiply(n1, sa, sb, f); // f = sa*sb
	// a0*b0, a1*b1, a0*b1+a1*b0 
	//    = (a0+a1)*(b0+b1) - a0*b0 - a1*b1
	for (int i = 0; i < n; i++)
		f[i] -= c[i] + c[i + n];
	for (int i = 0; i < n; i++)
		c[i + n1] += f[i];
}
/***
  Какие числа можно умножить за n^2 за 1 секунду?
  60 000 потому что система счисления не 10, а 10^9

  А Карацуба? n^{1.58}
  400 000 за 1 секунду
*/