뒤틀린 운명과 함께, Nadeko는 알파벳 소문자로 이루어진 문자열 $s$를 가지고 있습니다. 그녀의 궁극적인 소원은 다음 조건을 만족하는 문자열 $t$를 만드는 것입니다:
- $t$는 $s$를 부분수열로 포함하지 않습니다.
- $s$와 일치하지 않는 $s$의 모든 부분수열은 $t$에 부분수열로 포함됩니다.
가능한 한 가장 짧은 길이의 문자열 $t$를 찾도록 도와주세요. 그러한 문자열이 여러 개 있다면 아무것이나 출력해도 됩니다.
입력
입력의 첫 번째 줄에 Nadeko의 문자열 $s$ ($2 \le |s| \le 10^6$)가 주어집니다. $s$는 알파벳 소문자로만 이루어져 있음이 보장됩니다.
출력
문제의 조건을 만족하는 최소 길이의 문자열 $t$를 한 줄에 출력합니다.
예제
입력 1
aaaa
출력 1
aaa
입력 2
bba
출력 2
bab
참고
두 번째 예제에서 문자열 bab는 bb, ba, a, b를 부분수열로 포함하지만 bba는 포함하지 않습니다. 또한 길이가 $2$인 올바른 수열을 구성하는 것이 불가능하다는 것은 자명하므로 bab는 가능한 답입니다.