UPSUB  Up Subsequence
If x = a_{0}a_{1}a_{2}...a_{n1} is a string where a_{i} denotes the character at index i, a subsequence a_{j0}a_{j1}a_{j2}...a_{jn} is called an upsubsequence if a_{j0} <= a_{j1} <= a_{j2} <= ... <= a_{jn} and j0 < j1 < j2 < ... < jn.
A maximal upsubsequence of a string is defined as the upsubsequence of maximum length. BuggyD observes that a string x can have many maximal upsubsequences. Help him find all the maximal upsubsequences in x.
Input
The first line of the input contains an integer t, the number of test cases. t test cases follow.
Each test case consists of a single line containing a string x, where the length of x is no more than 100. x will not contain any spaces, tabs or other whitespace characters.
Output
For each test csae, output all of the maximal upsubsequences of x in lexicographical order. Print a blank line after each test case.
Example
Input: 1 abcbcbcd Output: abbbcd abbccd abcccd
hide comments
Shubham:
20160518 17:46:30
solve TRIP first :D :D 

Ankit:
20151015 18:04:26
moving backwards will automatically give sorted order :) 

Praneeth.N:
20150226 02:36:14
I am not sure why the problem is giving wrong answer inspite of covering all the cases...Can some one kindly give some hints or a test case where there is chance of getting wrong answer.. 

Zen:
20140819 10:54:55
:D


kipoujr:
20111019 18:20:57
You forgot to place a '\n' character at the end of the file! Please correct. 
Added by:  Matthew Reeder 
Date:  20061030 
Time limit:  0.309s 
Source limit:  30000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  AlKhawarizm 2006 