/*
 * lower_bound-rotate.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.
 *
 * std::rotate() is used to rotate the string into place, after inserting it at 
 * the end of the container, using vector::push_back() or vector::emplace_back().
 */
#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&& s, vector_psi& v);

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;
   }

   auto distance = pos - begin(v);  // push_back() invalidates iterators

   v.push_back({ s, 1 });
   rotate(begin(v) + distance, end(v) - 1, end(v));
}

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;
   }

   auto distance = pos - begin(v);  // emplace_back() invalidates iterators

   v.emplace_back(s, 1);
   rotate(begin(v) + distance, end(v) - 1, end(v));
}

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;
   }
}