using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace ConsoleApplication1
{
    public interface IData
    {
        void Draw();
    }

    public class BinaryTreeNode : IData
    {
        public int Data;
        public BinaryTreeNode LeftChild;
        public BinaryTreeNode RightChild;

        public BinaryTreeNode(int data)
        {
            this.Data = data;
        }
        public BinaryTreeNode(int data, BinaryTreeNode leftChild, BinaryTreeNode rightChild)
        {
            this.Data = data;
            this.LeftChild = leftChild;
            this.RightChild = rightChild;            
        }

        public override string ToString()
        {
            return this.Data.ToString();
        }

        #region IData Members

        public void Draw()
        {
            int deepth = GetDeepth(this);
            string space = "    ";

            List<BinaryTreeNode> currentLevelNodes = new List<BinaryTreeNode>();
            List<BinaryTreeNode> nextLevelNodes = new List<BinaryTreeNode>();
            currentLevelNodes.Add(this);

            for (int i = deepth; i >= 1; i--)
            {
                for (int j = 1; j < deepth; i++)
                {
                    Console.Write(space);
                }
                foreach (BinaryTreeNode currentLevelNode in currentLevelNodes)
                {
                    Console.Write(currentLevelNode.Data.ToString());
                }
            }
        }

        private static int GetDeepth(BinaryTreeNode node)
        {
            if (node == null)
            {
                return 0;
            }

            int lDeepth = GetDeepth(node.LeftChild);
            int rDeepth = GetDeepth(node.RightChild);

            return lDeepth > rDeepth ? lDeepth + 1 : rDeepth + 1;
        }

        #endregion
    }

    public class LinkTableNode : IData
    {
        public int Data;
        public LinkTableNode Next;

        public LinkTableNode(int data, LinkTableNode next)
        {
            this.Data = data;
            this.Next = next;
        }

        public LinkTableNode Copy()
        {
            LinkTableNode node = new LinkTableNode(this.Data, this.Next);
            return node;
        }

        #region IData Members

        public void Draw()
        {
            LinkTableNode node = this;
            Console.Write(node.Data.ToString());

            int i = 0;
            while (node.Next != null)
            {
                i++;
                node = node.Next;
                Console.Write("-->");
                Console.Write(node.Data.ToString());
            }

            Console.WriteLine();
        }

        #endregion
    }

    public class DataProvider
    {
        public static BinaryTreeNode CreateRandomBinaryTree(int expectedNodeCount)
        {
            if (expectedNodeCount <= 0)
            {
                return null;
            }

            List<BinaryTreeNode> currentLevelNodes = new List<BinaryTreeNode>();
            List<BinaryTreeNode> nextLevelNodes = new List<BinaryTreeNode>();

            int currentNodeCount = 0;

            BinaryTreeNode rootNode = new BinaryTreeNode(GetRandomInt());
            currentLevelNodes.Add(rootNode);
            currentNodeCount++;

            while (currentNodeCount < expectedNodeCount)
            {
                foreach (BinaryTreeNode currentLevelNode in currentLevelNodes)
                {
                    bool hasLeftChild = GetRandomBool();
                    bool hasRightChild = GetRandomBool();

                    if (hasLeftChild)
                    {
                        BinaryTreeNode node = new BinaryTreeNode(GetRandomInt());
                        currentLevelNode.LeftChild = node;

                        nextLevelNodes.Add(node);

                        currentNodeCount++;
                    }

                    if (currentNodeCount >= expectedNodeCount)
                    {
                        break;
                    }

                    if (hasRightChild)
                    {
                        BinaryTreeNode node = new BinaryTreeNode(GetRandomInt());
                        currentLevelNode.RightChild = node;

                        nextLevelNodes.Add(node);

                        currentNodeCount++;
                    }

                    if (currentNodeCount >= expectedNodeCount)
                    {
                        break;
                    }
                }

                if (nextLevelNodes.Count > 0)
                {
                    currentLevelNodes.Clear();
                    currentLevelNodes.AddRange(nextLevelNodes);
                    nextLevelNodes.Clear();
                }
            }

            return rootNode;
        }
        public static BinaryTreeNode CreateStaticBinaryTree()
        {
            BinaryTreeNode rootNode56 = new BinaryTreeNode(56);
            BinaryTreeNode rootNode14 = new BinaryTreeNode(14);
            BinaryTreeNode rootNode16 = new BinaryTreeNode(16);
            BinaryTreeNode rootNode95 = new BinaryTreeNode(95);
            BinaryTreeNode rootNode23 = new BinaryTreeNode(23);
            BinaryTreeNode rootNode4 = new BinaryTreeNode(4);
            BinaryTreeNode rootNode51 = new BinaryTreeNode(51);
            BinaryTreeNode rootNode34 = new BinaryTreeNode(34);
            BinaryTreeNode rootNode69 = new BinaryTreeNode(69);
            BinaryTreeNode rootNode98 = new BinaryTreeNode(98);
            
            rootNode98.LeftChild = rootNode34;
            rootNode98.RightChild = rootNode69;
            rootNode34.LeftChild = rootNode23;
            rootNode34.RightChild = rootNode4;
            rootNode69.LeftChild = rootNode51;
            rootNode23.LeftChild = rootNode56;
            rootNode23.RightChild = rootNode14;
            rootNode4.LeftChild = rootNode16;
            rootNode4.RightChild = rootNode95;

            return rootNode98;
        }
        public static BinaryTreeNode CreateSortedBinaryTree()
        {
            BinaryTreeNode rootNode56 = new BinaryTreeNode(56);
            BinaryTreeNode rootNode14 = new BinaryTreeNode(14);
            BinaryTreeNode rootNode16 = new BinaryTreeNode(16);
            BinaryTreeNode rootNode95 = new BinaryTreeNode(95);
            BinaryTreeNode rootNode23 = new BinaryTreeNode(23);
            BinaryTreeNode rootNode4 = new BinaryTreeNode(4);
            BinaryTreeNode rootNode51 = new BinaryTreeNode(51);
            BinaryTreeNode rootNode34 = new BinaryTreeNode(34);
            BinaryTreeNode rootNode69 = new BinaryTreeNode(69);
            BinaryTreeNode rootNode98 = new BinaryTreeNode(98);

            rootNode56.LeftChild = rootNode23;
            rootNode56.RightChild = rootNode69;
            rootNode23.LeftChild = rootNode14;
            rootNode23.RightChild = rootNode34;
            rootNode34.RightChild = rootNode51;
            rootNode14.LeftChild = rootNode4;
            rootNode14.RightChild = rootNode16;
            rootNode69.RightChild = rootNode95;
            rootNode95.RightChild = rootNode98;

            return rootNode56;
        }
        
        public static LinkTableNode CreateStaticLinkTable()
        {
            //LinkTableNode tail = new LinkTableNode(67, null);
            //LinkTableNode node9 = new LinkTableNode(56, tail);
            //LinkTableNode node8 = new LinkTableNode(2, node9);
            //LinkTableNode node7 = new LinkTableNode(76, node8);
            //LinkTableNode node6 = new LinkTableNode(25, node7);
            //LinkTableNode node5 = new LinkTableNode(73, node6);
            //LinkTableNode node4 = new LinkTableNode(123, node5);
            //LinkTableNode node3 = new LinkTableNode(77, node4);
            //LinkTableNode node2 = new LinkTableNode(53, node3);
            //LinkTableNode node1 = new LinkTableNode(46, node2);
            //LinkTableNode head = new LinkTableNode(0, node1);
            LinkTableNode tail = new LinkTableNode(82, null);
            LinkTableNode node9 = new LinkTableNode(59, tail);
            LinkTableNode node8 = new LinkTableNode(81, node9);
            LinkTableNode node7 = new LinkTableNode(23, node8);
            LinkTableNode node6 = new LinkTableNode(43, node7);
            LinkTableNode node5 = new LinkTableNode(34, node6);
            LinkTableNode node4 = new LinkTableNode(55, node5);
            LinkTableNode node3 = new LinkTableNode(42, node4);
            LinkTableNode node2 = new LinkTableNode(6, node3);
            LinkTableNode head = new LinkTableNode(89, node2);

            return head;
        }
        public static LinkTableNode CreateStaticSortedLinkTable()
        {
            LinkTableNode tail = new LinkTableNode(67, null);
            LinkTableNode node9 = new LinkTableNode(56, tail);
            LinkTableNode node8 = new LinkTableNode(54, node9);
            LinkTableNode node7 = new LinkTableNode(24, node8);
            LinkTableNode node6 = new LinkTableNode(21, node7);
            LinkTableNode head = new LinkTableNode(7, node6);

            return head;
        }
        public static LinkTableNode CreateRandomLinkTable(int expectedNodeCount)
        {
            if (expectedNodeCount == 0)
            {
                return null;
            }

            LinkTableNode head = new LinkTableNode(GetRandomInt(), null);
            LinkTableNode previousNode = head;
            for (int i = 2; i <= expectedNodeCount; i++)
            {
                LinkTableNode node = new LinkTableNode(GetRandomInt(), null);
                previousNode.Next = node;
                previousNode = node;
            }

            return head;
        }

        private static Random R = new Random();
        private static int GetRandomInt()
        {
            return R.Next(1, 100);
        }
        private static bool GetRandomBool()
        {
            int i = GetRandomInt();
            if (i <= 75)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }

    public class Algorithm
    {
        #region Binary Tree
        public static BinaryTreeNode GetSameParent(BinaryTreeNode root, BinaryTreeNode node1, BinaryTreeNode node2)
        {
            return GetSameParent(root, node1.Data, node2.Data);
        }
        public static BinaryTreeNode GetSameParent(BinaryTreeNode root, int node1, int node2)
        {
            if (root == null)
            {
                return null;
            }

            BinaryTreeNode sameNode = null;

            if (IsInTree(root, node1) && IsInTree(root, node2))
            {
                sameNode = root;
            }

            if (GetSameParent(root.LeftChild, node1, node2) != null)
            {
                sameNode = GetSameParent(root.LeftChild, node1, node2);
            }
            if (GetSameParent(root.RightChild, node1, node2) != null)
            {
                sameNode = GetSameParent(root.RightChild, node1, node2);
            }

            return sameNode;
        }
        private static bool IsInTree(BinaryTreeNode root, BinaryTreeNode node)
        {
            return IsInTree(root, node.Data);
        }
        private static bool IsInTree(BinaryTreeNode root, int nodeData)
        {
            if (root == null)
            {
                return false;
            }
            else
            {
                if (nodeData == root.Data)
                {
                    return true;
                }
                bool lb = IsInTree(root.LeftChild, nodeData);
                bool rb = IsInTree(root.RightChild, nodeData);

                return lb || rb;
            }
        }

        public static BinaryTreeNode InsertNode(BinaryTreeNode root, int value)
        {
            BinaryTreeNode insertNode = new BinaryTreeNode(value);
            if (root == null)
            {
                return insertNode;
            }            

            BinaryTreeNode parentNode = GetInsertPosition(root, value);
            if (parentNode.Data > value)
            {
                parentNode.LeftChild = insertNode;
            }
            else
            {
                parentNode.RightChild = insertNode;
            }

            return root;
        }
        private static BinaryTreeNode GetInsertPosition(BinaryTreeNode root, int value)
        {
            if (root.Data == value)
            {
                throw new Exception("Can't insert duplicate node");
            }

            if ((root.Data < value && root.RightChild == null) ||
                (root.Data > value && root.LeftChild == null))
            {
                return root;
            }
            else
            {
                if (root.Data < value)
                {
                    return GetInsertPosition(root.RightChild, value);
                }
                else
                {
                    return GetInsertPosition(root.LeftChild, value);
                }
            }
        }

        public static void PrintBinaryTreeByLevel(BinaryTreeNode root)
        {
            if (root == null)
            {
                Console.Write("Empty Tree");
                return;
            }

            List<BinaryTreeNode> nodes = new List<BinaryTreeNode>();
            nodes.Add(root);
            PrintBinaryTreeNodes(nodes);
        }
        private static void PrintBinaryTreeNodes(List<BinaryTreeNode> nodes)
        {
            if (nodes.Count == 0)
            {
                return;
            }

            List<BinaryTreeNode> nextLevelNodes = new List<BinaryTreeNode>();
            foreach (BinaryTreeNode node in nodes)
            {
                Console.Write(node.Data.ToString() + "   ");
                if (node.LeftChild != null)
                {
                    nextLevelNodes.Add(node.LeftChild);
                }
                if (node.RightChild != null)
                {
                    nextLevelNodes.Add(node.RightChild);
                }
            }
            Console.WriteLine("");

            PrintBinaryTreeNodes(nextLevelNodes);
        }

        public static List<BinaryTreeNode> GetPath(BinaryTreeNode root, int value)
        {
            if (root == null)
            {
                return null;
            }

            Stack<SearchedBinaryTreeNode> stack = new Stack<SearchedBinaryTreeNode>();
            stack.Push(new SearchedBinaryTreeNode { Node = root });

            //stack = GetPath(value, stack);
            stack = GetPathNoRecursion(value, stack);

            if (stack == null || stack.Count == 0)
            {
                return null;
            }

            List<BinaryTreeNode> result = new List<BinaryTreeNode>();

            while (stack.Count > 0)
            {
                result.Add(stack.Pop().Node);
            }

            for (int i = 0; i < result.Count / 2; i++)
            {
                BinaryTreeNode tmp = result[i];
                result[i] = result[result.Count - 1 - i];
                result[result.Count - 1 - i] = tmp;
            }

            return result;
        }

        private static Stack<SearchedBinaryTreeNode> GetPath(int value, Stack<SearchedBinaryTreeNode> stack)
        {
            if (stack.Count == 0)
            {
                return null;
            }

            SearchedBinaryTreeNode currNode = stack.Pop();
            if (currNode.Node.Data == value)
            {
                stack.Push(currNode);
                return stack;
            }
            else
            {              
                if (currNode.Node.LeftChild != null && !currNode.SearchedLeft)
                {
                    currNode.SearchedLeft = true;
                    stack.Push(currNode);

                    SearchedBinaryTreeNode node = new SearchedBinaryTreeNode();
                    node.Node = currNode.Node.LeftChild;
                    stack.Push(node);

                    return GetPath(value, stack);
                }
                else if (currNode.Node.RightChild != null && !currNode.SearchedRight)
                {
                    currNode.SearchedRight = true;
                    stack.Push(currNode);

                    SearchedBinaryTreeNode node = new SearchedBinaryTreeNode();
                    node.Node = currNode.Node.RightChild;
                    stack.Push(node);

                    return GetPath(value, stack);
                }
                else
                {
                    return GetPath(value, stack);
                }
            }
        }
        private static Stack<SearchedBinaryTreeNode> GetPathNoRecursion(int value, Stack<SearchedBinaryTreeNode> stack)
        {
            if (stack.Count == 0)
            {
                return null;
            }

            while (stack.Count > 0)
            {
                SearchedBinaryTreeNode currNode = stack.Pop();
                if (currNode.Node.Data == value)
                {
                    stack.Push(currNode);
                    return stack;
                }
                else
                {
                    if (currNode.Node.LeftChild != null && !currNode.SearchedLeft)
                    {
                        currNode.SearchedLeft = true;
                        stack.Push(currNode);

                        SearchedBinaryTreeNode node = new SearchedBinaryTreeNode();
                        node.Node = currNode.Node.LeftChild;
                        stack.Push(node);

                        continue;
                    }
                    else if (currNode.Node.RightChild != null && !currNode.SearchedRight)
                    {
                        currNode.SearchedRight = true;
                        stack.Push(currNode);

                        SearchedBinaryTreeNode node = new SearchedBinaryTreeNode();
                        node.Node = currNode.Node.RightChild;
                        stack.Push(node);

                        continue;
                    }
                    else
                    {
                        continue;
                    }
                }
            }

            if (stack.Count > 0)
            {
                return stack;
            }
            else
            {
                return null;
            }
        }
        private class SearchedBinaryTreeNode
        {
            internal BinaryTreeNode Node;
            internal bool SearchedLeft = false;
            internal bool SearchedRight = false;
        }
        #endregion

        #region String
        public static bool IsMatch(string source, string dest)
        {
            if (string.IsNullOrEmpty(source) || string.IsNullOrEmpty(dest) || source.Length < dest.Length)
            {
                return false;
            }

            bool match = false;

            for (int i = 0; i <= source.Length - dest.Length; i++)
            {
                if (source.Substring(i, dest.Length) == dest)
                {
                    match = true;
                }
            }

            return match;
        }
        public static bool IsMatch2(string source, string dest)
        {
            if (string.IsNullOrEmpty(source) || string.IsNullOrEmpty(dest) || source.Length < dest.Length)
            {
                return false;
            }

            bool match = false;

            int i = 0;
            int j = 0;

            while (j < dest.Length && i <= source.Length - dest.Length)
            {
                if (source.Substring(i + j, 1) == dest.Substring(j, 1))
                {
                    j++;
                }
                else
                {
                    i++;
                    j = 0;
                }
            }

            if (j == dest.Length)
            {
                match = true;
            }

            return match;
        }

        public static int[] BuildT(string pattern)
        {
            int[] array = new int[pattern.Length];
            int i = 0, s = pattern.Length;
            if (s > 1)
                array[0] = 0;
            for (i = 1; i < s; i++)
            {
                if (pattern[i] == pattern[array[i - 1]])
                    array[i] = array[i - 1] + 1;
                else
                    array[i] = 0;
            }

            return array;
        }

        public static int Match(string target, string pattern, int start)
        {
            int[] array = BuildT(pattern);

            int target_index = start;
            int pattern_index = 0;
            int target_length = target.Length;
            int pattern_length = pattern.Length;

            while (target_index < target_length && pattern_index < pattern_length)
            {
                if (target[target_index] == pattern[pattern_index])
                {
                    target_index++;
                    pattern_index++;
                }
                else
                {
                    if (pattern_index == 0)
                        target_index++;
                    else
                        pattern_index = array[pattern_index - 1];
                }
            }

            if (pattern_index == pattern_length)
                return target_index - pattern_length;
            return -1;
        }

        public static long ConvertToLong(string s)
        {
            char[] cs = s.ToCharArray();
            long n = 0;
            long j = 1;
            for (int i = cs.Length - 1; i >= 0; i--)
            {
                n += (((int)cs[i]) - (int)'0') * j;
                j = j * 10;
            }
            return n;
        }

        public static List<string> GetAllArrange(string s, int i)
        {
            List<string> result = new List<string>();
            if (i == s.Length - 1)
            {
                result.Add(s);
            }
            else
            {
                char[] cs = s.ToCharArray();
                for (int j = i; j < cs.Length; j++)
                {
                    if (j != i)
                    {
                        char tmp = cs[i];
                        cs[i] = cs[j];
                        cs[j] = tmp;
                    }
                    s = GetString(cs);

                    result.AddRange(GetAllArrange(s, i + 1));
                }
            }
      
            return result;
        }
        public static List<string> GetAllArrange(string s)
        {
            List<string> result = new List<string>();
            if (s == null)
            {
                return result;
            }
            if (s == "" || s.Length == 1)
            {
                result.Add(s);
                return result;
            }

            string left = s.Substring(0, 1);
            string right = s.Substring(1);

            List<string> tmpResult = GetAllArrange(right);
            foreach (string tmp in tmpResult)
            {
                string r = left + tmp;
                result.Add(r);
                for (int i = 0; i < tmp.Length; i++)
                {
                    r = tmp.Substring(0, i + 1) + left + tmp.Substring(i + 1);
                    result.Add(r);
                }
            }

            return result;
        }
        private static string GetString(char[] cs)
        {
            if (cs == null || cs.Length == 0)
            {
                return "";
            }
            string s = "";
            for (int i = 0; i < cs.Length; i++)
            {
                s += cs[i].ToString();
            }
            return s;
        }

        public static string MergeStrings(string s1, string s2)
        {
            if (string.IsNullOrEmpty(s1))
            {
                return s2;
            }
            if (string.IsNullOrEmpty(s2))
            {
                return s1;
            }

            int duplicateLength = s2.Length;
            if (s2.Length > s1.Length)
            {
                duplicateLength = s1.Length;
            }

            while (duplicateLength > 0)
            {
                if (s2.Substring(0, duplicateLength) == s1.Substring(s1.Length - duplicateLength))
                {
                    break;
                }
                else
                {
                    duplicateLength--;
                }
            }

            if (duplicateLength > 0)
            {
                return s1 + s2.Substring(duplicateLength);
            }
            else
            {
                return s1;
            }
        }
        #endregion

        #region Linked Table
        public static LinkTableNode ReverseLinkedTable(LinkTableNode head)
        {
            if (head == null)
            {
                return null;
            }

            LinkTableNode curr = head;
            LinkTableNode prev = null;
            LinkTableNode next = null;

            while (curr != null)
            {
                next = curr.Next;
                curr.Next = prev;
                prev = curr;
                curr = next;
            }

            return prev;
        }
        public static LinkTableNode ReverseLinkedTableByRecursion(LinkTableNode head)
        {
            if (head == null || head.Next == null)
            {
                return head;
            }

            LinkTableNode result = ReverseLinkedTableByRecursion(head.Next);
            head.Next = null;

            LinkTableNode tmp = result;
            while (tmp.Next != null)
            {
                tmp = tmp.Next;
            }
            tmp.Next = head;

            return result;
        }

        public static LinkTableNode InsertSort(LinkTableNode head)
        {
            if (head == null || head.Next == null)
            {
                return head;
            }

            LinkTableNode resultHead = head.Copy();
            resultHead.Next = null;
            LinkTableNode currentNode = head.Next;

            while (currentNode != null)
            {
                LinkTableNode tmp = currentNode.Next;
                currentNode.Next = null;
                resultHead = Insert(resultHead, currentNode);
                currentNode = tmp;
            }

            return resultHead;
        }
        public static LinkTableNode InsertSort2(LinkTableNode head)
        {
            if (head == null || head.Next == null)
            {
                return head;
            }

            LinkTableNode resultHead = null;
            LinkTableNode resultTail = null;

            resultHead = head;
            resultTail = head;
            head = head.Next;
            resultHead.Next = null;
            resultTail.Next = null;

            while (head != null)
            {
                if (head.Data >= resultTail.Data)
                {
                    LinkTableNode tmp = head.Next;
                    resultTail.Next = head;
                    resultTail = head;
                    head.Next = null;
                    head = tmp;
                }
                else
                {
                    if (resultHead.Data >= head.Data)
                    {
                        LinkTableNode tmp = head.Next;
                        head.Next = resultHead;
                        resultHead = head;
                        head = tmp;
                    }
                    else
                    {
                        LinkTableNode prev = resultHead;
                        LinkTableNode curr = resultHead.Next;
                        while (curr != null)
                        {
                            if (curr.Data >= head.Data)
                            {
                                LinkTableNode tmp = head.Next;
                                prev.Next = head;
                                head.Next = curr;
                                head = tmp;
                                break;
                            }
                            else
                            {
                                prev = curr;
                                curr = curr.Next;
                            }
                        }
                    }
                }
            }

            return resultHead;
        }
        public static LinkTableNode Insert(LinkTableNode head, LinkTableNode node)
        {
            if (head == null)
            {
                return node;
            }
            if (head.Next == null)
            {
                if (head.Data >= node.Data)
                {
                    node.Next = head;
                    return node;
                }
                else
                {
                    head.Next = node;
                    return head;
                }
            }

            LinkTableNode prev = null;
            LinkTableNode curr = head;
            if (IsMaxamumToMinumam(head))
            {
                while (curr != null)
                {
                    if (curr.Data <= node.Data)
                    {
                        node.Next = curr;
                        if (prev == null)
                        {
                            head = node;
                        }
                        else
                        {
                            prev.Next = node;
                        }
                        break;
                    }
                    else
                    {
                        prev = curr;
                        if (curr.Next == null)
                        {
                            curr.Next = node;
                            break;
                        }
                        curr = curr.Next;
                    }
                }
            }
            else
            {
                while (curr != null)
                {
                    if (curr.Data >= node.Data)
                    {
                        node.Next = curr;
                        if (prev == null)
                        {
                            head = node;
                        }
                        else
                        {
                            prev.Next = node;
                        }
                        break;
                    }
                    else
                    {
                        prev = curr;
                        if (curr.Next == null)
                        {
                            curr.Next = node;
                            break;
                        }
                        curr = curr.Next;
                    }
                }
            }

            return head;
        }
        public static bool IsMaxamumToMinumam(LinkTableNode head)
        {
            if (head == null || head.Next == null)
            {
                return true;
            }
            else
            {
                while (head.Next != null)
                {
                    if (head.Data - head.Next.Data < 0)
                    {
                        return false;
                    }
                    else if (head.Data - head.Next.Data > 0)
                    {
                        return true;
                    }
                    else
                    {
                        head = head.Next;
                    }
                }

                return true;
            }
        }

        public static LinkTableNode SortLinkedTable(LinkTableNode head)
        {
            if (head == null || head.Next == null)
            {
                return head;
            }

            LinkTableNode first = head;
            LinkTableNode second = head;

            while (second.Next != null && second.Next.Next != null)
            {
                first = first.Next;
                second = second.Next.Next;
            }

            second = first.Next;
            first.Next = null;
            first = head;

            return MergeSort(SortLinkedTable(first), SortLinkedTable(second));
        }
        private static LinkTableNode MergeSort(LinkTableNode first, LinkTableNode second)
        {
            LinkTableNode result = new LinkTableNode(-1, null);
            LinkTableNode current = result;

            while (first != null && second != null)
            {
                if (first.Data <= second.Data)
                {
                    current.Next = second;
                    second = second.Next;
                    current = current.Next;
                }
                else
                {
                    current.Next = first;
                    first = first.Next;
                    current = current.Next;
                }
            }

            if (first != null)
            {
                current.Next = first;
            }

            if (second != null)
            {
                current.Next = second;
            }

            return result.Next;
        }
        #endregion        

        #region Integer
        public static int Fibonacci(int n, Dictionary<int, int> cache)
        {
            if (n < 0)
            {
                throw new Exception();
            }

            if (n == 0)
            {
                return 0;
            }

            if (n == 1)
            {
                return 1;
            }

            if (cache == null)
            {
                cache = new Dictionary<int, int>();
            }

            if (!cache.Keys.Contains(n))
            {
                cache.Add(n, Fibonacci(n - 1, cache) + Fibonacci(n - 2, cache));
            }

            return cache[n];
        }

        public static int GetMaxCommonDivisior(int n1, int n2)
        {
            if (n1 == 0 && n2 == 0)
            {
                throw new ArgumentException();
            }
            if (n1 * n2 == 0)
            {
                return n1 == 0 ? n2 : n1;
            }

            if (n1 < 0)
            {
                n1 = 0 - n1;
            }
            if (n2 < 0)
            {
                n2 = 0 - n2;
            }

            while (n1 != n2)
            {
                if (n1 > n2)
                {
                    n1 -= n2;
                }
                else
                {
                    n2 -= n1;
                }
            }

            return n1;
        }
        public static int GetMaxCommonDivisionRecursion(int n1, int n2)
        {
            if (n1 == 0 && n2 == 0)
            {
                throw new ArgumentException();
            }
            if (n1 * n2 == 0)
            {
                return n1 == 0 ? n2 : n1;
            }

            if (n1 > n2)
            {
                return GetMaxCommonDivisionRecursion(n1 - n2, n2);
            }
            else if (n2 > n1)
            {
                return GetMaxCommonDivisionRecursion(n1, n2 - n1);
            }
            else
            {
                return n1;
            }
        }
        public static int GetMaxCommonDivisior2(int n1, int n2)
        {
            if (n1 == 0 && n2 == 0)
            {
                throw new ArgumentException();
            }
            if (n1 * n2 == 0)
            {
                return n1 == 0 ? n2 : n1;
            }

            if (n1 < 0)
            {
                n1 = 0 - n1;
            }
            if (n2 < 0)
            {
                n2 = 0 - n2;
            }

            if (n1 < n2)
            {
                n1 = n2 + n1;
                n2 = n1 - n2;
                n1 = n1 - n2;
            }

            while (n1 % n2 != 0)
            {
                n1 -= n2;

                if (n1 < n2)
                {
                    n1 = n2 + n1;
                    n2 = n1 - n2;
                    n1 = n1 - n2;
                }
            }

            return n2;
        }
        #endregion

        #region Array
        public static void DrawSymmetricalIntArray(int size)
        {
            if (size <= 0)
            {
                return;
            }

            int[,] result = new int[size, size];
            int middle = size % 2 == 0 ? size / 2 : size / 2 + 1;

            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    if (i < middle)
                    {
                        if (j < middle)
                        {
                            result[i, j] = i <= j ? i + 1 : j + 1;
                        }
                        else
                        {
                            result[i, j] = result[i, size - j - 1];
                        }
                    }
                    else
                    {
                        if (j < middle)
                        {
                            result[i, j] = result[size - i -1, j];
                        }
                        else
                        {
                            result[i, j] = result[size - i - 1, size - j - 1];
                        }
                    }
                }
            }

            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    Console.Write(result[i, j].ToString() + " ");
                }
                Console.WriteLine();
            }
        }
        #endregion
    }
}

