#include <iostream.h>
#include <string.h>

/*
     Copyright (c) 1999 Nathan Meyers
     $Id: wordtree.C,v 1.5 1999/11/10 17:48:17 nathanm Exp $

     Permission is hereby granted, free of charge, to any person obtaining
     a copy of this software and associated documentation files (the
     "Software"), to deal in the Software without restriction, including
     without limitation the rights to use, copy, modify, merge, publish,
     distribute, sublicense, and/or sell copies of the Software, and to
     permit persons to whom the Software is furnished to do so, subject
     to the following conditions:

     The above copyright notice and this permission notice shall be
     included in all copies or substantial portions of the Software.

     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
     KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
     WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
     NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
     BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
     AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
     IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
     THE SOFTWARE.
*/

// Node: Represent a node in our dictionary tree
class Node
{
public:
    char *mystring;
    int input_count;
    int other_count;
    Node *left, *right;
    // Constructor: Create a local copy of the word and zero the count
    Node(char *s)
    {
	mystring = new char[strlen(s) + 1];
	strcpy(mystring, s);
	input_count = 0;
	other_count = 0;
	left = right = NULL;
    }
    // Destructor: Delete local copy of the word
    ~Node()
    {
	delete[] mystring;
    }
    // Comparison operators
    operator<(Node &n)
    {
	return strcmp(mystring, n.mystring) < 0;
    }
    operator==(Node &n)
    {
	return !strcmp(mystring, n.mystring);
    }
    operator!=(Node &n)
    {
	return strcmp(mystring, n.mystring) != 0;
    }
    operator>(Node &n)
    {
	return strcmp(mystring, n.mystring) > 0;
    }
    // Define a way to output this node
    friend ostream& operator<<(ostream &str, Node &n)
    {
	return str << n.mystring << ": " << n.input_count << ", "
		   << n.other_count;
    }
    // In-order recursive traversal code: arg is a function to be
    // executed for each node
    void traverse(void(*proc)(Node &))
    {
	if (left) left->traverse(proc);
	proc(*this);
	if (right) right->traverse(proc);
    }
    // Method to increment the count for a node matching the requested
    // key
    void count_word(Node &);
};

// Here is our main dictionary, including root of the tree
class Dictionary
{
    Node *root;
public:
    Dictionary(istream &);
    // Start an in-order traversal on the root
    void traverse(void(*proc)(Node &))
    {
	root->traverse(proc);
    }
    // Look for this word in the dictionary. If we find it, increment
    // its counter.
    void count_word(char *word)
    {
	// Create an automatic instance of node to use as key
	Node node(word);
	// Start searching at root
	root->count_word(node);
    }
};

// We'll use this class to throw an exception
class ErrorMsg
{
public:
    char *message;
    // Constructor: A message and a missing word to concatenate
    ErrorMsg(char *msg, char *word)
    {
	// Allocate enough space to hold the concatenated message plus
	// a space plus null
	message = new char[strlen(msg) + strlen(word) + 2];
	strcpy(message, msg);
	strcat(message, " ");
	strcat(message, word);
    }
    ~ErrorMsg()
    {
	delete[] message;
    }
    friend ostream& operator<<(ostream &str, ErrorMsg &msg)
    {
	return str << msg.message;
    }
};

// This is the function we'll use for node traversal
void print_a_word(Node &node)
{
    cout << node << '\n';
}

int main(int argc, char *argv[])
{
    Dictionary dictionary(cin);
    for (int i = 1; i < argc; i++)
    {
	try { dictionary.count_word(argv[i]); }
	catch (ErrorMsg &msg)
	{
	    cerr << msg << '\n';
	}
    }
    dictionary.traverse(print_a_word);
}

Dictionary::Dictionary(istream &str)
{
    char word[1024];
    root = NULL;
    // Build a simple, unbalanced binary tree containing all words we
    // scan from str.
    while (!(str >> word).fail())
    {
	// If tree is empty, build root from first word
	Node *newnode;
	if (!root) newnode = root = new Node(word);
	else
	{
	    // Build a local Node to use as a key
	    Node key(word);
	    // Start search from root
	    newnode = root;
	    // Continue until we find matching node
	    while (key != *newnode)
	    {
		if (key < *newnode)
		{
		    if (!newnode->left) newnode->left = new Node(word);
		    newnode = newnode->left;
		}
		else
		{
		    if (!newnode->right) newnode->right = new Node(word);
		    newnode = newnode->right;
		}
	    }
	}
	newnode->input_count++;
    }
}

void Node::count_word(Node &key)
{
    // Look for a matching node in the tree. If we find it, increment the
    // counter, else throw an exception.
    if (key == *this)
    {
	other_count++;
	return;
    }
    if (key < *this && left) left->count_word(key);
    else if (key > *this && right) right->count_word(key);
    else throw(ErrorMsg("No such word:", key.mystring));
}