Palindrome Decomposition

Given a string s, find all possible decompositions such that every substring in the decomposition is a palindrome.

A palindrome is a string that reads the same forwards and backwards. For example, "racecar" is a palindrome because it is identical when reversed.

Your task is to output all possible decompositions of the input string where each decomposition is a list of palindromic substrings. The output should be printed in a Python-style list format. For example, for the input aab the expected output is [['a', 'a', 'b'], ['aa', 'b']].

The underlying algorithm typically uses backtracking to generate all valid partitions. As a reminder, a decomposition P of string s is a list [p₁, p₂, ... , p_k] where each p_i is a palindrome and p₁ + p₂ + ... + p_k = s.

Note on formulas: A string s of length n can be decomposed into palindromes if for every index i (with 0 \le i < n), there is some j such that s[i:j] is a palindrome. In \( O(2^n) \) worst-case time, all partitions may be generated.

inputFormat

Input is read from standard input. A single line containing a non-empty string s is provided.

outputFormat

Print the list of all possible palindrome decompositions of s to standard output. The decompositions should be printed as a Python-style list of lists. Each inner list represents one valid decomposition where every substring is a palindrome.## sample

aab

[['a', 'a', 'b'], ['aa', 'b']]