C:\Users\Administrator\Desktop\WSDLs>SvcUtil.exe "TransactionWebService - Copy.wsdl"
Microsoft (R) Service Model Metadata Tool
[Microsoft (R) Windows (R) Communication Foundation, Version 3.0.4506.2152]
Copyright (c) Microsoft Corporation.  All rights reserved.

Error: Cannot import wsdl:portType
Detail: An exception was thrown while running a WSDL import extension: System.ServiceModel.Description.DataContractSerializerMessageContractImporter
Error: Schema with target namespace 'urn:schemas.microsoft.com/CommercePlatform/Services/Transaction
Service/2010/01' could not be found.
XPath to Error Source: //wsdl:definitions[@targetNamespace='urn:schemas.microsoft.com/CommercePlatform/Services/TransactionService/2010/01']/wsdl:portType[@name='TransactionService']


Error: Cannot import wsdl:binding
Detail: There was an error importing a wsdl:portType that the wsdl:binding is dependent on.
XPath to wsdl:portType: //wsdl:definitions[@targetNamespace='urn:schemas.microsoft.com/CommercePlatform/Services/TransactionService/2010/01']/wsdl:portType[@name='TransactionService']
XPath to Error Source: //wsdl:definitions[@targetNamespace='urn:schemas.microsoft.com/CommercePlatfo
rm/Services/TransactionService/2010/01']/wsdl:binding[@name='TransactionServiceEndPoint']


Error: Cannot import wsdl:port
Detail: There was an error importing a wsdl:binding that the wsdl:port is dependent on.
XPath to wsdl:binding: //wsdl:definitions[@targetNamespace='urn:schemas.microsoft.com/CommercePlatform/Services/TransactionService/2010/01']/wsdl:binding[@name='TransactionServiceEndPoint']
XPath to Error Source: //wsdl:definitions[@targetNamespace='urn:schemas.microsoft.com/CommercePlatfo
rm/Services/TransactionService/2010/01']/wsdl:service[@name='TransactionService']/wsdl:port[@name='T
ransactionServiceEndPoint']


Generating files...
Warning: No code was generated.
If you were trying to generate a client, this could be because the metadata documents did not contain any valid contracts or services
or because all contracts/services were discovered to exist in /reference assemblies. Verify that you passed all the metadata documents to the tool.

Warning: If you would like to generate data contracts from schemas make sure to use the /dataContrac
tOnly option.