Time Limit: 8 sec / Memory Limit: 64 MB





Example

Input

eggchickenegg


Output

egg
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main() {
  string s;
  cin >> s;
  const static string name[2] = {"egg","chicken"};
  vector<int> v;
  for(int i = 0; i < s.size(); ) {
    for(int j = 0; j < 2; ++j) {
      if(s[i] == name[j][0]) {
	v.push_back(j);
	i += name[j].size();
	break;
      }
    }
  }

  vector<vector<int> > t;
  for(int i = 1, length = 1, id = 0; i <= v.size(); ++i) {
    if(i == v.size() || v[i-1] == v[i]) {
      vector<int> tmp(3);
      tmp[0] = -length;
      tmp[1] = id++;
      tmp[2] = v[i-1];
      t.push_back(tmp);
      length = 1;
    } else {
      ++length;
    }
  }
  sort(t.begin(), t.end());
  cout << name[t[0][2]] << endl;
  return 0;
}