Time Limit: 8 sec / Memory Limit: 64 MB





Example

Input

eggchickenegg


Output

egg
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#define X first
#define Y second
using namespace std;

int main(){
	string key[] = {"egg", "chicken"};
	vector<vector<string> > combi(1000);
	pair<int, int> currentpos(0, 0); 
	string input;
	cin >> input;
	for(int i = 0; i < input.size();){
		int index;
		if(input[i]==key[0][0]){
			index = 0;
			i += key[0].size();
		}
		else if(input[i]==key[1][0]){
			index = 1;
			i += key[1].size();
		}
		if(currentpos.Y){
			if(combi[currentpos.X][currentpos.Y-1] == key[index]){
				currentpos.X++;
				currentpos.Y = 0;
			}
			combi[currentpos.X].push_back(key[index]);
		}
		else combi[currentpos.X].push_back(key[index]);
		currentpos.Y++;
	}
	int maxX = 0, maxY = 0;
	for(int i = 0; i < combi.size(); i++){
		if(maxY < combi[i].size()){
			maxX = i;
			maxY = combi[i].size();
		}
	}

	cout << combi[maxX][maxY-1] << endl;
	return 0;
}