using System;

using System.Collections.Generic;

using System.Linq;

​

public class Program

{

    public static void Main()

    {

        string[] arr=new string[] {"baa", "abcd", "abca", "cab", "cad"};

        AlienAlphaOrderQueue(arr);

    }

    public static void AlienAlphaOrderQueue(string[] arr)

        {

            Queue<char> previous = new Queue<char>();

            Queue<char> current = new Queue<char>();

            Dictionary<char, int> results = new Dictionary<char, int>();

​

            results.Add(arr[0][0], 1);

            char prev = new char();

            char curr = new char();

            int max = 1;

            bool isGreater = false;

            int temp = 0;

​

            foreach (var ch in arr[0].ToCharArray())

            {

                previous.Enqueue(ch);

                if (!results.ContainsKey(ch))

                {

                    max++;

                    results.Add(ch, max);

                }

            }

​

            for (int i = 1; i < arr.Length; i++)

            {

                prev = new char();

                curr = new char();

                temp = 0;

​

                for (int j = 0; j < arr[i].Length; j++)

                {

                    if (previous.Count > 0)

                        prev = previous.Dequeue();

​

                    current.Enqueue(arr[i][j]);

                    curr = arr[i][j];

​

                    if (!isGreater)

                    {

                        if (!results.ContainsKey(arr[i][j]))

                        {

                            max++;

                            results.Add(arr[i][j], max);

                        }

                        else

                        {

                            if (results[curr] < results[prev])

                            {

                                if (results[curr] > 1 && results[prev] > 1)

                                {

                                    temp = results[prev];

                                    results[prev] = results[curr];

                                    results[curr] = temp;

                                }

                            }

                            else

                            {

                                if (!results.ContainsKey(arr[i][j]))

                                {

                                    max++;

                                    results.Add(arr[i][j], max);

                                }

​

                                if(results[curr] != results[prev])

                                    isGreater = true;

                            }                            

                        }

​

                    }

​

                    if (!results.ContainsKey(arr[i][j]))

                    {

                        max++;

                        results.Add(arr[i][j], max);

                    }

                    prev = new char();

                    curr = new char();

                    temp = 0;

                }

​

                previous = current;

                isGreater = false;

                current = new Queue<char>();

            }

​

            var output = from item in results orderby item.Value ascending select item;

​

            foreach (KeyValuePair<char,int> key in output)

                Console.WriteLine(key.ToString());

        }

}