Find Palindromic Subsequences

Given a string, your task is to find all distinct non-empty subsequences that are palindromes. A subsequence is obtained by deleting zero or more characters from the original string without changing the order of the remaining characters. A palindrome is a string that reads the same forwards and backwards. In this problem, you are required to output the palindromic subsequences in lexicographical order (i.e. sorted alphabetically), with each subsequence separated by a space.

The mathematical formulation for a palindrome can be written as:

\( s = s^R \),

where \( s^R \) denotes the reverse of string \( s \).

Note: The input string is intentionally kept small (for example, with a length of at most 15) to allow for the generation of all subsequences, since the number of subsequences grows exponentially with the length of the string.

inputFormat

The input consists of a single line containing a string.

outputFormat

Output all distinct non-empty palindromic subsequences sorted in lexicographical order. The subsequences should be separated by a single space. If no valid palindromic subsequences exist, output an empty line.

abca

a aa aba aca b c