Longest Repeating T1 Substring

You are given a non-empty string s. Your task is to find the longest substring t₁ (which is a prefix of s) such that the concatenation t1t1 appears as a substring within s.

If there is no such substring, output an empty string.

Formally, you need to find the largest integer k (with k > 0) such that, if t1 = s[0:k], then t1t1 (i.e. t1 concatenated with itself) is a substring of s. All indices are 0-indexed.

Note: In the above description, if you wish to represent any mathematical formula, please use LaTeX format. For instance, you can describe the condition as: $$ s\text{ contains }t_1t_1\quad\text{ where } t_1 = s[0:k]. $$

inputFormat

The input consists of a single line containing the string s (1 ≤ |s| ≤ 1000).

outputFormat

Output the longest substring t₁ such that t1t1 is a substring of s. If no such substring exists, output an empty string.

abcabcabcabc

abcabc