Given a string s$,$ find all longest palindromic subsequences in s$.$ Return the list of subsequences which being sorted in lexicographic order. You may assume that the maximum length of s is $1000.$

Example $1$:

input: "bacdab"

output: "bacab badab"

Example $2$:

input: $"$bcdcdb$"$

output: $"$bcdcb$","$bdcdb$"$

Input Format

string

Constraints

length of string s $<=1000$

Output Format

sorted array of strings

Sample Input $0$

bacdab

Sample Output $0$

bacab badab