Longest Prefix Suffix

medium
Question Solve Solutions 
Given a string S, print the longest Prefix which is also a suffix.
Try doing it using constant space.

Input Format

A string S

Output Format

Print the answer, print "" (without quotes) if no answer found.

Constraints

2 <= |S| <= 10^5

Example

Input
abcab
Output
ab
Previous
Longest Duplicate Substring
Next
Lexicographical Suffixes

Related Questions

easy Shortest Palindrome medium Longest Palindromic Substring hard Kmp Pattern Searching hard Z Algorithm For Pattern Searching hard Find String Roots hard Manacher's Algorithm hard String Rotation hard Prefix And Suffix Count medium Say No To Palindrome medium String Polynomial Hashing medium Diane medium Rabin Karp Pattern Find (spoj) hard Password medium Good Substrings hard Longest Duplicate Substring hard Lexicographical Suffixes