Dfs In Suffix Tree

hard

Text Processing

Question Solve Solutions

Suffix Tree is implemented for you, you just have to write the code for DFS traversal and print all the suffixes in lexicographical order

Input Format

Given a string S

Output Format

Output each suffix in lexicographical order on different lines

Constraints

|S| &lt;= 10^5

Example

Input

abca

Output

$
a$
abca$
bca$
ca$

Hidden Password - Icpc Regionals

Sufix Tree - Application 1 - Pattern Find

Related Questions

easy Shortest Palindrome medium Longest Palindromic Substring hard Kmp Pattern Searching hard Z Algorithm For Pattern Searching hard Find String Roots hard Manacher's Algorithm hard String Rotation hard Prefix And Suffix Count medium Say No To Palindrome medium String Polynomial Hashing medium Diane medium Rabin Karp Pattern Find (spoj) hard Password medium Good Substrings hard Longest Duplicate Substring medium Longest Prefix Suffix