class Solution {
  public:
  class TrieNode{
    public:
        vector<TrieNode*> v;
        int indices ;
        
        TrieNode(){
            v.resize(26,NULL);
            indices = -1;
        }
        ~TrieNode(){
            v.clear();
        }
    };
    void dfs(TrieNode* curr, vector<string>& ans,vector<string>& Dictionary){
        if(curr->indices != -1)
            ans.push_back(Dictionary[curr->indices]);
        for(int i = 0 ; i < 26; i++){
            if(curr->v[i] != NULL)
                dfs(curr->v[i], ans, Dictionary);
        }
    }
    void push(string word,TrieNode* root ){
        static int i =0;
        TrieNode* currRoot = root;
        for(char letter:word){
            if(letter >='a' && letter <='z')
                continue;
            letter = tolower(letter);
            if(currRoot->v[letter - 'a'] == NULL)
                currRoot->v[letter - 'a'] = new TrieNode();
            currRoot = currRoot->v[letter-'a'];
        }
        currRoot->indices = i++;
    }

    vector<string> CamelCase(int N, vector<string> Dictionary, string Pattern) {
        // code here
        TrieNode* root = NULL;
        root = new TrieNode();
        for(auto word : Dictionary){
            push(word, root);
        }
        TrieNode* curr = root;
        for(auto chr : Pattern){
            chr = tolower(chr);
            if(curr->v[chr-'a'] == NULL)
                return {"-1"};
            curr = curr->v[chr- 'a']; 
        }
        vector<string> ans;
        dfs(curr, ans,Dictionary);
        return ans;
    }
};