/*
 * lower_bound-insert.cc
 *
 * Strings are stored in alphabetical order, pair::second is used to
 * count the number of times each string has occured in the input.
 *
 * std::lower_bound() is used to find the position where a string is
 * to be stored.
 *
 * vector::insert() or vector::emplace() is used to insert the string
 * into place.
 */
#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <utility>
#include <vector>
using namespace std;

using pair_si = pair<string, int>;
using vector_psi = vector<pair_si>;

void insert(const string& s, vector_psi& v);
void insert(string&&, vector_psi&);

namespace std  // ADL (actually only pair_si overload create problem)
{
   ostream& operator<<(ostream&, const pair_si&);
   ostream& operator<<(ostream&, const vector_psi&);
}

int main()
{
   vector_psi v;
   string     s;

   while (cin >> s)
   {
      // insert(s, v);
      insert(move(s), v);
   }

   cout << v << endl;

   return 0;
}

void insert(const string& s, vector_psi& v)
{
   auto pos = lower_bound(begin(v), end(v), s,
			  [](const pair_si& p, const string& s) 
			  { return p.first < s; });

   if (pos != end(v) && pos->first == s)
   {
      ++pos->second;
      return;
   }

   v.insert(pos, { s, 1 });
}

void insert(string&& s, vector_psi& v)
{
   auto pos = lower_bound(begin(v), end(v), s,
			  [](const pair_si& p, const string& s) 
			  { return p.first < s; });

   if (pos != end(v) && pos->first == s)
   {
      ++pos->second;
      return;
   }

   v.emplace(pos, s, 1 );
}

namespace std
{
   ostream& operator<<(ostream& os, const pair_si& p)
   {
      os << p.first << " (" << p.second << ")";
      return os;
   }

   ostream& operator<<(ostream& os, const vector_psi& v)
   {
      copy(begin(v), end(v), ostream_iterator<pair_si>{os, "\n"});
      return os;
   }
}