Palindrome Partitioning

Given a string s, your task is to partition s into substrings such that each substring is a palindrome. Return all possible palindrome partitionings of s in the format of pipe-separated substrings. The order of the partitionings can be arbitrary.
A palindrome is a string that reads the same forward and backward.

Input

The input consists of a single string s (1 ≀ |s| ≀ 16), containing only lowercase English letters.

Output

Return a list of all possible palindrome partitionings of s. Each partitioning should be represented as a string where the substrings are joined with the | symbol. The order of the partitionings in the output list can be arbitrary.

Examples

Input
Output
aab
a|a|b aa|b
aba
a|b|a aba

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue