题目描述

给定一个集合 S，使用递归生成其所有子集。

输入格式

第一行一个整数 n，表示集合的大小。第二行 n 个不同的整数，表示集合元素。

输出格式

按字典序打印所有子集，每个子集中的元素按升序排列，子集之间用换行分隔。

示例

输入

3
1 2 3

输出

{}
{1}
{1,2}
{1,2,3}
{1,3}
{2}
{2,3}
{3}