/*
 * find_if-insert-multi.cc
 *
 * Strings are stored in alphabetical order. If the same string is already
 * stored, a new entry for that string is placed after the excisting ones.
 * pair::second is used to verify this, by storing the order in which 
 * strings are read.
 *
 * std::find_if() 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&, vector_psi&);
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)
{
   static int n = 0;

   auto pos = find_if(begin(v), end(v), 
		      [&](const pair_si& p) { return s < p.first; });

   v.insert(pos, { s, ++n });
}

void insert(string&& s, vector_psi& v)
{
   static int n = 0;

   auto pos = find_if(begin(v), end(v), 
		      [&](const pair_si& p) { return s < p.first; });

   v.emplace(pos, move(s), ++n);
}

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