Expect some short downtimes and small glitches during the first week of February.

Subsets (1) P18957

Statement

Write a program that, given $n$ different words $s_1, \dots, 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_1, \dots, s_n$ .

Print all the subsets that can be made up with $s_1, \dots, 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