Palindromic Substrings

You are given a string s of length n. Your task is to find all substrings of s that are palindromes. A palindrome is a string that reads the same backward as forward. Note that even single characters are considered palindromic.

The algorithm should identify all palindromic substrings (including duplicates) following the order determined by examining all substrings in increasing length order (from 1 to n) and, for a fixed length, scanning from left to right.

Example:

• Input: aaa
• Output (each substring on a new line):

  a
  a
  a
  aa
  aa
  aaa
      

Note: The output should be printed to standard output with each palindromic substring on a separate line.

inputFormat

The input consists of a single line containing the string s.

Constraints: You may assume that the length of the string is at least 1.

outputFormat

Print each palindromic substring found in the string on a separate line, in the order defined by checking all substrings of increasing length, and for a given length, in left-to-right order.

a

a