Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s in lexicographic order.

Example 1:

Input: aab
Output:
a a b
aa b

Example 2:

Input: a
Output:
a

Constraints:

• 1 ≤ s.length ≤ 16
• s consists of only lowercase English letters.

Input format: A single string.

Output format: Each valid partition on its own line, parts space-separated. In lexicographic order.