Generate All Combinations of Characters

You are given a non-empty string ( s ) consisting of characters (which may include duplicates). Your task is to generate all possible combinations (i.e. non-empty subsequences) of the characters from the string. A combination is defined as a sequence that can be obtained by deleting some (or no) characters without changing the relative order of the remaining characters. The result should include duplicate combinations if they occur, and the final output must list all combinations in lexicographical order.

Formally, for a string ( s ) of length ( n ), for every non-empty subset of indices ( { i_1, i_2, \ldots, i_k } ) such that ( 1 \le i_1 < i_2 < \cdots < i_k \le n ), the corresponding combination is ( s_{i_1} s_{i_2} \ldots s_{i_k} ).

inputFormat

Input is read from standard input (stdin). It consists of a single line containing the string ( s ).

outputFormat

Output to standard output (stdout) the generated combinations, each on a separate line, in lexicographical order.## sample

a

a