Description

一个字符串的某一个子串中可能含有重复出现的字符，如字符串"abab"的其中一个子串"aba"就含有2个重复出现的字符"a"。现给出一个字符串，要求找出无重复字符的最长子串。

Format

Input

一行，若干个字符

Output

输出无重复字符的最长子串，若有多个最长子串，则输出起始位置最小的子串。

Samples

abab

ab

Limitation

1s, 1024KiB for each test case.