• محدودیت زمان: ۱۰ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

آقا حسین، یکی از دانشجویان قوی و پر تلاش رشته کامپیوتر دانشگاه دورقوزآباد، مشغول تمرین برنامه نویسی به کمکِ الگوریتم های بازگشتی بود که با سؤال جالبی برخورد کرد. حسین آقا که هنوز با مفاهیم آرایه و رشته آشنایی نداشت، تصمیم گرفت مرز های علم و دانش را جا به جا کرده و هر طور که ممکن است این سوال را حل کند.

برنامه ای بنویسید که تمامِ زیر مجموعه های مجموعه اعداد ‍‍۱ تا $n$ را به ترتیبی مانند مثال های داده شده، در خروجی چاپ کند.

آقا حسین پس از ساعت ها تلاشِ پیاپی، موفق به حل این سوال نشد، حال این شما و این سوالِ آقا حسین.

ورودی

ورودی تنها شامل یک خط است که در آن عدد طبیعی $n$ آمده است. $$1 \le n \le 20$$

خروجی

هر خط از خروجی شامل یک زیر مجموعه از مجموعه اعداد ۱ تا $n$ بوده و اعضای مجموعه با یک فاصله از یک دیگر چاپ خواهند شد.

مثال

ورودی نمونه ۱

3

خروجی نمونه ۱

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

ورودی نمونه ۲

4

خروجی نمونه ۲

{ 1 2 3 4 }
{ 1 2 3 }
{ 1 2 4 }
{ 1 2 }
{ 1 3 4 }
{ 1 3 }
{ 1 4 }
{ 1 }
{ 2 3 4 }
{ 2 3 }
{ 2 4 }
{ 2 }
{ 3 4 }
{ 3 }
{ 4 }
{ }