#!/usr/bin/env python2.7 import sys word = raw_input() assert 1 <= len(word) <= 1000000 if word == word[::-1]: print word sys.exit(0) word = "____" + word word_ = word tmp = [">"] for c in word: tmp.append(c) tmp.append("-") tmp = tmp[:-1] tmp.append("<") word = tmp wl = len(word) pal_center = 0 pal_end = 0 scores = [0]*wl for i in xrange(1, wl-1): score = 0 if pal_end > i: score = min(pal_end - i, scores[pal_center * 2 - i]) while True: if word[i + score + 1] == word[i - score - 1]: score += 1 else: break if i + score > pal_end: pal_center = i pal_right = i + score scores[i] = score #print word #print scores tmp = list(enumerate(scores)) m = max(tmp, key=lambda x: x[1]) i, l = m #print "index=%d len=%d" % (i,l) #print (i - 1 - l) #print (i - 1 - l) / 2 start = ((i - 1 - l) / 2) + 1 end = start + l print word_[start:end]