Lexicographical Suffixes

hard
Question Solve Solutions 
Given a string, print all suffixes of it in lexicographical order.

Input Format

A string S.

Output Format

Print |S| lines, each having a suffix.

Constraints

|S| <= 10^5

Example

Input
bananaban
Output
aban
an
anaban
ananaban
ban
bananaban
n
naban
nanaban
Previous
Longest Prefix Suffix
Next
Longest Common Substring (2 Strings)

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