#include<bits/stdc++.h>
using namespace std;
//Data stored in the node type

struct WordCount
{

    string word;

    int count;
};

//Node type:

struct TreeNode
{

    WordCount info;

    TreeNode * left;

    TreeNode * right;

};

// Two function's prototype

// Increments the frequency count if the string is in the tree

// or inserts the string if it is not there.

void Insert(TreeNode*&rt, string tmp)
{
    if(!rt)
    {
        rt = new TreeNode;
        rt->info.word = tmp;
        rt->info.count = 1;
        rt->left = rt->right = NULL;
        return ;
    }
    else if(tmp==rt->info.word)
    {
        rt->info.count++;
    }
    else if(tmp<rt->info.word)
    {
        Insert(rt->left,tmp);
    }
    else
    {
        Insert(rt->right,tmp);
    }

}


// Prints the words in the tree and their frequency counts.

void PrintTree(TreeNode* rt, ofstream& outfile)
{

    if(rt!=NULL)
    {
       // cout<<rt->info.word<<" "<<rt->info.count<<endl;
        outfile<<rt->info.word<<" "<<rt->info.count<<endl;


        PrintTree(rt->left,outfile);
        PrintTree(rt->right,outfile);
    }

}

//Start your main function and the definitions of above two functions.
int main()
{
    ifstream infile;
    ofstream outfile;
    string in_name,out_name;
    cout<<"please input the name of infile"<<endl;
    cin>>in_name;
    infile.open(in_name.c_str());
    string tmp;
    TreeNode * root  = NULL;
    while(infile>>tmp)
    {
        if(tmp=="")continue;
        // cout<<tmp<<endl;
        int len = tmp.size();
        if(len<3)continue;
        if(tmp[len-1]>='a'&&tmp[len-1]<='z')
        {
            Insert(root,tmp);
        }
        else if(tmp[len-1]>='A'&&tmp[len-1]<='Z')
        {
            Insert(root,tmp);
        }
        else if(tmp[len-1]>='0'&&tmp[len-1]<='9')
        {
            Insert(root,tmp);
        }
        else
        {
            string hh = "";
            for(int i=0; i<len-1; i++)
            {
                hh+=tmp[i];
            }
            Insert(root,hh);

        }
    }
    infile.close();
    cout<<"please input the name of outfile"<<endl;
    cin>>out_name;
    outfile.open(out_name.c_str());
    PrintTree(root,outfile);
    outfile.close();
    return 0;
}