All Palindromic Substrings

Given a string S, find and output all of its palindromic substrings. A substring is a contiguous sequence of characters from S and is considered palindromic if it reads the same forwards and backwards, i.e. if it satisfies the condition $$X = X^R$$ where \(X^R\) is the reverse of \(X\).

The substrings should be printed in a specific order: first, all substrings of length 1 in their original order, then all substrings of length 2, and so on. Duplicate substrings produced from different positions must be preserved.

For example:

• For input "aba", the output should be:

a
b
a
aba

Note: For some test cases the order is not explicitly checked (set equality is used), but for others (e.g. when the string length is one), the exact order must be produced.

inputFormat

The input consists of a single line containing a non-empty string S.

Constraints:

• The length of S is at least 1 and at most 1000.

outputFormat

Output all palindromic substrings found in S following these rules:

• Substrings are grouped and printed in order of increasing length.
• Within the same length, maintain the original order as they appear in S.
• Each substring must be printed on a separate line.

## sample

aba

a
b
a
aba

</p>