Challenge: Every Subset

Lab Python Intermediate 20 points

Read some distinct letters and print every subset using backtracking, one per line, in this order: at each letter, first explore taking it, then skipping it. Print each subset as its letters joined together, and the empty subset as {}.

Input

One line of distinct letters separated by spaces (at most 10).

Output

2ⁿ lines.

Example

Input

a b c

Output

abc
ab
ac
a
bc
b
c
{}

Sample input available Sample output available

Editor

Python

Hints

explore(i) decides about items[i].

Choose (append), explore(i + 1), un-choose (pop), then explore(i + 1) again.

Solution explanation

Each letter is either in or out, giving 2ⁿ subsets.

Show solution

items = input().split()
cur = []


def explore(i):
    if i == len(items):
        print("".join(cur) if cur else "{}")
        return
    cur.append(items[i])
    explore(i + 1)
    cur.pop()
    explore(i + 1)


explore(0)

Output

Answer