#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iterator>
#include <ctime>
using namespace std;

struct BigInt
{
    vector<int> digits;

    BigInt(string str="0");

    BigInt operator+(const BigInt & bi) const;
    BigInt operator-(const BigInt & bi) const;
    BigInt operator*(const BigInt & bi) const;
    BigInt operator*(int n) const;
    BigInt operator<<(int n) const;
};

typedef const BigInt & BICR;
typedef BigInt & BIR;

struct Ascii2Int { int operator()(int c) {return c-'0';} };

struct CarryPos
{
    int & carry;

    CarryPos(int & c):carry(c){}

    int operator()(int n)
    {
        n+=carry; carry=n/10; n%=10;
        return n;
    }
};

struct CarryNeg
{
    int & carry;

    CarryNeg(int & c):carry(c){}

    int operator()(int n)
    {
        n-=carry; carry=0;
        while (n<0) {n+=10; carry++;}
        return n;
    }
};

struct NegMinus { int operator()(int a, int b) {return b-a;} };

BigInt::BigInt(string str)
{
    transform(str.rbegin(),str.rend(),back_inserter(digits),Ascii2Int());
}

BigInt BigInt::operator+(BICR bi) const
{
    const BigInt * max_op=this;
    const BigInt * min_op=&bi;

    if (max_op->digits.size()<min_op->digits.size())
        swap(max_op,min_op);

    BigInt result(*max_op);

    transform(min_op->digits.begin(),min_op->digits.end(),
        result.digits.begin(),result.digits.begin(),plus<int>());

    int carry=0;
    transform(result.digits.begin(),result.digits.end(),
        result.digits.begin(),CarryPos(carry));

    if (carry) result.digits.push_back(carry);

    return result;
}

BigInt BigInt::operator-(BICR bi) const
{
    BigInt result(*this);

    transform(bi.digits.begin(),bi.digits.end(),
        result.digits.begin(),result.digits.begin(),NegMinus());

    int carry=0;
    transform(result.digits.begin(),result.digits.end(),
        result.digits.begin(),CarryNeg(carry));

    return result;
}

BigInt BigInt::operator*(int n) const
{
    BigInt result(*this);

    transform(result.digits.begin(),result.digits.end(),
        result.digits.begin(),bind1st(multiplies<int>(),n));

    int carry=0;
    transform(result.digits.begin(),result.digits.end(),
        result.digits.begin(),CarryPos(carry));

    while (carry)
    {
        result.digits.push_back(carry%10);
        carry/=10;
    }

    return result;
}

BigInt BigInt::operator<<(int n) const
{
    BigInt result(*this);

    result.digits.resize(result.digits.size()+n);

    copy(result.digits.rbegin()+n, result.digits.rend(),result.digits.rbegin());
    fill(result.digits.begin(),result.digits.begin()+n,0);

    return result;
}

BigInt BigInt::operator*(BICR bi) const
{
    const BigInt * max_op=this;
    const BigInt * min_op=&bi;

    int max_size=max_op->digits.size();
    int min_size=min_op->digits.size();

    if (max_size<min_size)
    {
        swap(max_op,min_op);
        swap(max_size,min_size);
    }

    BigInt * array=new BigInt[min_size];

    for (int i=0; i<min_size; i++)
        array[i]=(*max_op)*(min_op->digits[i]);

    BigInt result(array[0]);

    for (int i=1; i<min_size; i++)
        result=result+(array[i]<<i);

    delete[] array;
    return result;
}

void split(BICR op1, BICR op2, BIR x0, BIR x1, BIR y0, BIR y1, int & m)
{
    int size1=op1.digits.size();
    int size2=op2.digits.size();

    int min_size=size1;
    if (min_size>size2) min_size=size2;

    m=min_size/2;

    x0.digits.resize(m);
    x1.digits.resize(size1-m);

    y0.digits.resize(m);
    y1.digits.resize(size2-m);

    copy(op1.digits.begin(),op1.digits.begin()+m,x0.digits.begin());
    copy(op1.digits.begin()+m,op1.digits.end(),x1.digits.begin());

    copy(op2.digits.begin(),op2.digits.begin()+m,y0.digits.begin());
    copy(op2.digits.begin()+m,op2.digits.end(),y1.digits.begin());
}

BigInt karatsuba(BICR op1, BICR op2)
{
    BigInt x0, x1, y0, y1;
    BigInt z0, z1, z2;

    if (op1.digits.size()<30 || op2.digits.size()<30)
        return op1*op2;

    int m;
    split(op1,op2,x0,x1,y0,y1,m);

    z0=karatsuba(x0,y0);
    z2=karatsuba(x1,y1);
    z1=(karatsuba(x0+x1,y0+y1)-z2)-z0;

    z1=z1<<m;
    z2=z2<<2*m;

    return z0+z1+z2;
}

ostream & operator<<(ostream & os, BICR bi)
{
    copy(bi.digits.rbegin(),bi.digits.rend(),ostream_iterator<int>(os));
    return os;
}

void test(string s1, string s2)
{
    BigInt n1(s1);
    BigInt n2(s2);
    BigInt rs, rk;

    int start_s, stop_s, start_k, stop_k;

    start_s=clock();
    rs=n1*n2;
    stop_s=clock();

    start_k=clock();
    rk=karatsuba(n1,n2);
    stop_k=clock();

    cout << rs << endl;
    cout << rk << endl;
    cout << "standard time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;
    cout << "karatsuba time: " << (stop_k-start_k)/double(CLOCKS_PER_SEC)*1000 << endl;
}

int main()
{
    test(
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789",

    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321");
    cout << "\nhit enter to continue..." << endl;
    cin.get();

    test(
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789",

    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321");
    cout << "\nhit enter to continue..." << endl;
    cin.get();

    test(
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789",

    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321");
    cout << "\nhit enter to continue..." << endl;
    cin.get();

    test(
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789",

    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321");
    cout << "\nhit enter to continue..." << endl;
    cin.get();

    test(
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
    "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789",

    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
    "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321");
    cout << "\nhit enter to continue..." << endl;
    cin.get();

    return 0;
}