using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("10 x 10 = " +  M.Karatsuba("10", "10"));

        Console.WriteLine("321654987 x 987654321 = " +  M.Karatsuba("321654987", "987654321"));

        Console.WriteLine("987654987654 x 987654987654 = " +  M.Karatsuba("987654987654", "987654987654"));

    }

    class M

    {

        // this doesn't work!!

        static public string Karatsuba(string X, string Y)

        {

            int xl = X.Length;

            int yl = Y.Length;

            byte[] Xb = new byte[xl];

            for(int i = 0; i < xl; i++)

                Xb[xl-i-1] = (byte)Int32.Parse(X[i].ToString());

            //Console.WriteLine("X: "+X + " ["+string.Join(" ", Xb)+"]");

            byte[] Yb = new byte[yl];

            for(int i = 0; i < yl; i++)

                Yb[yl-i-1] = (byte)Int32.Parse(Y[i].ToString());

            //Console.WriteLine("X: "+X + " ["+string.Join(" ", Xb)+"]");

            string res = string.Join(" ", Karatsuba(Xb, Yb));

            return res.Replace(" ", "");

            //return string.Join(Karatsuba(Xb, Yb), ' ').Replace(" ", "");

        }

        static public byte[] Karatsuba(byte[] X, byte[] Y)

        {

            int N = Math.Max(X.Length, Y.Length);

            if (X.Length == 1) return Mul(Y, X[0]);

            if (Y.Length == 1) return Mul(X, Y[0]);

​

            int half = N / 2;

            byte[] xLow, xHigh, yLow, yHigh;

            Split(X, half, out xLow, out xHigh);

            Split(Y, half, out yLow, out yHigh);

​

            byte[] z0 = Karatsuba(xLow, yLow);

            byte[] z2 = Karatsuba(xHigh, yHigh);

            byte[] z1 = Karatsuba(Add(xLow, xHigh), Add(yLow, yHigh));

            z1 = Subtract(Subtract(z1, z0), z2);

            byte[] resultArray = Add(z0, Add(Shift(z1, half), Shift(z2, 2*half)));

            return Normalize(resultArray);

        }

​

        private static void Split(byte[] x, int half, out byte[] low, out byte[] high) {

            high = new byte[Math.Max(1, x.Length - half)];

            if (x.Length > half) Array.Copy(x, half, high, 0, high.Length);

            Array.Resize(ref x, Math.Min(half, x.Length));

            low = x;

        }

​

        private static byte[] Add(byte[] a, byte[] b) {

            int n = a.Length;

            int m = b.Length;

            int length = Math.Max(n, m);

            byte[] result = new byte[length + 1];

            byte carry = 0;

            for (int i = 0; i < length; i++) { // Wrong direction

                byte sum = (byte) ((i < n ? a[i] : 0) + (i < m ? b[i] : 0) + carry);

                result[i] = (byte) (sum % 10);

                carry = (byte) (sum / 10);

            }

            result[length] = carry;

            return Normalize(result);

        }

​

        private static byte[] Subtract(byte[] a, byte[] b) {

            int n = a.Length;

            int m = b.Length;

            byte[] result = new byte[n];

            int carry = 0;

            for (int i = 0; i < n; i++) {

                int sub = a[i] - (i < m ? b[i] : 0) - carry;

                if (sub < 0) {

                    sub += 10;

                    carry = 1;

                } else {

                    carry = 0;

                }

                result[i] = (byte)sub;

            }

            return Normalize(result);

        }

​

        private static byte[] Mul(byte[] a, byte b) {

            byte[] result = new byte[a.Length + 1];

            byte carry = 0;

​

            for (int i = 0; i < a.Length; i++) {

                byte product = (byte)(a[i] * b + carry);

                result[i] = (byte)(product % 10);

                carry = (byte)(product / 10);

            }

            result[a.Length] = carry;

            return Normalize(result);

        }

​

        private static byte[] Shift(byte[] a, int shift) {

            byte[] result = new byte[a.Length + shift];

            Array.Copy(a, 0, result, shift, a.Length);

            return result;

        }

​

        private static byte[] Normalize(byte[] a) {

            int n = a.Length - 1;

            if (a[n] > 0) return a; // No change needed

            while (n > 0 && a[n] == 0) {

                n--;

            }

            Array.Resize(ref a, n + 1);

            return a;

        }

​

    }

}