#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct Node
{
  Node* children[8];
  int num;
  vector <pair <string, unsigned int> > words;
};

Node* create_node()
{
    Node* new_node = new Node;
    for (int i = 0; i < 8; i++)
        new_node->children[i] = NULL;
    new_node->num = 0;
    return new_node;
}

void add_node(Node* curr, int index)
{
    Node* new_node = create_node();
    curr->children[index] = new_node;
}

void walk (Node* curr)
{
    cout << "Node with key "<<  curr->num + 2 << ",words: ";   
    for (size_t i = 0; i < curr->words.size(); i++)
        cout << curr->words[i].first << "," << curr->words[i].second << " ";
    cout << endl;
    
    for (int i = 0; i < 8; i++)
        if (curr->children[i] != NULL)
           walk(curr->children[i]); 

}
int letter_to_int (char c)
{
    if ( ( c >= 97) && ( c <= 99))
       return 2;    
    else if ( ( c >= 100) && ( c <= 102))
       return 3;
    else if ( ( c >= 103) && ( c <= 105))
       return 4;
    else if ( ( c >= 106) && ( c <= 108))
       return 5;
    else if ( ( c >= 109) && ( c <= 111))
       return 6;
    else if ( ( c >= 112) && ( c <= 115))
       return 7;
    else if ( ( c >= 116) && ( c <= 118))
       return 8;
    else if ( ( c >= 119) && ( c <= 122))
       return 9;      
}


void tree_input(Node* root, string word, unsigned int freq)
{
     Node* curr = root;
     pair <string, unsigned int> tmp;
     int key;
     size_t n;  
     
     for (size_t i = 0; i < word.size(); i++)
     {
         key = letter_to_int(word[i]) - 2;    
         if (curr->children[key] == NULL)     
             add_node(curr, key);    
         curr = curr->children[key];
         curr->num = key;
     }    
   
     tmp.first = word;
     tmp.second = freq;     
     curr->words.push_back(tmp);     
     n = curr->words.size();
     key = 0;     
     if (n > 1)
     {
         for (size_t i = n - 2; i >= 0; i--)
             if (freq > curr->words[i].second)
                 key++;
             else
                 break;
         if (key)
         {
             curr->words.insert(curr->words.end() - key - 1, curr->words[n-1]);
             curr->words.erase(curr->words.end());
         }
     }
 
}

void find_word (Node* curr, string command, unsigned int fr_count)
{
     unsigned int num, freq;
     pair <string, unsigned int> tmp;
     string t;
     
     for (size_t i = 0; i < command.size(); i++)
     {
         num = (unsigned int)command[i] - 48;
         curr = curr->children[num - 2];
     }
     
     fr_count = fr_count % curr->words.size(); 
     
     cout << curr->words[fr_count].first; 
         
     if (curr->words[fr_count].second < 1000)     
          curr->words[fr_count].second++;
     
     freq = curr->words[fr_count].second;
     
     num = 0;
     
     for (size_t i = fr_count - 1; i >=0; i--)
             if (freq >= curr->words[i].second)
                 num++;
             else
                 break;
     
     if (num)
     {
         tmp = curr->words[fr_count];
         curr->words.erase(curr->words.begin() + fr_count);
         curr->words.insert(curr->words.begin() + fr_count - num, tmp);
     }   
}

int main(int argc, char *argv[])

{
    vector < pair<string, unsigned int> > vocabulary;
 
    pair <string, unsigned int> temp;
    Node* root = create_node(); 
    // Test input
    temp.first = "ad";
    temp.second = 2;
    vocabulary.push_back(temp);
    temp.first = "be";
    temp.second = 1;
    vocabulary.push_back(temp);
    temp.first = "not";
    temp.second = 10;
    vocabulary.push_back(temp);
    temp.first = "or";
    temp.second = 5;
    vocabulary.push_back(temp);
    temp.first = "to";
    temp.second = 50;
    vocabulary.push_back(temp);
    for (size_t i = 0; i < vocabulary.size(); i++)    
        tree_input(root, vocabulary[i].first, vocabulary[i].second);
        
    walk(root);    
    find_word(root, "86", 0);    
   
    return 0;
}