Subsets (1) P18957

Statement

thehtml

Write a program that, given n different words s₁, …, s_n, prints all the subsets that can be made up with the words.

Input

Input consists of a number n > 0, followed by s₁, …, s_n.

Output

Print all the subsets that can be made up with s₁, …, s_n.

You can print in any order both the solutions and the elements inside each solution.

Public test cases

Input

3
hola adeu hi

Output

{}
{hi}
{adeu}
{adeu,hi}
{hola}
{hola,hi}
{hola,adeu}
{hola,adeu,hi}

Information