Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence in s. A subsequence is a sequence that can be derived from the string by deleting some or no characters without changing the order of the remaining characters. A palindrome is a string that reads the same backward as forward.

If there are multiple longest palindromic subsequences, output the lexicographically smallest one.

Note: The solution should read the input from standard input and print the result to standard output.

inputFormat

The input consists of a single line containing the string s (with length at least 1).

outputFormat

Output the longest palindromic subsequence as described. If multiple solutions exist, output the lexicographically smallest one.

a

a