public class StreamChecker {

    public class Trie{
        Trie[] next = new Trie[26];
        bool end;
        
    }

    public Trie root;
    public List<int> query;
    public StreamChecker(string[] words) {
        // Initialize a query list.
        root = new Trie();
        query = new List<int>();
        
        // Loop on words array
        foreach(string s in words){
            char[] c = s.ToCharArray();
            Trie t = root;
            // add the word into trie but in reverse order
            for(int i = c.Length - 1; i >= 0; i--){
                if(t.next[c[i] - 'a'] == null) t.next[c[i] - 'a'] = new Trie();

                t = t.next[c[i]-'a'];
            }
            // mark the end of word
            t.end = true;
        }
            
    }
    
    public bool Query(char letter) {
        // Add the query character into list
        query.Add(letter - 'a');
        Trie t = root;
        // position = size of list - 1
        int i = query.Count - 1;
        

        // while(position >= 0)
        while(i >= 0){
        //  update temp = temp.next[query.Contains(position)]
            t = t.next[query.IndexOf(i)];
        //  if(temp != null and temp is endOfWord)
        //     return true
            if(t != null && t.end){
                return true;
            }
        //  else if (temp = null)
        //     return false
            else if (t == null){
                return false;
            }
        //  position--;
            i--;
        }
        // return false
        return false;
    }

    

}