Sorted Substrings

You are given a string (S). Your task is to generate all possible substrings of (S) and then output them in lexicographical order. A substring is a contiguous sequence of characters within a string. Note that if the same substring appears more than once, only one instance should be kept. Read the string from standard input and output each unique substring on a new line in sorted order.

For example, given (S = \texttt{bcda}), the unique substrings in lexicographical order are: (a, b, bc, bcd, bcda, c, cd, cda, d, da).

inputFormat

The input consists of a single line containing the string (S). The string will be non-empty and may contain any characters.

outputFormat

Output all unique substrings of (S) in lexicographical order. Each substring should be printed on its own line.## sample

bcda

a
b
bc
bcd
bcda
c
cd
cda
d
da