Dfs In Suffix Tree
hard
Suffix Tree is implemented for you, you just have to write the code for DFS traversal and print all the suffixes in lexicographical order
Constraints
|S| <= 10^5
Format
Input
Given a string S
Output
Output each suffix in lexicographical order on different lines
Example
Sample Input
abca
Sample Output
$
a$
abca$
bca$
ca$