using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        Trie trie = new Trie();

        trie.Insert("Nalan");

        trie.Insert("Naveeen");

        trie.Insert("Naveeen_Jun");

        trie.Insert("Naveeen Snr");

        trie.Insert("Narayan");

        trie.PrintAllChildren("Nav");

    }

    public class Trie {

​

    /** Initialize your data structure here. */

    public class TrieNode

    {

        public Dictionary<char, TrieNode> children;

        public bool endOfWord;

        public TrieNode()

        {

            children = new Dictionary<char, TrieNode>();

            endOfWord = false;

        }

    }

    public TrieNode root;

    public Trie() 

    {

        root = new TrieNode();

    }

    /** Inserts a word into the trie. */

    public void Insert(string word) 

    {

        TrieNode cur = root;        

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

        {

            if(!cur.children.ContainsKey(word[i]))

            {

                cur.children.Add(word[i], new TrieNode()); 

            }

            cur = cur.children[word[i]];

        }

        cur.endOfWord = true;

    }

    /** Returns if the word is in the trie. */

    public bool Search(string word) 

    {

        TrieNode cur = root;        

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

        {

            if(!cur.children.ContainsKey(word[i]))

            {

                return false;

            }

            cur = cur.children[word[i]];

        }

        return cur.endOfWord;        

    }

    /** Returns if there is any word in the trie that starts with the given prefix. */

    public bool StartsWith(string prefix) 

    {

        TrieNode cur = root;        

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

        {

            if(!cur.children.ContainsKey(prefix[i]))

            {

                return false;

            }

            cur = cur.children[prefix[i]];

        }

        return true;        

    }

    public void PrintAllChildren(string prefix)

    {

        TrieNode cur = root;

        foreach(char c in prefix)

        {

            if(cur.children.ContainsKey(c))

            {

                cur = cur.children[c];   

            }

            else

                return;            

        }

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

        Helper(prefix, result, cur);

        foreach(string s in result)

        {

            Console.WriteLine("{0}", s);

        }

    }

    private void Helper(string input, List<string> result, TrieNode cur)

    {

        if(cur == null) return;

        if(cur.endOfWord)

        {

            result.Add(input);            

        }

        foreach(KeyValuePair<char, TrieNode> pair in cur.children)

        {

            Helper(input + pair.Key, result, pair.Value);

        }

    }

}

}